Slashdot is powered by your submissions, so send in your scoop


Forgot your password?
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. ×
News Books Media Book Reviews

Review: The Art of Computer Programming

Reader and veteran book reviewer Danny Yee has written a review of Donald Knuth's The Art of Computer Programming. This book is a bit different from the normal pack, getting at the heart of how most computer systems function underneath, with much exploration into the algorithims and methods. So, for a better grasp of the fundament of computing, click below.
The Art of Computer Programming
1: Fundamental Algorithms
2: Seminumerical Algorithms
3: Sorting and Searching

Donald E. Knuth
Addison-Wesley 1997, 1998

Danny's Homepage

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

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

This discussion has been archived. No new comments can be posted.

Review: The Art of Computer Programming

Comments Filter:

I have a theory that it's impossible to prove anything, but I can't prove it.