
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:
(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 fansin 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 shortshrift 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 (averagecase) analysis of algorithms by the pen of its creator.
Joachim von zur Gathen, in IEEE Annals of the History of Computing (AprilJune 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 wholeheartedly 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)
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 "Zetafunction" 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 "intermediatewalks" to "intermediatelength 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 (20face 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
 Addendum
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
 add page 120
 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
 add page 189
 page 611, left column, global analysis entry
 change "28" to "28–29"
 page 613, left column, Lawler entry
 add page 74
 page 614, left column
 change 'MacLeod' to 'Macleod'
 page 615, oneway equalities entry
 add page 39
 page 616, left column, partial quotients entry
 add pages 29–32
 page 616, right column, in the entry for Nicholas John Pippenger
 change '501' to '472, 501'
 page 617, left column, pushdown automata entry
 add page 23
 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
 add page 74
I hope the book is otherwise errorfree; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to knuthbug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 943059045 USA. In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.
I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.
DO NOT SEND EMAIL TO KNUTHBUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brandX operating systems for all values of X.