The Art of Computer Programming is, rightly, the most celebrated book, or rather set of books, in computer science and the publication of a new volume is a cause for celebration.

There's a new announcement on Donald Knuth's Recent News page - Volume 4B is here!. The exclamation mark is justified as it is now over 11 years since Volume 4A was published. 

Knuth's comment about its publication is: 

The fourth volume of The Art of Computer Programming deals with Combinatorial Algorithms, the area of computer science where good techniques have the most dramatic effects. I love it the most, because one good idea can often make a program run a million times faster. It's a huge, fascinating subject, and I published Part 1 (Volume 4A, 883 pages, now in its twenty-first printing) in 2011.

It was in 1962, sixty years ago, that Addison Wesley suggested that Knuth write a book on compilers. He initially planned the book as a twelve chapter work and in typical academic fashion the first three chapters would be based on notes for a course. However, once he embarked on writing he decided on a more ambitious work - one that would codify the theories, methods and algorithms of computer programming - an almost virgin subject at the time, in a complete fashion.

Knuth was able to convince Addison Wesley that the book was a good idea 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 and therefore decided to convert it into a multi-part work. Accordingly the first volume of The Art of Computer Programming, subtitled Fundamental Algorithms and published in 1968, consisted of just the first two chapters of the manuscript on Basic concepts and Information Structures. It is this volume that is by far the best known. It was the only one available in paperback and usually the only one that students ever really look at. 

The next volume, of what was then expected to be a seven-volume set, was Seminumerical Algorithms was published following year consisting of  a further two chapters on Random numbers and on Arithmetic. Two more chapters were combined to create the third volume, Sorting and Searching, which appeared in 1973 and tended to attract more attention perhaps because of the practical importance of the topic. These first three volumes virtually created the subject of computer science overnight and led to Knuth being described as the Euclid of computer science, which gives you some idea of just how important the work is. Volumes 1-3 were first combined into a slip case in 1988.

In the early 1990s Donald Knuth was of the opinion that it might take another twenty years before the remaining four volumes would be complete! But this estimate was woefully wrong

Why? One reason is the 9-year gap during which Knuth, dissatisfied with the typesetting used for his books invented (and documented) TeX, a language for typography and Metafont, a font design system. The other is that over the years the subject matter has expanded and Knuth is steadfast in his aim to present as complete an account as possible. The material that had been the topic of Volume 4 - combinatorial algorithms and recursion - could no longer be a single book but instead 4 books, A to D and now Volume 4B has made it into the new set.

According to Christine Solnon of the Department of Computer Science at the Institut National des Sciences Appliquées de Lyon, whose review is on the book's Informit page, Volume 4B

"dives deep into the fascinating exploration of search spaces (which is quite like looking for a needle in a haystack or, even harder, to prove the absence of a needle in a haystack), where actions performed while moving forward must be meticulously undone when backtracking. It introduces us to the beauty of dancing links for removing and restoring the cells of a matrix in a dance which is both simple to implement and very efficient. And it studies the iconic and versatile satisfiability problem and carefully analyses various ingredients of SAT solvers." 

Another review from Eiiti Wada, an "elder computer scientist" at the University of Tokyo refers to the exercises included in the book. 

"Professor Donald E. Knuth has always loved to solve problems. In Volume 4B he now promotes two brand new and practical general problem solvers, namely (0) the Dancing Links Backtracking and (1) the SAT Solver. To use them, a problem is defined declaratively (0) as a set of options, or (1) in Boolean formulae. Today's laptop computers, heavily armoured with very high speed processors and ultra large amounts of memory, are able to run either solver for problems having big input data. Each section of Volume 4B contains a multitudinous number of tough exercises which help make understanding surer. Happy reading!" 

Is there anyone else working on anything like TAoCP - even if only parts of the subject matter. Does anyone else have the breadth, depth and enthusiasm that makes TAoCP such a triumph. Thank you Donald Knuth for continuing to add to this magnificent work.

More Information

The Art of Computer Programming (TAOCP) Website

Knuth's Website

Related Articles

Donald Knuth and the Art of Programming

Donald Knuth At 80 Still Improving TAOCP

Another Chunk of The Art of Computer Programming 

The Art of Computer Programming, Volume 4, Fascicle 1 (book review)

The Art Of Computer Programming - Ace Gift For Any Programmer 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

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

<ASIN:0137935102>

<ASIN:0201038064>