The Art of Computer Programming, Volume 4: Generating All Trees, History of Combinatorial Generation

by Donald E. Knuth, Addison Wesley & Prentice Hall, Upper Saddle Rive, New Jersey, 2006. 120 pp., $19.99 (paper). ISBN 0-321-33570-8.

Reviewed by Charles Ashbacher, Charles Ashbacher Technologies, Hiawatha , IA, USA,

space BOOK

PDF Icon
PDF Version

It can be convincingly argued that Knuth's three volumes The Art of Programming is the best reference set for computer science ever written. They top my list of required reference works; the only items that might be placed ahead of them are books such as complete listings of the values of Unicode characters. Even then, it would be very specific to the situation.

It would be very difficult to overstate the value of the tree data structure in computing. If you cannot program the creation and searching of trees, do yourself and your employer a favor and find another line of work. In this book, Knuth gives the history of how the many uses of trees arose in the history of human problem solving. Concise with just enough detail, it is well worth reading. He frequently uses algorithms expressed in stepwise notation to make his points.

However, the real value of this book is in the exercises at the end of the sections. Because so much of it was familiar to me, I was often skimming through the explanatory material. That strategy changed when I reached the exercises, they are extensive and really force you to think the matter through. An enormous amount of fundamental computer science is expressed in those 156 questions and detailed answers to all of the exercises are included at the end. Even though there is only approximately sixty pages of explanatory material in this book, it could be used as a semester long text in advanced programming.

If working with trees is part of your job description, then you are a fool if you don't buy this book, study it then keep it for a reference. It is that good and in my opinion, it is the best computer book published in 2006.

Cite this book review as follows: Charles Ashbacher: "The Art of Computer Programming, Volume 4: Generating All Trees, History of Combinatorial Generation", in Journal of Object Technology, vol. 6, no. 1, January-February 2007, pp 65