y Knuth: Selected Papers on Analysis of Algorithms

# Selected Papers on Analysis of Algorithms

by Donald E. Knuth (Stanford, California: Center for the Study of Language and Information, 2000), xvi+621 pp.
(CSLI Lecture Notes, no. 102.)
ISBN 1-57586-212-3
Printings made after 2006 have xvi+622 pp., because the index has gotten longer.

This is the fourth in a series of eight volumes that contain archival forms of my published papers, together with new material. (The first book in the series was Literate Programming; the second was Selected Papers on Computer Science; the third was Digital Typography.) The Analysis of Algorithms volume is characterized by the following remarks quoted from its preface.

People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.''
I once had the pleasure of writing those words for the Foreword of An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet, and I can't think of any better way to introduce the present book. After enjoying such double happiness for nearly forty years, I'm delighted that I can finally bring together this collection of essays about the subject that I love most.
... Most of the chapters in this book appeared originally as research papers that solved basic problems related to some particular algorithm or class of algorithms. But the emphasis throughout is on techniques that are of general interest, techniques that should lead also to the solution of tomorrow's problems. The way a problem is solved is generally much more important than the solution itself, and I have therefore tried to explain the principles of solution and discovery as well as I could. Thus I believe the material in this book remains highly relevant even though much of it was written many years ago. I have also appended additional material to most of the chapters, explaining subsequent developments and giving pointers to more recent literature.
... The process of compiling this book has given me an incentive to improve some of the original wording, to make all of the notations consistent with The Art of Computer Programming, to doublecheck almost all of the mathematical formulas and the reasoning that supports them, to correct all known errors, to improve the original illustrations by redrawing them with MetaPost, and to match the bibliographic information with original sources in the library. Thus the articles now appear in a form that I hope will remain useful for at least another generation or two of scholars who will carry the work forward.

This book isn't exactly Analysis of Algorithms for Dummies,'' but it does contain expositions of nearly every important aspect of the subject. It has the following chapters:

1. Mathematical Analysis of Algorithms [P46]
2. The Dangers of Computer Science Theory [P56]
3. The Analysis of Algorithms [P44]
4. Big Omicron and Big Omega and Big Theta [Q43]
5. Optimal Measurement Points for Program Frequency Counts [P60]
6. Estimating the Efficiency of Backtrack Programs [P69]
7. Ordered Hash Tables [P64]
8. Activity in an Interleaved Memory [P74]
9. An Analysis of Alpha-Beta Pruning [P70]
10. Notes on Generalized Dedekind Sums [P75]
11. The Distribution of Continued Fraction Approximations [P106]
12. Evaluation of Porter's Constant [P86]
13. Analysis of the Subtractive Algorithm for Greatest Common Divisors [P76]
14. Length of Strings for a Merge Sort [P12]
15. The Average Height of Planted Plane Trees [P51]
16. The Toilet Paper Problem [P111]
17. An Analysis of Optimum Caching [P104]
18. A Trivial Algorithm Whose Analysis Isn't [P84]
19. Deletions That Preserve Randomness [P89]
20. Analysis of a Simple Factorization Algorithm [P78]
21. The Expected Linearity of a Simple Equivalence Algorithm [P88]
22. Textbook Examples of Recursion [P135]
23. An Exact Analysis of Stable Allocation [P149]
24. Stable Husbands [P127]
25. Shellsort With Three Increments [P157]
26. The Average Time for Carry Propagation [P90]
27. Linear Probing and Graphs [P158]
28. A Terminological Proposal [Q33]
29. Postscript About NP-hard Problems [Q36]
30. An Experiment in Optimal Sorting [P52]
31. Duality in Addition Chains [Q58]
32. Complexity Results for Bandwidth Minimization [P77]
33. The Problem of Compatible Representatives [P132]
34. The Complexity of Nonuniform Random Number Generation [P80]

(Numbers like P158 and Q33 in this list refer to the corresponding papers in my list of publications.)

This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).

The papers in this book are a collection of gems that were previously published or presented as lectures by the author. The very title bears Knuth's signature, since it was he who introduced the phrase analysis of algorithms.'' ... He presents new pure'' results, which is surprising in view of the age of the topics. Generally, nobody will have the last word, as most of the papers include a sizable supplement discussing more recent developments. ... This collection will be highly prized by Knuth fans---in fact, by all computer scientists.
--Harvey Cohn, in Computing Reviews (July 2000)
The range of topics, although mostly confined to the analysis of algorithms, is vast. ... To focus on any one aspect ... would give short-shrift to the others. I therefore decided to focus this review on why I believe every reader of SIGACT News should buy this book. ... The evolution of current technology and fundamental unifying ideas can be found ... excellent reading for a beginning student in algorithm analysis ... many hilarious misapplications of theory to practice ... Knuth does an amazing job of relating how he approaches problems rather than merely recording a highly polished solution which to the reader seems to come out of the blue ... It's just plain fun to read.
--Timothy H. McNicholl, in SIGACT News (March 2001)
... combines succinctness and formal rigour with clarity and humour ... These papers on algorithmic analysis exemplify how best to convey the often complex mathematics lying behind the behaviour of apparently simple techniques. ... this collection will be of interest to those who value the highest quality technical writing, as well as to algorithm analyzers.
--Greg Michaelson, in The Computer Bulletin (May 2001)
... In summary, the papers collected here give a beautiful picture of charms and challenges of the (average-case) analysis of algorithms by the pen of its creator.
--Joachim von zur Gathen, in IEEE Annals of the History of Computing (April--June 2002)
... The particular value of this book is that much of the material has appeared in publications which are available only with difficulty. The collection is a valuable addition to the literature.
--A. D. Booth, in Mathematical Reviews (2001)
... thoughtful, thorough, and inspiring. ... Most of these papers, although excellent in every sense of this word, are quite technical, and I certainly don't recommend them for easy reading.'' ... I would whole-heartedly recommend this book to my colleagues who have some time to spare, and who would like to get into one of the greatest minds in computer science.
--Zhizhang Shen, in Zentralblatt Math (March 2001)

## Errata

As usual, I promise to pay a reward of $2.56 to the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. The printing of 2012 corrected all of the previously known errors in the original printing of 2000 and errors in the printing of 2008; the following further corrections are still needed. An asterisk (*) marks technical errors that are not merely typographical: page 2, line 17 from the bottom change 'fewer than 9' to 'fewer than 7' page 4, line 14 change 'MacLeod" to "Macleod" page 4, line 2 from the bottom change '9 statements' to '8 statements', and '12 separate' to '11 separate' page 5, line 3 change '12 individual' to '11 individual' page 8, line 4 from the bottom put bars on B, C, D, E, F page 10, line 13 change 'MacLeod' to 'Macleod' page 10, line 3 from the bottom change 'MacLeod' to 'Macleod' page 18, in reference [16] change 'MacLeod' to 'Macleod' page 25, line 1 of reference [1] change алгорифм to алгоритм *page 29, line 3 change$t\le y$to$t<y$,$t'<y$*page 29, line 4 change$\sigma_{-1}(n)^2$to$(\log\log n)^4$page 31, line$-9$change$>{1\over\theta''-\theta'}$to$\ge{1\over\theta''-\theta'}$page 40, in reference [5] change "zeta function" to "Zeta-function" and 1918 to 1917 page 53, in reference [5] change "S. J." to "Samuel J." and "4" to "41" page 59, line 17 *change "such that" to "such that$P_()$is true and *page 64, line 5 from the bottom change 'nonnegative' to 'positive' *page 65, line 11 change 'perfect:' to 'perfect, if we assume that all costs at terminal nodes are positive:' page 73, in ref [4] change "Chess Pie III ... tournament" to "Chess Pie No. 3: The Official Souvenir of the International Tournament" page 73, in ref [5] change "intermediate-walks" to "intermediate-length walks" page 73, in ref [10] change "22–28" to "22–38" page 74, in ref [15] change "(1959)" to "(1957)" page 74, in ref [19] change "O'Bierne" to "O'Beirne" page 74, in ref [20] change "generating dice" to "generating icosahedral dice (20-face dice)" page 166, line 3 change$a_1,a_2$to$a_0,a_1$page 223, in reference [4] change 'eventails' to 'éventails' page 233, in reference [1] change 'considerations geometriques' to 'considérations géométriques' page 233, in reference [4] change "l'interpretation geometrique" to "l'interprétation géométrique" *page 258, line 26 change [1, page 5] to [1, Theorem 2] page 296, line 3 from the bottom change 'be very strong' to 'be a very strong' page 419, line 2 from the bottom change$\sigma(\pi(1)),\ldots,\sigma(\pi(m))$to$\sigma(\pi(1))\ldots\sigma(\pi(m))$page 442, line 12 from the bottom change$(1+\epsilon)\ln n$to$(1+\epsilon)\ln m\$
page 472, new copy
Nicholas Pippenger [“Analysis of carry propagation in addition: An elementary approach,” Journal of Algorithms 42 (2002), 317–333] has explained how to obtain these results without using contour integration.
page 603, line 7
change 'cofficients' to 'coefficients'
page 605, right column, ALGOL language entry
add pages 61 and 108
page 606, left column
automata, 2, 15–16, 20–23, 29, 491, 586–587, 599–601, 603.
page 606, right column
Betz, Bernard Keith, 21, 25.
page 607, left column, branching process entry
page 607, left column
Bush, Laurens Earle, 121, 17.
page 607, colored cubes entry
change "56–59, 65–66" to "56–60, 65"
page 608, left column, computer science entry
add pages 19 and 149
page 609, Euler entry
spell his Cyrillic name as in TAOCP
page 610, right column, gcd entry
page 611, left column, global analysis entry
change "28" to "28–29"
page 613, left column, Lawler entry
page 614, left column
change 'MacLeod' to 'Macleod'
page 615, one-way equalities entry
page 616, left column, partial quotients entry
page 616, right column, in the entry for Nicholas John Pippenger
change '501' to '472, 501'
page 617, left column, pushdown automata entry
page 618, left column
change 'Rice, Stephan' to 'Rice, Stephen'
page 618, left column, Schreier entry
change "Jozef" to "Józef"
page 618, right column
change 'Simon, Istvan Gusztav" to 'Simon, Istv´n Guszt´v'
page 621, left column, Vitányi entry
change "Paul Michaèl" to "Pál Mihály (= Paul Michael)"
page 621, right column, Wood entry