                 int n; double x;
                 answer[1] = 1;
                 for (n = 2;n <= L;++n) {
                   x = answer[n/2] + answer[(n+1)/2] + r * n;
                   if (x < n * n) x = n * n;
                   answer[n] = x;
                 }

30. The straightforward recursive algorithm is

                 double T(int n)
                 { double x;
                   if (n == 1) return 1;
                   x = T(n/2) + T((n+1)/2) + r * n;
                   if (x < n * n) x = n * n;
                   return x;
                 }

which is much too slow; it does 2(n − 1) recursive calls. But caching the results is fast enough:

                 double T(int n)
                 { double x;
                   if (n == 1) return 1;
                   if (answer[n]) return answer[n];
                   x = T(n/2) + T((n+1)/2) + r * n;
                   if (x < n * n) x = n * n;
                   answer[n] = x;
                   return x;
                 }

There are several ways to reduce the space requirements.

31. The number of additions is \binom{n}{i} − 1.

32. One solution is to cache the results of the algorithm in exercise 31.

33(a). It takes n operations to choose the largest dimension and remove that dimension from the list, n − 1 operations to choose the largest remaining dimension and remove that dimension from the list, etc. The total time is O(n^{2}). There are faster algorithms.

33(b). Consider multiplying matrices of sizes 1×2, 2×4, and 4×3. The greedy algorithm multiplies 2×4×3 and then 1 × 2 × 3, for a total of 30 multiplications of real numbers. It is better to multiply 1 × 2 × 4 and then 1 × 4 × 3, for a total of 20 multiplications of real numbers.

34. T (n) = 3^{n}(n + 1).

35. T (n) = (a^{n+1} − b^{n+1})/(a − b).

36. T (n) = (41 · 3^{n} − 4n^{3} − 18n^{2} − 36n − 33)/8.

37. There is some constant k, depending on the model of computation, such that an algorithm can write at most k bits of output in each step. If the input of A_{1} has b bits then A_{1} performs at most p(b) steps, so the output of A_{1} has at most kp(b) bits, so A_{2} performs at most q(kp(b)) steps. Thus A_{3} performs at most p(b) + q(kp(b)) steps; this is a polynomial in b.

38. A proposed solution is a list of vertices v_{0}, v_{1}, v_{2}, …, v_{n}. A proposed solution v_{0}, v_{1}, v_{2}, …, v_{n} is a Hamilton circuit if and only if (1) v_{n} = v_{0}; (2) each vertex in the graph appears in v_{0}, v_{1}, v_{2}, …, v_{n−1} exactly once; (3) for each k, v_{k} is adjacent in the graph to v_{k+1}.

39. Given a graph, write down the same digraph, i.e., the digraph with edges x → y and y → x whenever the graph has edges x ↔ y. This function can be computed in polynomial time—in fact, in zero time if graphs and digraphs are represented in the usual way. The resulting digraph has a Hamilton circuit if and only if the original graph had a Hamilton circuit.

40. Reduction from the integer problem to the rational problem: given the integers, write down the same numbers as rational numbers. Reduction from the rational problem to the integer problem: given the rationals, multiply by all the denominators to obtain integers.