|
|
This is the seventh 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 fourth was Selected Papers on Analysis of Algorithms; the fifth was Selected Papers on Computer Languages; the sixth was Selected Papers on Discrete Mathematics.) The Design of Algorithms volume is characterized by the following remarks quoted from its preface.
Algorithms are the threads that tie together most of the subfields of computer science. This book is a collection of technical papers in which I've tried to introduce or make improvements to algorithms for a wide variety of intriguing tasks that have come to my attention during the past fifty years. I'm grateful for this opportunity to put the materials into a consistent format, and to correct errors in the original publications that have come to my attention. If any of this work deserves to be remembered, it is now in the form that I most wish people to remember it.
Something magically beautiful happens when a sequence of commands and decisions is able to marshal a collection of data into organized patterns or to discover hidden structure. Every once in awhile something “clicks”; an elegant procedure suddenly emerges by which small steps combine to fulfill a large objective---aha! On several occasions I've been lucky enough to encounter some of these unexpected nuggets of algorithmic paydirt, and I hope that I can communicate the essence of what makes them tick so that readers will be able to share my pleasure.
Since many different kinds of algorithms are considered here, I've organized this book by topic instead of by chronology. I doubt if anybody will actually read this book straight through from Chapter 1 to Chapter 28; yet I've tried to arrange the chapters so that such a journey will not seem like a completely random walk. Algorithms that deal with similar topics or use similar paradigms are therefore grouped together.
Chapter 1, however, is not about any particular algorithm. It is a eulogy to Bob Floyd, my long-time colleague to whom this book is dedicated, because he helped significantly to inspire so many of the ideas that are described in the other chapters. I know of no better way to begin a book about the design of algorithms than to describe Floyd’s life and work.
... And then the preface continues by describing the other chapters, which can be summarized more succinctly by quoting from the hype on the back cover:
Nearly thirty of Knuth’s classic papers on the subject are collected in this book, brought up to date with extensive revisions and notes on subsequent developments. Many of these algorithms have seen wide use --- for example, Knuth’s algorithm for optimum search trees, the Faller--Gallager--Knuth algorithm for adaptive Huffman coding, the Knuth--Morris--Pratt algorithm for pattern matching, the Dijkstra--Knuth algorithm for optimum expressions, and the Knuth--Bendix algorithm for deducing the consequences of axioms. Others are pedagogically important, helping students to learn how to design new algorithms for new tasks. One or two are significant historically, as they show how things were done in computing’s early days. All are found here, together with more than 40 newly created illustrations.
Here’s the table of contents:
(Numbers like P85 and Q17 in this list refer to the corresponding papers in my list of publications.)
Selected Papers on Design of Algorithms bears Knuth’s usual eloquence in writing. The algorithms and proofs in each chapter are presented cleanly, and pseudocode for implementing them accompanies most of the algorithms. Part of the real charm of this collection comes from the historical notes interspersed throughout the book. These take the form of either additional commentary attached to the end of a paper ... explaining which open problems have been solved, which haven't, and how the newer results were obtained ... Gems like these are probably the best reason to own the book.
-- Daniel Apon, in SIGACT News (June 2014)
This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).
As usual, I promise to deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect.
Here is a list of all nits that have been picked so far in the first printing (2010); an asterisk (*) marks technical errors that are not merely typographical:
- page xiv, line 8 from the bottom (05 February 2011)
- change "Edsger" to "Edsger W."
- page 14, line 6 (01 June 2010)
- change "Catholic University" to "Pontifical Catholic University"
- page 23, line 14 from the bottom (30 May 2017)
- change "an n-element" to "an optimum n-element"
- page 23, line 12 from the bottom (30 May 2017)
- change "n sorting" to "n optimum sorting"
- page 25, line 14 (30 May 2017)
- change "large" to "large while $x_1$, \dots, $x_{2n}$ are very small"
- *page 26, line 12 (30 May 2017)
- change $\alpha'=\alpha$ to $\alpha'=(12)\alpha$
- page 37, bottom line (30 May 2017)
- change "frequencies times the level" to "the frequencies times the levels"
- page 71, lines 5 and 6 (30 April 2010)
- "A. V. Anisimov ... Programmirovanie" should be in a slanted Cyrillic font
- *page 76, line 18 (23 March 2013)
- change "$(a_j,a_n)\in\Omega$ for $j\le k<n$" to "$(a_i,a_n)\in\Omega$ for $j\le i<n$"$
- *page 76, line 18 (30 May 2017)
- change "$a_k\ge a_n$" to "either $a_k>a_n$ or $k=n$"
- page 77, line 19 (30 April 2010)
- change "by the" to "be the"
- page 133, lines 18 and 19 (30 April 2010)
- "Trudy ... Steklova" should be in a slanted Cyrillic font
- *page 136, new paragraph (27 June 2012)
- I learned in 2012 that Yuri Matiyasevich had anticipated the linear-time pattern matching and pattern preprocessing algorithms of this paper, in the special case of a binary alphabet, already in 1969. He presented them as constructions for a Turing machine with a two-dimensional working memory in the paper “Real-time recognition of the inclusion relation,” Journal of Soviet Mathematics 1 (1973), 64--70, which is a translation of his original Russian article in Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta imeni V. A. Steklova 20 (1971), 104--114.
- page 154, line 5 (30 April 2010)
- "Doklady ... SSSR" should be in a slanted Cyrillic font
- page 164, line 9 from the bottom (19 February 2010)
- "Jon L. White" should be "Jon L White"
- page 168, lines 4 and 3 from the bottom (10 March 2018)
- change "it replaces $(A$ ... $B)$;" to "it sets $A\gets b_1$, $b_1\gets b_2$, \dots, $b_{r-1}\gets b_r$, $r\gets r-1$; operation B1 either does nothing or sets $r\gets r+1$, $b_r\gets B$;
- page 209, bottom line (21 May 2018)
- change "real constant" to "real constant or $+\infty$"
- page 210, line 17 (21 May 2018)
- change "nonnegative real" to "extended real"
- page 233, line 11 (15 October 2010)
- change '1993' to '1994'
- *page 234, replacement for the final paragraph (30 April 2017)
- An interesting counterexample to József Beck’s conjecture about 3-way rounding was found by Alantha Newman, Ofer Neiman, and Aleksandar Nikolov, “Beck’s three permutations conjecture: A counterexample and some consequences,” IEEE Symposium on Foundations of Computer Science 53 (2012), 253–262. They proved that the three permutations on $\{0,1,\ldots,3^k-1\}$ defined by $$ (a_1\ldots a_k)_3 \mapsto \bigl( ((a_1+j)\bmod3) \ldots ((a_k+j)\bmod3)\bigr)_3 $$ for $j\in\{0,1,2\}$ have discrepancy at least $k/3+1$.
- page 236, lines 22 and 23 (21 May 2018)
- change “point x ... with color 3.” to: “x could be painted with the current color of y, and y could be repainted with the current color of z, and z could be repainted with the color 3.”
- page 272, line 18 (15 October 2010)
- change '1993' to '1994'
- page 312, line 14 from the bottom (01 July 2010)
- change "know now" to "know how"
- page 340, line 14 from the bottom (01 July 2010)
- change "sérié" to "série"
- page 429, line 26 (06 March 2011)
- change "lines 18--23" to "lines 16--23"
- page 433, reference [5] (06 March 2011)
- change "Program optimizing" to "Optimum programming"
- page 433, reference [9] (06 March 2011)
- change "subroutines" to "sub-routines", and "1954)" to "1954), 5--43"
- page 433, reference [10] (06 March 2011)
- change "35 pages" to "63+xxi pages"
- *page 436, replacement for the three lines preceding the final paragraph (01 August 2010)
- Egon Balas, Matteo Fischetti, and Arrigo Zanette [“A hard integer program made easy by lexicography,” Mathematical Programming A135 (2012), 509--514] have used dramatically improved integer programming techniques to show that the optimum cost remains 22996 when this correction is made.
- page 436, amendments to the final paragraph (09 March 2011)
- Change "The floating-point ... A brief" to "See George R. Trimble, Jr., “A brief"; and change "page 49." to "page 49, for his account of the hand-optimized programs in [9] that inspired those of [10]."
- page 438, left column, new entry (01 August 2010)
- Balas, Egon, 436.
- page 439, left column
- change 'Burnside, William Snow, groups' to 'Burnside, William, groups'
- page 441, right column, new entry (01 August 2010)
- Fischetti, Matteo, 436.
- page 442, right column (01 June 2010)
- change "Gomez-Perez" to "Gómez-Pérez"
- page 443, left column, new entry (21 Feb 2011)
- Hanani, Haim, 243.
- page 446, left column, Matiyasevich entry (27 June 2012)
- add page 136.
- page 447, left column, new entry (30 April 2017)
- Neiman, Ofer, 234.
- page 447, left column, new entry (30 April 2017)
- Newman, Alantha, 234.
- page 447, left column, new entry (30 April 2017)
- Nikolov, Alexandar, 234.
- page 449, left column (16 November 2010)
- change "Mnysarchos" to "Mnesarchos"
- page 450, left column, new entry (21 February 2011)
- Sauer, Norbert Werner, 243.
- page 450, left column, new entry (21 February 2011)
- Schönheim, Johanan, 243.
- page 452, left column (27 June 2012)
- Turing, Alan, machines, 133, 136.
- page 452, right column (19 February 2011)
- change "White, Jon L" to "White, Jon L (= Lyle)"
- page 453, left column, new entry (01 August 2010)
- Zanette, Arrigo, 436.
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