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, "Introduction to Combinatorial Algorithms and Boolean
Functions." 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 I was contacted by an Addison-Wesley representative
about reviewing a portion of Volume 4 for Cipher, I did not even
bother to ask myself, "what has this got to do with computer
security?" I jumped at the chance.
What I'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.