### 习题

1. Consider the problem of finding all the anagrams of a given input word. How would you solve the problem given the word and the dictionary? What if you could spend some time and space to process the dictionary before answering any query?

2. Given a tape containg 4,300,000,000 32-bit integers, how can you find one that appears at least twice?

3. We studied two vector rotation algorithms that require subtle code; implement each as a program. How does the greatest common divisor of I and N appear in the analysis of each program?

5. Vector rotation routines change the vector AB to BA; how would you transfrom the vector ABC to CBA? (This models the problem of swapping unequal-length blocks of memory.)

6. Bell Labs has a “user-operated directory assistancd” program that allows employees to look up a number in a company telephone directory using a standard push-button telephone. To find the number of the designer of the system, Mike Lesk, one dials the number of the service, types “LESK*M*” (that is, “5375*6*”) and the system then speaks his number. One problem that arises in this system is that different names may have the same push-button encoding; when this happens in Lesk’s system, it asks the user for more information. Given a large file of names, such as a standard metropolitan telephone directory, how would you locate these “false matches”? (When Lesk did this experiment on such a directory, he found that their incidence was just 0.2 percent.) How would you implement the routine that is given a push-button encoding of a name and returns eigher a name or an appropriate message?

7. In the early 1960’s Vic Vyssotsky worked with a programmer who had to transpose a 4000-by-4000 matrix stored on magnetic tape(each record had the same several-dozen-byte format). The original program his colleague suggestd would have taken fifty hours to run; how would Vyssotsky reduce the run time to half an hour?

8. [J. Ullman] Given a set of N real numbers, a real number T, and an integer K, how quickly can you determine whether there exists a K-element subset of the set that sums to at most T?

9. Sequential search and binary search represent a tradeoff between search time and preprocessing time. How many binary searches need be performed in an N-element table to buy back the preprocessing time required to sort the table?

$O\left(n\log n\right) + k \times O\left(\log n\right) \leq k \times O\left(n \right)$

$k \geq O\left(\log n\right)$

10. On the first day a researcher worked with Thomas Edison, Edison asked him to compute the volume of an empty light bulb shell. After several hours with calipers and calculus, he returned with the answer of 150 cubic centimeters. In a few seconds, Edison computed and responded “closer to 155” –– how did he do it? Given other examples of aha! insights in analog computation.

0%