Art of Computer Programming, Volume 4, Fascicle 4,The: Generating All Trees--History of Combinatorial Generation (Paperback)

by Donald E. Knuth (Author)

Editorial Reviews

Product Description
This multivolume work on the analysis of algorithms has long been recognized as the definitive description of classical computer science.The three complete volumes published to date already comprise a unique and invaluable resource in programming theory and practice. Countless readers have spoken about the profound personal influence of Knuth's writings. Scientists have marveled at the beauty and elegance of his analysis, while practicing programmers have successfully applied his "cookbook" solutions to their day-to-day problems. All have admired Knuth for the breadth, clarity, accuracy, and good humor found in his books. To begin the fourth and later volumes of the set, and to update parts of the existing three, Knuth has created a series of small books called fascicles, which will be published at regular intervals. Each fascicle will encompass a section or more of wholly new or revised material. Ultimately, the content of these fascicles will be rolled up into the comprehensive, final versions of each volume, and the enormous undertaking that began in 1962 will be complete. Volume 4, Fascicle 4 This latest fascicle covers the generation of all trees, a basic topic that has surprisingly rich ties to the first three volumes of The Art of Computer Programming. In thoroughly discussing this well-known subject, while providing 124 new exercises, Knuth continues to build a firm foundation for programming. To that same end, this fascicle also covers the history of combinatorial generation. Spanning many centuries, across many parts of the world, Knuth tells a fascinating story of interest and relevance to every artful programmer, much of it never before told. The story even includes a touch of suspense: two problems that no one has yet been able to solve.

From the Back Cover

This multivolume work on the analysis of algorithms has long been recognized as the definitive description of classical computer science.The three complete volumes published to date already comprise a unique and invaluable resource in programming theory and practice. Countless readers have spoken about the profound personal influence of Knuth's writings. Scientists have marveled at the beauty and elegance of his analysis, while practicing programmers have successfully applied his “cookbook” solutions to their day-to-day problems. All have admired Knuth for the breadth, clarity, accuracy, and good humor found in his books.

To begin the fourth and later volumes of the set, and to update parts of the existing three, Knuth has created a series of small books called fascicles, which will be published at regular intervals. Each fascicle will encompass a section or more of wholly new or revised material. Ultimately, the content of these fascicles will be rolled up into the comprehensive, final versions of each volume, and the enormous undertaking that began in 1962 will be complete.

Volume 4, Fascicle 4

This latest fascicle covers the generation of all trees, a basic topic that has surprisingly rich ties to the first three volumes of The Art of Computer Programming. In thoroughly discussing this well-known subject, while providing 124 new exercises, Knuth continues to build a firm foundation for programming. To that same end, this fascicle also covers the history of combinatorial generation. Spanning many centuries, across many parts of the world, Knuth tells a fascinating story of interest and relevance to every artful programmer, much of it never before told. The story even includes a touch of suspense: two problems that no one has yet been able to solve.

See all Editorial Reviews

Product Details

• Paperback: 128 pages
• Publisher: Addison-Wesley Professional; 1 edition (February 16, 2006)
• Language: English
• ISBN-10: 0321335708
• ISBN-13: 978-0321335708
• Product Dimensions: 9.4 x 6.2 x 0.5 inches
• Shipping Weight: 9.1 ounces (View shipping rates and policies)
• Average Customer Review: 4.8 out of 5 stars See all reviews (5 customer reviews)
• Amazon.com Sales Rank: #348,123 in Books (See Bestsellers in Books)

Customer Reviews

Most Helpful Customer Reviews

8 of 8 people found the following review helpful:

5.0 out of 5 stars has a distinctive historical monograph, March 29, 2006

By	W Boudville (Terra, Sol 3) - See all my reviews (TOP 50 REVIEWER)    (REAL NAME)

This fascicle can perhaps best be read as a sequel to Knuth's Volume 3, on sorting and searching, where he discusses trees. The fascicle extends that into how does one generate every tree. Of the four fascicles thus published, this might be the skimpiest in terms of current mathematical knowledge. Though to a practising programmer, trees are a vital construct and the book could well have germane analysis. And, as with his other books in this series, there is a tough set problems that can be just as instructive and interesting as the text.

Still, to perhaps compensate for the thin length, the book contains a distinctive section on the history of combinatorial generation. Knuth delves into this subject while giving a deeper treatment of the maths than one would likely encounter in a popular text directed at a general audience. He cites the I Ching, as well as ancient Indian and Arab manuscripts. The I Ching is notable as it is still in print and likely to be familiar to many.

With the publication of this fascicle, the collective set of four would make a respectable book in its own right. However, Knuth is scarcely done yet. We can expect more fascicles, and soon, one might hope. And eventually, a hardcover.

5.0 out of 5 stars The best computer book published in 2006, January 8, 2009

By	Charles Ashbacher "([e-mail])" (Marion, Iowa United States([e-mail])) - See all my reviews (TOP 50 REVIEWER)

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.

Published in the online Journal of Object Technology, reprinted with permission

9 of 17 people found the following review helpful:

5.0 out of 5 stars Great for comp sci and math majors..., April 30, 2006

By	Thomas Duff "Duffbert" (Portland, OR United States) - See all my reviews (TOP 50 REVIEWER)    (REAL NAME)

I've known about The Art of Computer Programming volumes by Donald E. Knuth for some time, but I've always avoided reviewing them for fear of not being able to do them justice. But after being contacted specifically by the publisher asking if I was interested in the latest - The Art of Computer Programming, Volume 4, Fascicle 4 : Generating All Trees--History of Combinatorial Generation - I decided to give it a try. For the right audience, this is really good stuff. But I can tell you that I'm not it...

Content:
Chapter 7 - Combinatorial Searching: 7.2 - Generating All Possibilities; 7.2.1 - Generating Basic Combinatorial Patterns; 7.2.1.1 - Generating all n-tuples; 7.2.1.2 - Generating all permutations; 7.2.1.3 - Generating all combinations; 7.2.1.4 - Generating all partitions; 7.2.1.5 - Generating all set partitions; 7.2.1.6 - Generating all trees; 7.2.1.7 - History and further references; Answers to Exercises; Index and Glossary

Don't refresh your browser thinking the Content section didn't load properly. There's just chapter 7... For those who don't understand the "fascicle" concept (like I didn't before getting this volume), it's a small book (120 pages) of material that either updates writings in previous volumes or a "preview" of material that will eventually be rolled into a single volume (in this case, volume 4). Knuth has a lot of information he wants to convey, and by using fascicles, the public can get a steady flow of information and help shape the continuing evolution of the series. Interesting concept, and one I can appreciate. Another review stated that this was probably one of the "skimpiest" volumes in terms of mathematical knowledge. If true, then I fear what will await me with future installments. To get the most of out Knuth's work, you really do need to be well-grounded in computer science and mathematical theory. Every page is populated with numerous formulas to prove the subject matter, and I'll admit to being completely lost in most of it. That doesn't mean the book isn't good. It *is* excellent work, but I'm definitely not the target audience. I don't come from a formal computer science and mathematics background, so I'd have to really slog through everything from page 1 with supporting texts in order to fully benefit from it.

It wasn't a total loss for me, though... I enjoyed the History and Further References chapter, where he shows the tree theory and how it affected such things as literature and culture through the ages. Whether the ancient Chinese had all this in mind when developing the I Ching is open to debate, but the theory and underpinnings of trees is definitely there. And for those readers who really want to work through and apply the material, there are exercises galore at the end (with answers graciously provided for those who get stuck). You could likely set up a college level course based on this (and associated) book, and it would be foundational to a computer science degree.

So, for the right audience, this is the type of book that will allow for weeks of thought and learning. But if you're more like me, someone who deals more with business systems and development (without a comp sci degree to back it up), you'll likely miss most of the value here.