Donald Knuth's The Art of Computer Programming is a legend among computer science books. For those who are looking forward to the next installment of this multi-part work, the 2nd revision of pre-fascicle 6a is now available for download.

At the beginning of the 1960s Donald Knuth, who at the time was an associate professor at Caltech accepted a commission to write a book on programming language compilers but quickly realized that first a book on the fundamental theory of computer programming was required.

Knuth was able to convince Addison Wesley that the book was a good idea and so he embarked on it, and by 1965 he had completed a draft of twelve chapters consisting of 3000 hand written pages, which was initially planned to be a single book.

When the first chapter was sent to the publisher it was estimated that the finished book would be 2000 printed pages, which by the standards of the time was unthinkable. Having often criticized books of approaching 1000 pages as being unreadable because of their weight and tendency to fall apart it is easy to sympathize with Addison Wesley's decision to convert it into a multi-part work.

So it was that the first volume of The Art of Computer Programming, subtitled Fundamental Algorithms and published in 1968, consisted of just two chapters. 

Two further volumes of what was expected to be a seven-volume set and given the abbreviation TAOCP, appeared in 1969 and 1973.

• Volume 2 – Seminumerical Algorithms (Chapters 3 and 4)
• Volume 3 – Sorting and Searching (Chapters 5 and 6).

By this time Knuth had joined Stanford University, to which he is still affiliated., and these first three volumes created, or at least consolidated, the subject of computer science with Knuth being described as the Euclid of computer science. His work has been endorsed by many with Bill Gates being quoted on the Pearson website as saying:

If you think you’re a really good programmer… read [Knuth’s] Art of Computer Programming… You should definitely send me a résumé if you can read the whole thing.

After the publication of Volumes 1 -3 there was a long gap before Volume 4 began to appear. One reason for this being that Knuth became dissatisfied with the look of his books and decided to do something about it.

The few months that he intended to spend on the project turned into nine years during which time he invented TeX, a language for typography and Metafont, a font design system. All of the work he did has been placed in the public domain and Knuth's five-volume Computers & Typesetting, published in 1986 is the explanation of the theory, a user manual and a source of examples.

The other was that the topic of the original Chapter 7,  "combinatorial searching" had expanded so much in the intervening period. This and Chapter 8 on recursion had been intened to be combined into a single volume but the plan changed.

A new publishing strategy was adopted when Knuth resumed work on his magnum opus whereby short volumes, known as "fascicles" would be published. This led to the appearance in 2005 to 2009 of four slim books which were then combined into Volume 4A on the topic of combinatorial algorithms in 2011, followed shortly by a boxed set of Volumes 1-4A.

Last year Knuth agreed to letting Pearson create electronic versions of Volumes 1, 2, 3 and 4A and also of  Volume 1, Fascicle 1, MMIX -- A RISC Computer for the New Millennium, which is a volume devoted to the 64-bit RISC computer devised by Knuth to illustrate machine-level aspects of programming.  

In 1999 explained the importance of MMIX to TAOCP:

It replaces MIX, the 1960s-style machine that formerly played such a role... I strove to design MMIX so that its machine language would be simple, elegant, and easy to learn. At the same time I was careful to include all of the complexities needed to achieve high performance in practice, so that MMIX could in principle be built and even perhaps be competitive with some of the fastest general-purpose computers in the marketplace.

MMIX is so important that it now has another book devoted to it:  MMIX Supplement, The: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth.

This has been authored by  professor of mathematics and computer science at Munich University of Applied Sciences, Dr. Martin Ruckert, who maintains the MMIX home page. 

“I am thrilled to see the present book by Martin Ruckert: It is jam-packed with goodies from which an extraordinary amount can be learned. Martin has not merely transcribed my early programs for MIX and recast them in a modern idiom. He has penetrated to their essence and rendered them anew with elegance and good taste. His carefully checked code represents a significant contribution to the art of pedagogy as well as to the art of programming.” 

Currently Knuth is working on Volume 4B and it is the middle third, fascicle 6a, that is now online for beta testing;

Knuth says on his Recent News page: 

[this] will be a major introduction to the topic of Boolean Satisfiability, emphasizing its many applications, together with a variety of algorithms to solve SAT problems with greater and greater speed. I began studying this topic in autumn 2011, and found it to be amazingly interesting. Thus I've had great fun telling this story, and connecting SAT with many other aspects of computer science and math.

It's not a short story; indeed, this section has turned out to be the largest by far of any in The Art of Computer Programming. But the material is rich, beautiful, instructive, and important, so I'm pleased to have had the opportunity to pull it together from many sources.

Addison Wesley plans to publish this fascicle in paperback before the end of 2015 and Knuth is asking for feedback that can be taken into account in the final stages of preparation before September 15. A note on his site says:

I worked particularly hard while preparing some of those exercises, attempting to improve on expositions that I found in the literature; and in several noteworthy cases, nobody has yet pointed out any errors. It would be nice to believe that I actually got the details right in my first attempt. But that seems unlikely, because I had hundreds of chances to make mistakes. So I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out as yet.

He goes on to to ask for people to contact him to report that they have failed to find any errors in a long list of examples in prefascicle 6a.

So if you want to make a small contribution to this legendary work, visit Knuth's Recent News page download the 318-page pdf and check out some of its exercises.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0321751043>