|
|
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 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)
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_0()$ 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 66, line 5
- change 'and from' to 'where $p_j=p_0(j)$, and from'
- *page 66, line 5 from the bottom
- change 'constant' to 'constant, and if all costs $c(x_1,\ldots,x_k)$ are nonnegative'
- 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 "23–28" to "23–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 82, line 4 from the bottom
- change 'was with Algorithm A' to 'was for Algorithm A to search'
- page 117, line 22
- change '[18, Section 4]' to '[18, Section 5-12]'
- page 122, line 14
- change $p_i$ to $p_1$
- page 142, in reference [5]
- change 'Datastrakturer' to 'Datastrukturer'
- page 143, in reference [16]
- change '355' to '335' and '109–133' to '39–70'
- page 143, in reference [23]
- change '51' to '41' and '(1989)' to '(1988)'
- page 147, line 5
- change 'Don Beal and Martin C. Smith' to 'Don F. Beal and Michael C. Smith'
- page 180, in reference [5]
- change 'Mathematische Werke und Wissenschaftlicher Nachlass' to 'mathematische Werke und wissenschaftlicher Nachlass'
- page 166, line 3
- change $a_1,a_2$ to $a_0,a_1$
- *page 202, in reference [1]
- change 'Eudoxus Studien, I' to 'Euxodos-Studien I. Eine voreudoxische Proportionenlehre und ihre Spuren bei Aristoteles und Euklid'
- 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 336, line 18 from the bottom
- change 'но' to 'на'
- 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 504, in reference [6]
- change 'deutschen Mathematiker-Vereinigung' to 'Deutschen Mathematiker-Vereinigung'
- page 528, in reference [3]
- change 'Senol Tuku' to 'Senol Utku'
- page 603, line 7
- change 'cofficients' to 'coefficients'
- page 603, line 21
- change 'Universitata' to 'Universiteta'
- page 605, left column, new entry
- $\varphi(n)$ (totient function), 79, 198, 339.
- page 605, right column, ALGOL language entry
- add pages 61 and 108
- page 606, left column
- change 'Assman' to 'Assmann'
- 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, Brudno entry
- change 'Aleksandr' to 'Alexander'
- page 607, left column
- Bush, Laurens Earle, 121, 17.
- page 607, colored cubes entry
- change "56–59, 65–66" to "56–60, 65"
- page 607, right column, ceiling entry
- add pages 176–177
- page 607, right column, Chebyshev entry
- change 'шев' to 'шёв'
- page 608, left column, computer science entry
- add pages 19 and 149
- page 609, left column
- change 'Jon' to 'John Comstock'
- page 609, right column, Euler entry
- spell his Cyrillic name as in TAOCP
- page 609, right column, exposition entry
- add page 118
- page 610, left column, Feller entry
- change 'Willibald' to 'Vilibald'; add middle name 'Sre\'cko'
- page 610, right column, gcd entry
- add page 189
- page 610, right column entries for Fuller, Gaschnig, Gillogly
- add page 130
- page 611, left column, global analysis entry
- change "28" to "28–29"
- page 611, right column, replacement for Hung entry
- Hung, see Le Tu.
- page 613, left column, Lawler entry
- add page 74
- page 613, right column, new entry
- Le Tu, Quoc Hung, 531.
- page 614, left column
- change 'MacLeod' to 'Macleod'
- page 615, one-way 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 619, left column, Smith entry
- change 'Smith, Martin Charles' to 'Smith, Michael C.'
- page 619, right column, Stirling entry
- change 'subset numbers' to 'partition numbers'
- page 620, right column
- change 'Tuku, Senol, 528.' to 'Utku, Senol, 528.' and move it to the left column of page 621
- page 621, left column, Vitányi entry
- change "Paul Michaèl" to "Pál Mihály (= Paul Michael)"
- page 621, right column, Wiedijk entry
- change 'Frederik' to 'Frederik [= Freek]'
- page 621, right column, Wood entry
- add page 74
- page 622, left column, in the entry for Andrew Yao
- change '180, 195, 341–342' to '175, 180, 195, 341–342, 364'
I hope the book is otherwise error-free; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 1B, Stanford University, Stanford, CA 94305-9015 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 KNUTH-BUG 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 brand-X operating systems for all values of X.
Don Knuth's home page
Don Knuth's other books