Excerpt
To put all the good stuff into one book is patently impossible, and attempting even to be reasonably comprehensive about certain aspects of the subject is likely to lead to runaway growth. GERALD B. FOLLAND "Editor's Corner" (2005)
La dernière chose qu'on trouve en faisant un ouvrage est de savoir celle qu'il faut mettre la première.
BLAISE PASCAL, Pensées 740 (c. 1660)
This booklet is Fascicle 0 of The Art of Computer Programming, Volume 4: Combinatorial Algorithms. As explained in the preface to Fascicle 1 of Volume 1, I'm circulating the material in this preliminary form because I know that the task of completing Volume 4 will take many years; I can't wait for people to begin reading what I've written so far and to provide valuable feedback.
To put the material in context, this fascicle contains the opening sections intended to launch a long, long chapter on combinatorial algorithms. Chapter 7 is planned to be by far the longest single chapter of The Art of Computer Programming; it will eventually fill at least three volumes (namely Volumes 4A, 4B, and 4C), assuming that I'm able to remain healthy. Like the second-longest chapter (Chapter 5), it begins with pump-priming introductory material that comes before the main text, including dozens of exercises to get the ball rolling. A long voyage lies ahead, and some important provisions need to be brought on board before we embark. Furthermore I want to minimize the shock of transition between Chapter 6 and the new chapter, because Chapter 6 was originally written and published more than thirty years ago.
Chapter 7 proper begins with Section 7.1: Zeros and Ones, which is another sort of introduction, at a different level. It dives into the all-important topics that surround the study of Boolean functions, which essentially underly everything that computers do. Subsection 7.1.1, "Boolean basics," attempts to erect a solid foundation of theoretical and practical ideas on which we shall build significant superstructures later; subsection 7.1.2, "Boolean evaluation," considers how to compute Boolean functions with maximum efficiency.
The remaining parts of Section 7.1--namely 7.1.3, "Bitwise tricks and techniques," and 7.1.4, "Binary decision diagrams"--will be published soon as Volume 4, Fascicle 1. Then comes Section 7.2, Generating All Possibilities; the fascicles for Section 7.2.1, "Generating basic combinatorial patterns," have already appeared in print. Section 7.2.2 will deal with backtracking in general. And so it will go on, if all goes well; an outline of the entire Chapter 7 as currently envisaged appears on the taocp
webpage that is cited on page ii.
These introductory sections have turned out to have more than twice as many exercises as I had originally planned. In fact, the total number of exercises in this fascicle (366) is almost unbelievable. But many of them are quite simple, intended to reinforce the reader's understanding of basic definitions, or to acquaint readers with the joys of The Stanford GraphBase. Other exercises were simply irresistible, as they cried out to be included here--although, believe it or not, I did reject more potential leads than I actually followed up.
I would like to express my indebtedness to the late Robert W Floyd, who made dozens of valuable suggestions when I asked him to look over the first draft of this material in 1977. Thanks also to Robin Wilson of the Open University for his careful reading and many detailed suggestions; and to hundreds of readers who provided fantastic feedback on early drafts that circulated on the Internet.
I shall happily pay a finder's fee of $2.56 for each error in this fascicle when it is first reported to me, whether that error be typographical, technical, or historical. The same reward holds for items that I forgot to put in the index. And valuable suggestions for improvements to the text are worth 32¢ each. (Furthermore, if you find a better solution to an exercise, I'll actually reward you with immortal glory instead of mere money, by publishing your name in the eventual book:-)
Notations that are used here and not otherwise explained can be found in the Index to Notations at the end of Volumes 1, 2, or 3. Those indexes point to the places where further information is available. (See also the entries under "Notation" in the present booklet.) Of course Volume 4 will some day contain its own Index to Notations.
Machine-language examples in all future editions of The Art of Computer Programming will be based on the MMIX
computer, which is described in Volume 1, Fascicle 1.
Cross references to yet-unwritten material sometimes appear as '00' in the following pages; this impossible value is a placeholder for the actual numbers to be supplied later.
Happy reading!
D. E. K.
Stanford, California
January 2008