> So, what the hell's he planning to put in V4?
>From Knuth's web page at:
http://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4
his plans for upcoming volumes are:
Volume 4
Combinatorial Algorithms, in preparation.
Present plans are to publish ``Volume 4'' as three separate subvolumes:
Volume 4A, Enumeration and Backtracking
7.1. Boolean techniques (aka bit fiddling)
7.2. Generating all possibilities
7.2.1. Combinatorial generators
7.2.2. Basic backtrack
7.2.3. Efficient backtracking
7.3. Shortest paths
Volume 4B, Graph and Network Algorithms
7.4. Graph algorithms
7.4.1. Components and traversal
7.4.2. Special classes of graphs
7.4.3. Expander graphs
7.4.4. Random graphs
7.5. Network algorithms
7.5.1. Distinct representatives
7.5.2. The assignment problem
7.5.3. Network flows
7.5.4. Optimum subtrees
7.5.5. Optimum matching
7.5.6. Optimum orderings
7.6. Independence theory
7.6.1. Independence structures
7.6.2. Efficient matroid algorithms
Volume 4C, Optimization and Recursion
7.7. Discrete dynamic programming
7.8. Branch-and-bound techniques
7.9. Herculean tasks (aka NP-hard problems)
7.10. Near-optimization
8. Recursion
The material will first appear in beta-test form as fascicles of approximately
128 pages each, issued approximately twice per year beginning in 1999. These
fascicles will represent my best attempt to write a comprehensive account, but
computer science has grown to the point where I cannot hope to be an authority
on all the material covered in these books. Therefore I'll need feedback from
readers in order to prepare the official volumes later. The publishers have
pledged to make the fascicles available in an inexpensive form, essentially at
cost. (Of course, the paper and binding will probably be designed to self-
destruct in a few years, so that you will have to buy the real book after it
is debugged:-)
If all goes as planned, Volumes 4A, 4B, and 4C will be ready in the year 2004.
Volume 5
Syntactic Algorithms, in preparation.
9. Lexical scanning (includes also string search and data compression)
10. Parsing techniques
Estimated to be ready in 2009.
Future plans
As I write Volumes 4 and 5, I'll need to refer to topics that belong logically
in Volumes 1--3 but weren't invented yet when I wrote those books. Instead of
putting such material artificially into Volumes 4 or 5, I'll put it into
fascicle form. One of the first such fascicles will be a description of MMIX,
a RISC machine that will take the place of MIX.
After Volume 5 has been completed, I will revise Volumes 1--3 again to bring
them up to date. In particular, the new material for those volumes that has
been issued in beta-test fascicles will be incorporated at that time.
Then I will publish a ``reader's digest'' edition of Volumes 1--5, condensing
the most important material into a single book.
And after Volumes 1--5 are done, God willing, I plan to publish Volume 6 (the
theory of context-free languages) and Volume 7 (Compiler techniques), but only
if the things I want to say about those topics are still relevant and still
haven't been said. Volumes 1--5 represent the central core of computer
programming for sequential machines; the subjects of Volumes 6 and 7 are
important but more specialized.
