Donald E. Knuth

Donald Knuth's influence in computer science ranges from the
invention of methods for translating and defining programming
languages to the creation of the TEX and METAFONT systems for
desktop publishing. His award-winning textbooks have become classics
that are often credited for shaping the field; his scientific papers
are widely referenced and stand as milestones of development over a
wide range of topics. The present volume, which is the fourth in a
series of his collected works, is devoted to an important subfield
of Computer Science that Knuth founded in the 1960s and still
considers his main life's work. This field, to which he gave the
name Analysis of Algorithms, deals with quantitative studies of
computer techniques, leading to methods for understanding and
predicting the efficiency of computer programs. Analysis of
Algorithms, which has grown to be a thriving international
discipline, is the unifying theme underlying Knuth's well known
books *The Art of Computer Programming*. More than 30 of the
fundamental papers that helped to shape this field are reprinted and
updated in the present collection, together with historical material
that has not previously been published. Although many ideas come and
go in the rapidly changing world of computer science, the basic
concepts and techniques of algorithmic analysis will remain
important as long as computers are used.

6/1/2000

- 1. Mathematical Analysis of Algorithms 1
- 2. The Dangers of Computer Science Theory 19
- 3. The Analysis of Algorithms 27
- 4. Big Omicron and Big Omega and Big Theta 35
- 5. Optimal Measurement Points for Program Frequency Counts 43
- 6. Estimating the Efficiency of Backtrack Programs 55
- 7. Ordered Hash Tables 77
- 8. Activity in an Interleaved Memory 101
- 9. An Analysis of Alpha-Beta Pruning 105
- 10. Notes on Generalized Dedekind Sums 149
- 11. The Distribution of Continued Fraction Approximations 181
- 12. Evaluation of Porter's Constant 189
- 13. The Subtractive Algorithm for Greatest Common Divisors 195
- 14. Length of Strings for a Merge Sort 205
- 15. The Average Height of Planted Plane Trees 215
- 16. The Toilet Paper Problem 225
- 17. An Analysis of Optimum Caching 235
- 18. A Trivial Algorithm Whose Analysis Isn't 257
- 19. Deletions That Preserve Randomness 283
- 20. Analysis of a Simple Factorization Algorithm 303
- 21. The Expected Linearity of a Simple Equivalence Algorithm 341
- 22. Textbook Examples of Recursion 391
- 23. An Exact Analysis of Stable Allocation 415
- 24. Stable Husbands 429
- 25. Shellsort With Three Increments 447
- 26. The Average Time for Carry Propagation 467
- 27. Linear Probing and Graphs 473
- 28. A Terminological Proposal 485
- 29. Postscript About NP-hard Problems 493
- 30. An Experiment in Optimal Sorting 495
- 31. Duality in Addition Chains 501
- 32. Complexity Results for Bandwidth Minimization 505
- 33. The Problem of Compatible Representatives 535
- 34. The Complexity of Nonuniform Random Number Generation 545
- Index 605