Hints for Selected Problems
Column 1
4. Read Column 12.
5. Consider a two-pass algorithm.
6, 8, 9. Try key indexing.
10. Consider hashing, and don’t limit yourself to a computerized system.
11. This problem is for the birds.
12. How do you write without using a pen?
Column 2
1. Think about sorting, binary search and signatures.
2. Strive for an algorithm that runs in linear time.
5. Exploit the identity cba = (arbrcr)r.
7. Vyssotsky used a system utility and two one-shot programs that he wrote just for this job to rearrange data on tapes.
8. Consider the k smallest elements in the set.
9. The cost of s sequential searches is proportional to sn; the total cost of s binary searches is the cost of the searches plus the time required to sort the table. Before you put too much faith in the constant factors of the various algorithms, see Problem 9.9.
10. How did Archimedes determine that the king’s crown wasn’t pure gold?
Column 3
2. Use one array to represent the coefficients of the recurrence and another to represent the k previous values. The program consists of a loop within a loop.
4. Only one function need be written from scratch; the other two can call that one.
Column 4
2. Work from a precise invariant. Consider adding two dummy elements to the array to help you initialize your invariant: x[– 1] = – ∞ and x[n] = ∞.
5. If you solve this problem, run to the nearest mathematics department and ask for a Ph.D.
6. Look for an invariant preserved by the process, and relate the initial condition of the can to its terminal condition.
7. Read Section 2.2 again.
9. Try the following loop invariants, which are true immediately before the test in the while statement. For vector addition,
i≤n && ∀1≤j<i a[j] = b[j] + c[j]
and for sequential search,
i≤n && ∀1≤j<i x[j] ≠ t
11. See Solution 11.14 for a recursive function that passes a pointer to an array.
Column 5
3. Search for terms like “mutation testing”.
5. What can you accomplish in O(log n) or O(1) extra comparisons?
6. This book’s web site contains a Java program with a GUI for studying sorting algorithms.
9. The tab-separated output format of the scaffolding is designed to be compatible with most spreadsheets. I usually store a series of related experiments on a single page of a spreadsheet, together with graphs of their performance and comments about why I did the experiments and what I learned from each.
Column 6
1. Peek ahead to Section 8.5.
3. Modify the cost model for run times described in Appendix 3 to measure the cost of double-precision operations.
7. Automobile accidents are avoided by measures such as driver training, strict enforcement of speed limits, a minimum drinking age, stiff penalties for drunk driving and a good system of public transportation. If accidents do occur, injuries to passengers can be reduced by the design of the passenger compartment, wearing seat belts (perhaps as mandated by law) and air bags. And if injuries are suffered, their effect can be reduced by paramedics at the scene, rapid evacuation in helicopter ambulances, trauma centers and corrective surgery.
Column 7
5. I first played with the function (1+x/100)72/x, then used a spreadsheet to plot (1+.72/x)x. To prove properties about the Rule of 72, recall that limn→∞ (1 + c/n)n = ec, that the natural logarithm of 2 is approximately .693, and that the asymptote is not always the optimal approximation line.
8. Consider especially the designs and programs in Problems 2.7, 8.10, 8.12, 8.13, 9.4, 10.10, 11.6, 12.7, 12.9, 12.11, 13.3, 13.6, 13.11, 15.4, 15.5, 15.7, 15.9 and 15.15 and in Sections 1.3, 2.2, 2.4, 2.8, 10.2, 12.3, 13.2, 13.3, 13.8, 14.3, 14.4, 15.1, 15.2 and 15.3.
Column 8
4. Plot the cumulative sum as a random walk.
7. Floating point addition is not necessarily commutative.
8. In addition to computing the maximum sum in the region, return information about the maximum vectors ending at each side of the array.
10, 11, 12. Use a cumulative array.
13. The obvious algorithm has O(n4) run time; strive for a cubic algorithm.
Column 9
3. The addition increased k by at most n –1, so we know that k is less than 2n.
9. To make binary search competitive with sequential search even at small values of n, make the comparison operation very expensive (see, for instance, Problem 4.7).
Column 10
1. What code did the compiler generate for accessing packed fields?
5. Mix and match functions and tables.
7. Reduce the data by considering certain ranges of memory to be equivalent. Those ranges might be either fixed-length blocks (say, 64 bytes) or function boundaries.
Column 11
2. Let the loop index i move from high to low, so that it approaches the known value t in x[l].
4. When you have two subproblems to solve, which should you solve right away and which should you leave on the stack to return to later — larger or smaller?
9. Modify Quicksort so that it recurs only on the subrange that contains k.
Column 12
4. Go to a statistician and use the phrases “Coupon Collector’s Problem” and “Birthday Paradox”.
11. The problem said you could use the computer; it didn’t say you had to.
Column 13
2. Error checking should test to ensure that an integer to be inserted is in the proper range and that the data structure is not yet full. A destructor should return any allocated storage.
3. Use a binary search to test whether an element is in a sorted array.
Column 14
2. Aim for a Heapsort with this structure.
3. See Problem 2, and also consider moving code out of loops.
6. Heaps have implicit pointers from node i to node 2i; try the same in disk files.
7. Binary search in x[0..6] uses an implicit tree whose root is in x[3]. How might the implicit trees of Section 14.1 be used instead?
9. Use the O(n log n) lower bound on sorting. If both insert and extractmin run in less than O(log n) time, then you could sort in less than O(n log n) time; show how to use the operations to sort that quickly.
Column 15
15. Suppose that we are generating order-1 Markov text from a million-word document that contains the words x, y and z only in the single phrase “x y x z”. Half the time x should be followed by a y, the other half it should be followed by a z. What odds does Shannon’s algorithm give?
16. How could you use counts of k-grams of letters or words?
17. Some commercial speech recognizers are based on trigram statistics.