The beginning of the month saw Donald Knuth release his latest work, Art of Computer Programming, The: Combinatorial Algorithms, Volume 4B, as he continues to chug along on his life’s work at the young age of 84. He currently expects volume 5 to be ready in 2025, and I assume that means it will come prior to the remaining work on volume 4, which he has only done 2 pre-fascicles for 7.2.2.4 and 7.2.2.8:
7.2.2.3. Constraint satisfaction
7.2.2.4. Hamiltonian paths and cycles
7.2.2.5. Cliques
7.2.2.6. Covers
7.2.2.7. Squares
7.2.2.8. A potpourri of puzzles
7.2.2.9. Estimating backtrack costs
7.2.3. Generating inequivalent patterns
7.3. Shortest paths
7.4. Graph algorithms
7.4.1. Components and traversal
7.4.1.1. Union-find algorithms
7.4.1.2. Depth-first search
7.4.1.3. Vertex and edge connectivity
7.4.2. Special classes of graphs
7.4.3. Expander graphs
7.4.4. Random graphs
7.5. Graphs and optimization
7.5.1. Bipartite matching
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
7.7. Discrete dynamic programming
7.8. Branch-and-bound techniques
7.9. Herculean tasks (aka NP-hard problems)
7.10. Near-optimization
Recursion
Every time I see them, or pull one off the shelf it just amazes me how much time, and effort has gone into this wonderful project between the research, writing, and developing TeX, and his ability to keep working it all of these years later.
I wonder if any thought has been given to working with a younger partner to prepare them to carry on the work in the future, as there will still work to be done for many years.
Donald E. Knuth is nothing short of legendary. My understanding was that this was expected to be done much sooner but just kept expanding and expanding.
I think his original plan was probably that it would be done in the 70s. Then with him taking a chunk of time to develop TeX so he could have the books look the way he wanted, plus the explosion of knowledge in the field, and I guess other things he has been interested in have really stretched out the time. Wikipedia says TeX was initially released in 1978. There were 3rd editions of 1 and 2, plus a 2nd edition of 3 in the mid-90s, and then for a long time it was the pre-print bits he would have on his webpage for sections of the ongoing work, with 4A finally being published in 2011 (wow, didn’t realize it had been that long already) and now 4B. I have no idea how the rest of those sections listed are going to break down into further volume 4 books, and just how much work has been done over the years on those sections. It seems like he continually gathering information and researching different parts, then puts out pre-prints to experts in those fields to comment on, and eventually something gets published.
It would be great if he really does plan to put out volume 5 in 2025, but that seems like a very optimistic schedule.
He still has the following listed as planned:
Volume 5 on lexical scanning and parsing techniques
Revision of volumes 1 - 3 once volume 5 is complete
A “reader’s digest” edition condensing most important material into single book
With these to follow if he feels there is something he wants to say that hasn’t been said:
Volume 6 (the theory of context-free languages)
Volume 7 (Compiler techniques)
Plus somewhere in the above there are the other bits of volume 4.
The topics you listed in that book sound interesting. Unfortunately for the job I have, and even the last one I had, I have no use for such knowledge. Back in the day when I did game development though, I would have found such a book indispensable.
Googling this term it seems the only use is related to TAOCP! (/Fascicles/ can be found, however)
I’ve always liked to imagine that whatever the final chapter is (compilers, it seems) it’s his favourite topic, but he’s had to miserably grind through every other topic before he gets to that one!
It always reminds me of printing out a googleplex too, in that his pace of output is smaller than the pace of innovation, but unlike printing a googleplex he can’t just restart on a faster machine and eventually catch up.
