book cover

Problems
(Section 7.6 of
Programming Pearls)

The quiz in Appendix 2 contains additional problems.

The Solutions to Column 7 give answers for some of these problems.

1. While Bell Labs is about a thousand miles from the mighty Mississippi, we are only a couple of miles from the usually peaceful Passaic River. After a particularly heavy week of rains, the June 10, 1992, edition of the Star-Ledger quoted an engineer as saying that ``the river was traveling about 200 miles per hour, about five times faster than average''. Any comments?

2. At what distances can a courier on a bicycle with removable media be a more rapid carrier of information than a high-speed data line?

3. How long would it take you to fill a floppy disk by typing?

4. Suppose the world is slowed down by a factor of a million. How long does it take for your computer to execute an instruction? Your disk to rotate once? Your disk arm to seek across the disk? You to type your name?

5. Prove why ``casting out nines'' correctly tests addition. How can you further test the Rule of 72? What can you prove about it?

6. A United Nations estimate put the 1998 world population at 5.9 billion and the annual growth rate at 1.33 percent. Were this rate to continue, what would the population be in 2050?

7. Appendix 3 describes programs to produce models of the time and space costs of your system. After reading about the models, write down your guesses for the costs on your system. Retrieve the programs from the book's web site, run them on your system, and compare those estimates to your guesses.

8. Use quick calculations to estimate the run time of designs sketched in this book.

a. Evaluate programs and designs for their time and space requirements.
b. Big-oh arithmetic can be viewed as a formalization of quick calculations -- it captures the growth rate but ignores constant factors. Use the big-oh run times of the algorithms in Columns 6, 8, 11, 12, 13, 14 and 15 to estimate the run time of their implementation as programs. Compare your estimates to the experiments reported in the columns.

9. Suppose that a system makes 100 disk accesses to process a transaction (although some systems need fewer, some systems require several hundred disk accesses per transaction). How many transactions per hour per disk can the system handle?

10. Estimate your city's death rate, measured in percent of population per year.

11. [P. J. Denning] Sketch a proof of Little's Law.

12. You read in a newspaper article that a United States quarter-dollar coin has ``an average life of 30 years''. How can you check that claim?

Next: Section 7.7. Further Reading.

Copyright © 1999 Lucent Technologies. All rights reserved. Mon 9 Aug 1999