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.

Amazon.com® Reader Reviews (Ranked by Helpfulness)

Average Amazon.com® Rating:  Based on 4 Ratings

Great for comp sci and math majors... - 2006-04-30
Reviewer Rating:
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.

has a distinctive historical monograph - 2006-03-30
Reviewer Rating:
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.

Expands upon a multi-volume work with hundreds of new programming exercises - 2006-04-13
Reviewer Rating:
The fourth volume in the classic ART OF COMPUTER PROGRAMMING: GENERATING ALL TREES: HISTORY OF COMBINATORIAL GENERATION add to and expands upon a multi-volume work on the analysis of algorithms in classical programming, updating sections of the set using a series of small fascicle books. This covers the generatio of all trees, a topic covered in the first three volumes of ART OF COMPUTER PROGRAMMING, and provides over a hundred new exercises to programmers.

The best computer book published in 2006 - 2009-01-08
Reviewer Rating:
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

Browse Similar Topics

Top Level Categories:
Software Engineering

Sub-Categories:
Software Engineering > Algorithms