Selected Papers on Computer Science

by Donald E. Knuth (Stanford, California: Center for the Study of Language and Information, 1996), xii+274pp.; xii+276pp. after the second printing.
(CSLI Lecture Notes, no. 59.)
ISBN 1-881526-91-7

This is the second 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 third, Digital Typography.) The Computer Science volume is characterized by the following remarks quoted from its preface.

This book assembles under one roof all of the things I've written about computer science for people who aren't necessarily specialists in the subject---for scientists and mathematicians in general, and for educated people in all fields. 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.
It has the following chapters:
  1. Algorithms, Programs, and Computer Science [Q18, Q126]
  2. Computer Science and its Relation to Mathematics [P63]
  3. Mathematics and Computer Science: Coping with Finiteness [P82]
  4. Algorithms [P79]
  5. Algorithms in Modern Mathematics and Computer Science [P94]
  6. Algorithmic Themes [Q102]
  7. Theory and Practice, I [never before published]
  8. Theory and Practice, II [Q82]
  9. Theory and Practice, III [never before published]
  10. Theory and Practice, IV [P138]
  11. Are Toy Problems Useful? [Q46]
  12. Ancient Babylonian Algorithms [P53]
  13. Von Neumann's First Computer Program [P40]
  14. The IBM 650: An Appreciation from the Field [P112]
  15. Artistic Programming [Q133]
  16. Speech in St. Petersburg [Q140]
  17. George Forsythe and the Development of Computer Science [P54]

(Numbers like P79 and Q82 in this list refer to the corresponding papers in my list of publications. The chapters are numbered from 0 to 16; some buggy browsers unfortunately show them as 1 to 17 in the listing above. In the first two printings, Chapters 14 and 16 were called Chapters 15 and 14, respectively, and the new ``St. Petersburg'' chapter was not included.)

Available from the publisher (CSLI), and also from the distributor (University of Chicago Press).

It is a real pleasure to reread these articles, which are generally as fresh today as when they were first written. The Scientific American article entitled ``Algorithms,'' from 1977, ... is still the best treatment of searching that I have ever read. -- J. Nunemacher, IEEE Annals of the History of Computing, 1998
This is a delightful book. -- R. B. Kellogg, SIAM Review, 1998
Immensely satisfying. -- S. Khuller, SIGACT News, 1998
It is a lovely read ... clear and crisp. -- Adrian Larner, The Computer Journal, 1998
... Covering a period from 1966 to 1993, its interest lies not only in the content of each of these papers --- still timely today --- but also in their being put together so that ideas expressed at different times complement each other nicely. -- N. Bernard, Zentralblatt Math
... This is a fascinating survey of the work of one of the most important computer scientists ever. In particular, his discussion of theory and practice and his view of algorithms and algorithmic research enhance this impressive survey of the development of computer science. His clear and entertaining way of writing makes it a pleasure to read the book. -- F. Meyer auf der Heide, Mathematical Reviews, 1998

Errata to the Third Printing

The third printing (2004) introduced several pages of new material and corrected all of the previously known errors in the first and second printings. The following further corrections are still needed:

page 2, line 17 (01 Mar 2010)
change "trigonometric functions" to "Bernoulli numbers"
page 15, lines 5 and 6 from the bottom (11 Oct 09)
change H to G
page 16, line 5 after the caption to Fig. 1 (27 Mar 10)
change nth to nth
page 28, line 8 (09 Dec 04)
omit ", vol. 2"
page 28, line 3 from the bottom (09 Dec 04)
change "Chapter 14" to "Chapter 16"
page 29, line 18
change "Slaught Memorial Monograph" to "Herbert Ellsworth Slaught Memorial Papers"
page 40, caption to Figure 2
change "grid" to "array of squares"
page 51, lines 9 and 6 from the bottom (28 Feb 06)
change "sets" to "finite sets"
page 51, line 4 from the bottom (28 Feb 06)
change "nonempty" to "finite nonempty"
page 51, bottom two lines (28 Feb 06)
change "would, however, be false, since ... largest element." to "would also be true, since we are dealing only with finite sets."
page 55, line 4 (25 Oct 11)
change "84" to "83"
page 55, line 7 (25 Oct 11)
change "(1962), 73--82" to "(1963), 73--81"
page 72, line 11 from the bottom
change "l, r and j" to "l, r, and j"
page 88, line 9 from the bottom
change "Abu" to "abû"
page 91, line 2
change "abu-aljabr" to "abû al-jabr"
page 102, bottom line
insert the additional factor $\sqrt n$ in the denominator
page 103, line 2
change "$\cos x/\sqrt n$ to $\cos(x/\sqrt n)$
page 106, line 8
change "addition, multiplication, and multiplication by" to "addition and multiplication, together with multiplication by"
page 107, line 6
change $\delta(t)$ to $\delta(\epsilon)$
page 107, line 2 from the bottom (01 Mar 10)
change "assume" to "assume\footnote*{Oops: Patrick Cégielski pointed out in 2009 that this assumption fails; there's no algorithm to decide if, say, $\{y_0,y_1\}$ contains two distinct points, when $y_0$ and $y_1$ are Bishop-style reals. Further correction is necessary.}"
page 108, line 14
change $(\epsilon/(2MB))$ to $(\epsilon/(2MB))(t)$
page 112, bottom line (29 Nov 11)
change Mathematicheskie to Matematicheskie
page 113, first line of reference [18] (29 Nov 11)
change "An" to "an"
page 167, line 2 of reference [3] (29 May 05)
change "September 1985" to "August 1983"
page 187, line 22 (21 Mar 09)
change "85194" to "85200"
page 197, line 13 (05 Mar 10)
change "shows the one-fourth" to "shows one-fourth"
page 210, line 2 from the bottom
change "S" to "S"
page 213, line 14 from the bottom (2 Feb 11)
change "consecutive short tanks" to "consecutive memory locations"
page 215, line 8 from the bottom
page 218, line 17 from the bottom
page 239, reference [14]
change "35 pp." to "63+xxi pp."
page 264, include the following photo of George Forsythe, taken in 1971
page 265, left column, lines 14 and 19
change "abu" to "abû"
page 267, left column, new entry (01 Mar 10)
Cégielski, Patrick, 107.
page 268, Dijkstra entry (28 Mar 05)
change "Wijbe" to "Wybe"
page 269, Greibach entry (14 Oct 09)
change "Shiela" to "Sheila"
page 272, Speroni entry (06 Aug 07)
change "Joseph P." to "Joseph Paul"
page 275, Thureau-Dangin entry (21 Mar 09)
change "François" to "Jean Geneviève François"

Errata to the Fourth Printing (2012)

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 such “issues” that are currently known:

page 35, line 6 (18 May 2017)
change "medium-fast" to "medium-speed"
page 58, line 2 (28 June 2015)
change "an anonymous contributor to Encyclopædia Brittanica" to "Edward Bromhead in Encyclopædia Britannica"
page 58, line 2 (28 June 2015)
change "568--572" to "569--570"
page 145, lines 11 and 12 from the bottom (18 May 2017)
change "governor of Pennsylvania" to "governor of Pennsylvania (actually called “president” in those days)"
page 156, line 14 (18 May 2017)
insert a subscript ‘0’ after the ‘n’
page 207, line 6 from the bottom (18 May 2017)
change 19,000 to 17,000
page 266, new entry (28 June 2015)
Bromhead, Edward Thomas Ffrench, 58.

I hope the book is otherwise error-free, but (sigh) it probably isn't. Please send suggested corrections to, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 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, and to pay your reward with interest compounded from the day you pointed out the error.

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

Valid HTML 4.01 Transitional