The Art of Computer Programming |
1: Fundamental Algorithms
2: Seminumerical Algorithms
3: Sorting and Searching
Donald E. Knuth
The tale of how Knuth took a decade off from writing The Art of Computer Programming to create the TeX typesetting language is one of the great legends of computer science. The appearance of a third edition of The Art of Computer Programming - typeset in you will never guess what! - is therefore a landmark event.
For those unfamiliar with the work, it is not about computer programming in the broad sense, but about the algorithms and methods which lie at the heart of most computer systems. Fundamental Algorithms contains background information for the series. Chapter one provides mathematical preliminaries and basic programming concepts, along with an introduction to the MIX assembly language, used throughout for implementations. Chapter two covers simple information structures: lists, trees, and related data structures.
The two chapters in Seminumerical Algorithms cover pseudo-random numbers - their generation and statistical testing - and numerical computation - doing arithmetic with floating point numbers, rationals, and polynomials. Almost everyone who has ever programmed has written a bubble sort at some point, but the full complexities of sorting algorithms are another story entirely. After an introduction to the mathematics of permutations, Sorting and Searching presents and analyses an extensive array of algorithms for sorting in memory (insertion, exchange, selection, permutations, Sorting and Searching presents and analyses an extensive array of algorithms for sorting in memory (insertion, exchange, selection, merging, and distribution algorithms), sorting on secondary storage, and searching,
The Art of Computer Programming is not a work for everyone, not even for all programmers. It will be an valuable reference for those working on the implementation and optimisation of key algorithms and data structures, but the more mathematically inclined will dip into it simply for pleasure. Knuth himself clearly enjoys the subtleties of the mathematics as much as anything: he writes at one point
and he provides some gloriously learned historical tidbits and mathematical digressions. The mathematics is heavy going in places, but the more difficult sections are marked and the material is laid out in such a way that those seeking algorithms to implement and performance analyses can skip the proofs and derivations and the more esoteric material.
Exercises are liberally provided, along with proper answers, which take up around a quarter of each volume. The exercises are carefully graded in difficulty on a scale from 0 to 50, and range from trivial tests of definitions to unsolved research problems. Reading The Art of Programming is a serious enough undertaking in itself (I have only read about a third of it so far myself), but anyone who succeeds in doing all the exercises will probably have earnt themselves several doctorates!
There is plenty of new material in this third edition, including new algorithms, examples, and exercises. The somewhat archaic MIX language has been retained, but we are promised its replacement by a modern, RISC "MMIX" in the next edition. Another incentive to purchase this edition, for those who already have the second, is the vastly improved typesetting. But the most exciting news of all is that volumes four and five are finally going to appear, followed by another revision of volumes one to three and then maybe by volumes six and seven (on the theory of languages and compilers).
Browse 400 other book reviews by Danny Yee
Top | Subjects | Titles | Authors | Keywords | Publishers | Latest
Thanks to Danny for graciously submitting this review. If you are interested in picking this book up, grab volume one here, volume two here and volume three here. If anyone else is interested in doing reviews, please e-mail me, hemos.