|
|
This is the seventh in aseries of eight volumesthat contain archival forms of my published papers,together with new material. (The first book in the series wasLiterate Programming;the second wasSelected Papers on Computer Science;the third wasDigital Typography;the fourth wasSelected Papers on Analysis of Algorithms;the fifth wasSelected Papers on Computer Languages;the sixth wasSelected Papers on Discrete Mathematics.)The Design of Algorithms volume is characterized by the followingremarks quoted from its preface.
Algorithms are the threads that tie together most of the subfieldsof computer science. This book is a collection of technical papers inwhich I've tried to introduce or make improvements to algorithms for awide variety of intriguing tasks that have come to my attention during thepast fifty years.I'm grateful for this opportunity to put thematerials into a consistent format, and to correct errors in the originalpublications that have come to my attention. If any of this work deserves tobe remembered, it is now in the form that I most wish people to remember it.
Something magically beautiful happens when a sequence of commands anddecisions is able to marshal a collection of data into organized patternsor to discover hidden structure. Every once in awhile something “clicks”;an elegant procedure suddenly emerges by which small steps combine to fulfilla large objective---aha! On several occasions I've been lucky enough to encounter some ofthese unexpected nuggets of algorithmic paydirt, and I hope that I cancommunicate the essence of what makes them tick so that readers will be ableto share my pleasure.
Since many different kinds of algorithms are considered here, I've organizedthis book by topic instead of by chronology. I doubt if anybody will actuallyread this book straight through from Chapter 1 to Chapter 28; yet I've triedto arrange the chapters so that such a journey will not seem like a completelyrandom walk. Algorithms that deal with similar topics or use similar paradigmsare therefore grouped together.
Chapter 1, however, is not about any particular algorithm. It is a eulogy toBob Floyd, my long-time colleague to whom this book is dedicated, because hehelped significantly to inspire so many of the ideas that are described inthe other chapters. I know of no better way to begin a book about the design of algorithmsthan 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 onthe back cover:
Nearly thirty of Knuth’s classic papers on the subject are collected in thisbook, brought up to date with extensive revisions and notes on subsequentdevelopments. Many of these algorithms have seen wide use --- for example, Knuth’salgorithm for optimum search trees, the Faller--Gallager--Knuth algorithmfor adaptive Huffman coding, the Knuth--Morris--Pratt algorithm forpattern matching, the Dijkstra--Knuth algorithm for optimum expressions,and the Knuth--Bendix algorithm for deducing theconsequences of axioms. Others are pedagogically important, helpingstudents to learn how to design new algorithms for new tasks.One or two are significant historically, as they show how thingswere done in computing’s early days. All are found here, together withmore 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 mylist of publications.)
Selected Papers on Design of Algorithms bears Knuth’s usualeloquence in writing. The algorithms and proofs in each chapter are presentedcleanly, and pseudocode for implementing them accompanies most of thealgorithms. Part of the realcharm of this collection comes from thehistorical notes interspersed throughout the book. These take the form ofeither additional commentary attached to the end of a paper ... explainingwhich open problems have been solved, which haven't, and how the newer resultswere obtained ... Gems like these are probably the best reason to own the book.
-- Daniel Apon, inSIGACT 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 deposit0x$1.00 ($2.56)to the account of the first personwho 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 firstprinting (2010); an asterisk (*) marks technical errors that are notmerely 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 "ann-element" to "an optimumn-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-timepattern matching and pattern preprocessing algorithms of this paper, in thespecial case of a binary alphabet, already in 1969. He presented them asconstructions for a Turing machine with a two-dimensional working memory inthe paper “Real-time recognition of the inclusion relation,”Journalof Soviet Mathematics1 (1973),64--70, which is a translation of his original Russian article inZapiski Nauchnykh Seminarov Leningradskogo OtdeleniyaMatematicheskogo Instituta imeni V. A. Steklova20 (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 216, reference [7] (28 December 2023)
- "Advance Papers … Intelligence" should beslanted
- 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 conjectureabout 3-way rounding was found by Alantha Newman, Ofer Neiman, andAleksandar Nikolov, “Beck’s three permutations conjecture:A counterexample and some consequences,”IEEE Symposium on Foundations of Computer Science53 (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 “pointx ... with color 3.” to:“x could be painted with the current color ofy, andy could be repainted with the current color ofz, andz 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 380, reference [4] (28 December 2023)
- change "(1870)" to "(1871)"
- 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 integerprogram made easy by lexicography,”Mathematical ProgrammingA135 (2012), 509--514] have used dramaticallyimproved integer programming techniques to show that the optimum cost remains22996 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 thehand-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 447, right column, Ostrowski entry (14 Sep 2024)
- change "Markus" to "Markowich"
- 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) itprobably isn't, because each page presented me with hundreds of opportunitiesto make mistakes. Please send suggested corrections toknuth-bug@cs.stanford.edu, or send snail mail toProf. D. Knuth, Computer Science Department, CoDa Building room W208,Stanford University, Stanford, CA 94305-5008 USA.In either case please include your postal address, so that I canmail an official certificate of deposit as a token of thanks for anyimprovements to which you have contributed.
I may not be able toread your message until many months have gone by, because I'm workingintensively onThe 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, pleasedo notinclude attachments of any kind; your message should bereadable on brand-X operating systems for all values of X.
Don Knuth’s home pageDon Knuth’s other books