The Art of Computer Programming, Volume 1 - Knuth

I read Volume 1 of TAoCP in 2000, but then lost interest somewhere early in Volume 2. I've just started reading Volume 2 again, so this seems an appropriate point at which to do a retro-review.

Volume 1, Fundamental Algorithms is, to put it bluntly, not very good. It takes 500 pages to cover basic discrete maths for computer science, a description of the machine code language "MIX", lists, tree and some basic memory management. All of these things are actually covered better elsewhere by other texts, with the exception of MIX. This description of a made-up computer architecture is just a waste of time, instead.

The book really does get across how much of a hacker Knuth is. Algorithmic complexity is explored in terms of number of machine code instructions required on MIX. The algorithms are explored in terms of numbered steps and gotos rather than structured programs (like Cormen et al, say). I guess a lot of it is baggage from the early days of computing.

There's a lot of random extra side notes and histories of ideas. That's a Knuth-ism, too, but also reveals his inability to leave stuff out (or perhaps, leave enough out). Some of these asides are quite interesting, but slow the pace down, and presumably the research involved explains why it's taken quite so long for the series to be produced.

Perhaps this is the greatest weakness of the series. By trying so hard to include everything, rather than provide an introduction and more pointers to interesting papers (again, like Cormen), the content takes so long to produce that it falls behind the state of the art it wishes to convey. To a large degree, it starts to become interesting mostly for historical reasons.

Did I learn anything from this volume? There's clearly plenty in such an encyclopaedic volume that I hadn't heard of before reading, but what about things that I felt I cared about? I remember learning about threaded binary trees, and that's about it!

Posted 2013-12-07.