Page 2 of 3
The Art of Computer Programming
Knuth was able to convince Addison Wesley that the book was a good idea and so he started, and by 1965 he had completed a draft of twelve chapters - 3000 hand written pages.
The first chapter was sent to Addison Wesley who estimated that the finished book would be 2000 printed pages! Chapter One became half of the first volume of the now famous The Art of Computer Programming - a multi-part work that, 40 years after the original publication, is about to see the arrival of Volume 4A, Combinatorial Algorithms, Part 1.
The first three volumes virtually created the subject of computer science overnight. Knuth is sometimes described as the Euclid of computer science - only time will tell if this is a fair assessment but it gives you some idea of just how important the work is.
The first volume, Fundamental Algorithms, is by far the best known. It is the only one available in paperback and usually the only one that students ever really look at. Volume Two, Semi-numerical Algorithms, also gets less attention than Volume Three, Searching and Sorting, perhaps because of the practical importance of the topic.
Past, present and future
In the early 1990s Donald Knuth was of the opinion that it might take another twenty years (i.e. until now) before the remaining four volumes would be complete and that after the series was complete he planned to write music - a subject that he regards as equally important as computing.
If fact progress has been rather slower and the size of the project has increased. Over recent years sections of Volume 4 Combinatorial algorithms have appeared as "fascicles" (see the review of the most recent Volume 4, Fascicle 1, published in 2009). It is now planned for Volume 4 to appear as a series of at least three separate sub-volumes with Volume 4A expected to be published in January 2011.
Volume 5 Syntactical algorithms is also in preparation. Covering lexical scanning (includes also string search and data compression) and parsing techniques it is estimated to be ready in 2020 (postponed from an earlier estimate of 2015). After that Knuth intends to revise the existing material and his plans for Volume 6 (Theory of languages) and Volume 7 (Compilers) are to proceed with them "only if the things I want to say about those topics are still relevant and still haven't been said". You can follow progress at a website set up for this very purpose:
Personally, I feel that the difficulty in creating a complete work for each of the remaining topics is more difficult than for volumes one through three - but who am I to make this judgement. Perhaps I would have felt the same about the existing volumes had I not actually seen them!
When I first read Volume One back in 1975 I found it astounding. But you have to remember that the machines I was using were a 360 mainframe and a PDP mini and the book seemed just right for the time. Now when I look at it again I have to say that it seems dated in concept, approach, language and just about everything else you could list.
Knuth invented a computer and its language MIX to use in examples. I doubt if anyone today would set out to write a book on algorithms using assembly language - even a machine independent one. Also, the topics that are covered are not really the concern of most practising programmers today. You will find good discussions of sorting and searching, of fundamental data structures such as trees, lists etc. and of random numbers, but don't expect to find anything about fractals, sprites or web services. To a certain extent I agree that they would be out of place but on the other hand I'm not at all sure that they couldn't be turned into the same sort of intellectual stuff that is crammed into "The Art" - maybe there is a need for a second generation Knuth even before the master has completed the original work!
Still, this doesn't alter the fact that Knuth describes, explains and analyses many of the fundamental methods that all programmers should know. If you can't take the detailed maths then I would still suggest that a skim read is a good idea. Don't worry too much about understanding the MIX code in detail but concentrate on understanding the algorithms and the discussions of the results.
Knuth's works are classics but in many cases there are more modern books which deal with the same topics rather more clearly. I still think that every programmer should at least be exposed to the contents - it's our cultural heritage.