The Art of Computer Programming, Volume 4, Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Functions
by Donald E. Knuth
Addison-Wesley, Pearson Education 2008.
ISBN 978-0-321-53496-5, 216 pages, index and Answers to Exercises
Reviewed by Hilarie Orman and Richard Schroeppel May 23, 2008
If you have ever written computer software or talked to a programmer, you've heard of Donald Knuth's book series, The Art of Computer Programming. Everyone of a certain age, and many more, have the first three volumes. They are legendary. Even more legendary is the fourth volume, Combinatorial Algorithms. Legendary because it has been an elusive goal for the author. It has been 35 years since Volume 3, Sorting and Searching, was printed. We had all but given up on ever seeing Volume 4. That was why, when we were contacted by an Pearson representative about reviewing a portion of Volume 4 for Cipher, we did not even bother to ask ourselves, "what has this got to do with computer security?" We jumped at the chance.
What we've been perusing for a few weeks a booklet that is the tip of the iceberg that will be Volume 4. Knuth calls this 216 page gem a "fascicle", a part of a book. It introduces Chapter 7 of the book series, the subject of the chapter being combinatorial searching. This is a big topic, a huge topic, it outgrew the bounds of what one could call "a book", so Knuth plans to have it published as three books, Volumes 4A, 4B, and 4C.
If you loved volumes 1 through 3, you'll not be disappointed by this booklet. The font and typesetting are superb, the quotations at the start of each chapter are witty and apt, the exercises plentiful and difficult. The text draws you in with its cogent questions and accessible examples, but then hits you with the deep puzzles at the heart of the combinatorial matter. It's a minefield for the brain.
The booklet known as as Fascicle 0 contains 216 pages, the merest appetizer to the banquet promised as Volume 4. It has the introduction to chapter 7 and section 7.1. Section 7.1 is about variables and functions with only two values. There are two subsections: Boolean basics and Boolean evaluation.
If you haven't read Knuth previously, you might have some hurdles to master. This isn't a textbook, it is a tour through the workings of mathematical structures and the algorithms that answer questions about them. Although everything is interesting, accessible, and backed up by detailed references, this book does not pander to the casual reader. Be prepared to exercise your mind and find something new even in material you thought you mastered long ago.
The introduction to Chapter 7 begins with a one sentence definition of combinatorics. The next sentence introduces "Langford pairs" and launches into an explication of the five fundamental combinatoric questions as illustrated by Langford pairs.
The next topic is orthogonal Latin squares. Did you know that the great mathematician Euler worked on the problem near the end of his life, leaving behind him a conjecture that was not resolved until the modern computing era? Before you reach the end of this chapter introduction you will know all about it, and many other things, including the existence of the Stanford Graph Database.
There are the usual delightful exercises before the the Boolean basics. This has the history of two-valued logic, DeMorgan's Laws, definitions of normal forms, Horn and Krom clauses, and several other things that might together constitute an undergraduate logic course before even reaching the halfway point in the section. It rolls on through median labels, theshold functions, and canalizing functions. Then there are 133 tastefully chosen exercises.
The last section discusses the methods and the difficulty of evaluating Boolean functions in general. Knuth notes that thousands of papers have been written about them. It was his task to select a few topics that are of interest to computer programmers. The overview is good, and after working on any of the 88 exercises you might be tempted to peek at the answers at the back.
Readers may wonder why there are so few "cookbook" algorithms (only one per section). That might be because of the odd state of knowledge about evaluating Boolean functions. After all the thousands of papers, there is no real "killer algorithm" for evaluation and there is no set of explicit functions that has provable nonlinear cost. In some special cases there are shortcuts over the straightforward exponential time evaluation method, but true optimum is an elusive goal for any explicit function family.
Yes, there is a finder's reward of $2.56 for typos or other errors reported to the author, and 32 cents for suggested improvements, plus the possibility of Your Name in Print in the final work.
This tiny taste of Volume 4 is a delight, and we wait in respectful anticipation for Fascicle 1.