For those unfamiliar with the work, it is not about computer programming in the narrow 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, 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 a 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
"Even if sorting were almost useless, there would be plenty of rewarding reasons for studying it anyway! The ingenious algorithms that have been discovered show that sorting is an extremely interesting topic to explore in its own right. Many fascinating unsolved problems remain in this area, as well as quite a few solved ones." [Sorting and Searching, page 3]
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 have earned 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).
June 1998
- External links:
-
- information from Donald Knuth
- buy the boxed set from Amazon.com or Amazon.co.uk
Fundamental Algorithms
- buy from Amazon.com or Amazon.co.uk
Seminumerical Algorithms
- buy from Amazon.com or Amazon.co.uk
Sorting and Searching
- buy from Amazon.com or Amazon.co.uk
- Related reviews:
-
- books about computer science
- books about mathematics
- books published by Addison-Wesley