Customer Reviews

The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions

5 star:		(1)
4 star:		(1)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

First, the brevity. This book nominally contains 160 pages - take off a few for indicia and intro, and it's down to 150. Of those, page 87 and up are all "answers to exercises" - not really part of the exposition. Then, within those 86 pages, about 30 are exercises. Although helpful to the involved reader, they aren't direct exposition either.

The 50 or 60 pages left are good, though. They present the combinatorial content in deep detail, even if breadth sometimes seems to suffer. Proofs and analyses are thorough, but become lengthy and require fair bits of calculus. These discussions range across the width of contemporary math and the length of its last few generations of history.

That leaves the algorithms - a few good ones, but only a few. If you came to this as a cut-and-paster, you won't find much to take home. On the whole, it's a worthy addition to "The Art" and to the collection that makes up Volume 4. For many, however, it won't be the hardest-working reference on the shelf.

-- wiredweird

Only an author as smart and well known in his field as Donald Knuth would have tried this unusual format, which he terms a fascicle. In this third little book, he gives another extensive preview of his eventual fourth volume of "The Art of Computer Programming". When it finally appears, this volume is expected to span several books. In the interim, you will have to be content with these fascicles.

Even though this book is so slender, it is chock-a-block with tidbits, in the style of the first three volumes. Thus you can find out about a binomial tree, or even an infinite binomial tree. Or see how the Gray binary code also arises in the context of combinations.

An elegant aspect of this book is how Knuth ties in the discrete math of combinations with calculus applications. Quite often, these are two different worlds of maths, with different practitioners. Knuth uses the example of the varied properties of Bell numbers. Specifically, the rate at which these grow can be estimated by complex residues and saddle point analysis. Surprising results!