3. Algorithm Building Blocks

Question 1

What are the general sections in the algorithm template format used by Algorithms in a Nutshell?

Answer 1

Name, Input/Output, Context, Solution, Analysis, Variations.

Question 2

What is the Name section of the algorithm template?

Answer 2

A descriptive name for the algorithm, which is used to communicate the algorithm concisely to others.

Question 3

What is the Input/Output section of the algorithm template?

Answer 3

It describes the expected format of input data to the algorithm and the resulting values computed.

Question 4

What is the Context section of the algorithm template?

Answer 4

A description of a problem that illustrates when an algorithm is useful and when it will perform at its best. A description of the properties of the problem/solution that must be addressed and maintained for a successful implementation.

Question 5

What is the Solution section of the algorithm template?

Answer 5

The algorithm description using real working code with documentation.

Question 6

What is the Analysis section of the algorithm template?

Answer 6

A synopsis of the analysis of the algorithm, including performance data and information that helps to understand the behavior of the algorithm.

Question 7

What is the Variations section of the algorithm template?

Answer 7

It presents variations of the algorithm or different alternatives.

Question 8

What is the pseudocode template format of Algorithms in a Nutshell?

Answer 8

The pseudocode description is intentionally brief. Keywords and function names are described in boldface text. All variables are in lowercase characters, whereas arrays are capitalized and their elements are referred to using A[i] notation. The indentation in the pseudocode describes the scope of conditional if and looping while and for statements.

Question 9

What is the empirical evaluation format of Algorithms in a Nutshell?

Answer 9

The performance of each algorithm is confirmed by executing a series of benchmark problems appropriate for each individual algorithm. To properly evaluate the performance, a test suite is composed of a set of k individual trials (typically k ≥ 10). The best and worst performers are discarded as outliers, the remaining k — 2 trials are aggregated, and the average and standard deviations are computed. Tables are shown with problem instances typically ranging in size from n = 2 to 2²⁰.

Question 10

What are some differences in computation between integers and floating-point values?

Answer 10

Computers perform basic computations on values stored in registers by the CPU, which are typically 64-bits in size on modern computers. The CPU often supports basic operations—such as ADD, MULT, DIVIDE, and SUB—over integer values stored in these registers. Floating-point units (FPUs) can efficiently process floating-point computations according to the IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754). Mathematical computations over integer-based values have traditionally been the most efficient CPU computations, however, modern CPUs have dramatically improved the performance of floating-point computations relative to their integer counterparts.

Question 11

What are some performance issues of floating-point computation?

Answer 11

Despite substantial speed improvements in floating-point computation by processors over time, floating-point computations still tend to be thousands of times slower than their integer counterparts for common mathematical operations (CMP, MULT, DIV), however the differences between different sizes of floating-point values (32-bit, 64-bit, and 128-bit) are considerably less pronounced.

Question 12

How are 32-bit floating-point values (floats) represented?

Answer 12

1 bit for the sign, 8 bits for the exponent, and 23 bits for the mantissa.

Question 13

How are 64-bit floating-point values (doubles) represented?

Answer 13

1 bit for the sign, 11 bits for the exponent, and 52 bits for the mantissa.

Question 14

What is a technique used to achieve the greatest precision with the floating-point representation?

Answer 14

The mantissa is always normalized so that the left-most digit is always 1; this bit does not have to actually be stored, but is understood by the floating-point processor to be part of the number.

Question 15

How are floating-point values calculated?

Answer 15

(sign)*(mantissa)*2^exponent, where the sign is -1 or 1, the mantissa is a value between 0 and 1, and the exponent is a non-negative integer.

Question 16

How are floating-point errors described?

Answer 16

The most common way of describing floating-point error is to use the term relative error, which computes the ratio of the absolute error with the desired value. It is quite common for these relative errors to be less than 1 part per million.

Question 17

What is an approach to solving for rounding errors in floating-point computation?

Answer 17

One common solution is to introduce a small value δ to determine ≅ (approximate equality) between two floating-point values. Under this scheme, if |x — y| < δ, then we consider x and y to be equal. Still, by this simple measure, even when x ≅ y and y ≅ z, it’s possibly not true that x ≅ z. This breaks the principle of transitivity in mathematics and makes it really challenging to write correct code. Additionally, certain problems use signs of the value (0, positive, or negative) to make their decision.

Question 18

What are some uses of special quantities in floating-point representation?

Answer 18

Certain values are defined by the IEEE standard are reserved for interpretation as special numbers, and were designed to make it easier to recover from common errors, such as divide by zero, square root of a negative number, overflow of computations, and underflow of computations.

Question 19

What are the special quantities of IEEE 754?

Answer 19

• Positive infinity (exponent = max, mantissa = 0, sign = +)
• Negative infinity (exponent = max, mantissa = 0, sign = -)
• Not a number (NaN) (exponent = max, mantissa = non-zero, sign = any)
• Negative zero (exponent = 0, mantissa = 0, sign = -)
• Positive zero (exponent = 0, mantissa = 0, sign = +)

Question 20

Which special quantities can be used in computations?

Answer 20

Positive zero and negative zero.

Question 21

What are some characteristics of Greedy strategies?

Answer 21

A Greedy strategy completes a task of size n by incrementally solving the problem in steps. At each step, a Greedy algorithm will make the best local decision it can given the available information, typically reducing the size of the problem being solved by one. Once all n steps are completed, the algorithm returns the computed solution. Greedy strategies can be identified by the way the subproblems being solved shrink very slowly as an algorithm processes the input.

Question 22

What is the performance of Greedy strategies?

Answer 22

When a subproblem can be completed in O(log n) then a Greedy strategy will exhibit O(n log n) performance. If the subproblem requires O(n), then the overall performance will be O(n²).

Question 23

What are some characteristics of Divide and Conquer strategies?

Answer 23

A Divide and Conquer strategy solves a problem of size n by dividing it into two independent subproblems, each about half the size of the original problem. Quite often the solution is recursive, terminating with a base case that can be solved trivially. There must be some resolution computation that can determine the solution for a problem when given two solutions for two smaller subproblems.

Question 24

What is the performance of Divide and Conquer strategies?

Answer 24

A Divide and Conquer algorithm will exhibit O(n) performance if the resolution step can be accomplished in constant O(1) time. When the resolution step itself requires O(n) computations, then the overall performance will be O(n log n).

Question 25

What are some characteristics of Dynamic Programming?

Answer 25

Dynamic Programming is a variation on Divide and Conquer that solves a problem by subdividing it into a number of simpler subproblems that are solved in a specific order. It solves each smaller problem just once and stores the results for future use to avoid unnecessary recomputation. It then solves problems of increasing size, composing together solutions from the results of these smaller subproblems. In many cases, the computed solution is provably optimal for the problem being solved. Dynamic Programming is frequently used for optimization problems where the goal is to minimize or maximize a particular computation.