The Art Of Computer Programming

www-cs-faculty.Stanford.EDU

Donald Knuth's comprehensive survey of algorithms and techniques. It was originally intended to be a book with 7 chapters. Soon Donald Knuth realized that the topics needed to be treated in depth, and decided to make the book 7 volumes long. After writing the first three volumes, he got a little distracted by a computer-typesetting project (most of us are grateful enough for the existence of TeX that we can almost forgive the incompleteness of TAOCP). He's now back to working more or less full-time on TAOCP, but it'll be quite a while before it's done...

The first three volumes (i.e., all that have been published so far) are:

Fundamental Algorithms (ISBN 0-201-89683-4)

images.amazon.com

Seminumerical Algorithms (ISBN 0-201-89684-2)

images.amazon.com

Sorting and Searching (ISBN 0-201-89685-0)

images.amazon.com

Note that the fourth volume is planned to be published in 3 books...


The following is Knuth's own outline from the preface to volume one.

Volume One:
Fundamental Algorithms

Chapter 1. Basic Concepts

Chapter 2. Information Structures

Volume Two:
Seminumerical Algorithms

Chapter 3. Random Numbers

Chapter 4. Arithmetic

Volume Three:
Sorting and Searching

Chapter 5. Sorting

Chapter 6. Searching

Volume Four:
Combinatorial Algorithms
(in progress; actually represents three books, 4A, 4B, and 4C)

Chapter 7. Combinatorial Searching

Chapter 8. Recursion

Volume Five:
Syntactical Algorithms

Chapter 9. Lexical Scanning

Chapter 10. Parsing

Volume Six:
The Theory of Languages
(more specialized, chapters not given)

Volume Seven:
Compilers
(more specialized, chapters not given)

I for one am looking forward to chapters nine and ten. Too bad I will have to wait so long. In the meantime I have to rely on Compilers Principles Techniques And Tools.


A major problem with TAOCP is that Knuth insists on writing all his algorithms in assembly language. That's a shame because TAOCP would probably be much more widely read if the algorithms in it were clearer, i.e. written in a structured language. Another problem for many is that the books dive into deep and difficult mathematical analysis. The series would be more usefully titled something like ``The Mathematical Analysis Of Assembly Language Algorithms''.

Strongly disagree that that would be more useful - it would just mean even less people read it. The algorithms are not assembly language ones, just illustrated in assembly language, and the mathematical analysis can easily be skipped.

Alternative explanations in a higher level language [such as scheme] would probably be a good idea, but it's still an excellent source of knowledge

People who can't handle assembly language can't handle the rest of his material, either. He defends his choice perfectly reasonably right at the start.

In volume 1 he says (even in the current edition) that chapter 10 will introduce the high level language PL/MIX. I've always imagined that he'll make it sort of a cross between Pascal and C, but who knows. Scheme's continuations would in fact make it a better choice than many high level languages, since Knuth does give code for coroutines and other things that cannot be coded in many languages. (One of the justifications for assembler in the books.)


Knuth has released 4 fascicles on-line. The first is www-cs-faculty.stanford.edu and describes MMIX, a theoretical RISC machine he intends to rewrite his algorithms to use. He has also published a book, MMIXware, ISBN 3-540-66938-8. There's even been a GCC port to MMIX.

The other 3 are drafts of portions of Volume 4: www-cs-faculty.stanford.edu , www-cs-faculty.stanford.edu , and www-cs-faculty.stanford.edu . The first is on generating all n-tuples, the second on generating permutations, and the third on generating all combinations.


Find a (previously unreported) error in TAOCP and Donald Knuth will send you a check for Two Dollars And Fifty Six Cents (US currency).


See original on c2.com