|
|
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 2008 corrected all of the previously known errors in the original printing of 2000; the following further corrections are still needed. An asterisk (*) marks technical errors that are not merely typographical:
- page 7, line 8 from the bottom
- change '$\overline y_{ij}$' to '$y_{ij}$'
- page 7, line 5 from the bottom
- change '$\overline a$' to '$a$'
- page 8, lines 5 and 6
- change '$B$' to '$\overline B$', '$C$' to '$\overline C$', '$D$' to '$\overline D$', '$E$' to '$\overline E$', and '$F$' to '$\overline F$'
- page 8, line 2 from the bottom
- change '$A$' to '$\overline A$'
- *page 16, lines 16 and 17
- change '$k\ne l$' to '$l\ne j$' and '$k=l$' to '$l=j$'
- page 30, line 4
- change 'the set of all' to 'the sum of all'
- page 31, line 6 from the bottom
- change '$K_{t-s-3}(A_{s+4},\ldots,A_t)$' to $K_{t-s-3}(A_{s+4},\ldots,A_t)D$'
- page 49, line 6
- change 'some vertex' to 'some arc'
- page 73, line 13
- change 'Echecs Feeriques' to 'Échecs féeriques'
- page 106, lines 24 and 25
- change 'the ``best'' move' to 'a ``best'' move' and 'that the best' to 'that a best'
- *page 134, in (42)
- change '$1\le k\le$' to '$1\le k<$' (twice)
- *page 155, bottom line
- change '$\sum_{j=0}^{r-1}$' to '$\sum_{j=0}^r$'
- *page 156, line 5
- change '$r<s$' to '$s<r$'
- page 161, line 16 from bottom
- change '$C_3\ge$' to '$C_3\le$'
- *page 163, line 1
- change 'If $A_j=2$ for any $j$' to 'If $A_{j-1}=2$ for some $j$
- *page 173, line 8
- change '$+m_{j-1}$' to '$+m_{j+1}$' and '$+m_{j+2}$' to '$-m_{j+2}$'
- page 227, line 20
- change "idea [1]" to "idea (see [1] and [4])"
- page 233, replacement for reference [1]
- [1] J. Aebly, ``Démonstration du problème du scrutin par des considerations geometriques,'' L'Enseignement Mathématique 23 (1923), 185--186.
- page 233, move reference [4] to [5] and insert a new reference [4]
- [4] D. Mirimanoff, ``A propos de l'interpretation geometrique du problème du scrutin,'' L'Enseignement Mathématique 23 (1923), 187--189.
- *page 237, line 11 from the bottom
- change '$\rho_2=(0\ 3\ 2)$' to '$\rho_2=(0\ 1\ 3)$'
- *page 238, lines 15 and 17
- change '$m_t$' to '$m_{t-1}$' (four changes)
- *page 244, line 2 from the bottom
- change '$d^{h-k+1}$' to '$d^{h-1+k}$'
- page 246, line 8 from the bottom
- change '$P_{hd}(k)$' to '$p_{hd}(k)$'
- page 272, line 4 from the bottom
- change '$dt$' to '$dt\,dx\,dy$' (two changes)
- page 286, line 14
- change '$y'_{n-1+m}$' to '$y'_{n-1-m}$'
- page 293, line 17
- change '$I^*DI_o^*$' to '$I_o^*DI_o^*$'
- *page 310, line 12
- change '$\int_1^{x^{\alpha-1}}$' to '$x^\alpha \int_1^{x^{\alpha-1}}$'
- *page 310, line 6 from the bottom
- change '$1\over n-1$' to '$1\over n+1$'
- *page 311, line 2 from the bottom
- change '$x^\alpha\int_1^2$' to '$\int_1^2$'
- *page 312, lines 7 and 8
- change '$x^{2/\alpha}\,dt$' to $x^{2\alpha/t}\,dt\over\alpha$' and '$x^{\alpha u}\,du\over u^2$' to '$x^{\alpha u}\,du\over 2\alpha u^2$'
- page 316, line 4 from the bottom
- change '$\rho(t)$' to '$\rho_k(t)$'
- page 344, line 1
- change '$e^t$' to '$e^{-t}$'
- *page 347, bottom line
- change '$\int_0^1\exp(cn^{3/2}t)$' to '$\int_0^t\exp(cn^{3/2}u)$'
- *page 351, line 2 from the bottom
- change '$\exp$' to '$t^{k+m-2}\exp$'
- *page 358, bottom line
- change '${1\over n-c\sqrt k-1}\ldots{1\over n-c\sqrt k-k}$' to '${1\over n-c\sqrt k-1}+\cdots+{1\over n-c\sqrt k-k}$'
- page 398, line 11 from the bottom
- change 'using André's well-' to 'using a well-'
- page 399, line 3 from the bottom
- change 'by André's reflection' to 'by the reflection'
- page 434, line 7
- change '$l,p_1,h$' to '$l,p,h$'
- page 457, line 5 from the bottom
- change '$Q^*_{kl}$' to '$Q^*_l$'
- page 464, line 7 from the bottom
- change 'by (7.6)' to 'by (7.7)'
- page 470, line 7
- change '$2^{-n-1}b$' to '$2^{-n}b$'
- page 485, line 17 from the bottom
- change 'Hamiltonian circuit' to 'Hamiltonian cycle'
- page 500, replacement for the final paragraph
- Marcin Peczarski [``New results in minimum-comparison sorting,'' Algorithmica 40 (2004), 133--145; ``The Ford--Johnson algorithm still unbeaten for less than 47 elements,'' Information Processing Letters 101 (2007), 126--128] has extended Wells's method to prove that merge insertion is actually unbeatable when $n=13$, 14, or 15. The optimum procedure for sorting 16 elements remains unknown.
- page 526, line 3 from the bottom
- put an end-of-proof box after '$\le k$?'
- page 528, in reference [1]
- change 'SIAM Journal of Applied' to 'SIAM Journal on Applied'
- page 537, line 14
- change '$\bigvee_{n\in A_j}$' to '$\bigvee_{a\in A_j}$'
- page 559, line 6 from the bottom
- change 'If $n$ is odd$' to 'If $n>1$ is odd'
- *page 563, lines 8 and 9 following (3.9)
- change '$0<\theta$' to '$0\le\theta$' and '$n>0$' to '$n\ge0$'
- page 568, line 9
- change '$p+(1-p_1)$' to '$p_1+(1-p_1)$'
- page 571, line 19
- change 'know from (1.6)' to 'know from (1.5)'
- page 578, line 8
- change '$\varepsilon_m\bigl(f(x)\bigr)$' to '$\varepsilon_m\bigl(f(x)\bigr)\,dx$'
- page 591, in (7.6)
- change '$(1-t)^b$' to '$(1-t)^b\,dt$'
- page 607, right column
- change "André, Antoine Désiré, 233, 398--399" to "Aebly, Jakob, 233" (and re-alphabetize)
- page 607, right column
- change 'Chvátal, Václav' to 'Chvátal, Václav (= Vašek)'
- page 614, right column, new entry
- Mirimanoff, Dimitry, 233.
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 4B, Stanford University, Stanford, CA 94305-9045 USA. 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