*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 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