A Comparison of Four Algorithms Textbooks (2016)

I’m surprised, but I like this (I typically don’t like or agree with textbook comparisons, but I think this tour is mostly right). The Sedgewick text, Algorithms should be in there too but the author apparently didn’t read that.

My own experience basically agrees: I’ve read and enjoy Skiena, it’s written in clear style and it’s the “cover to cover” text for a working developer or for interview practice. But I also have TAOCP and CLRS on my shelf, and I haven’t read either of them. I’ve certainly used both of them a lot, but I simply haven’t read all of them because I use them more as reference texts.

Personally I find it bothersome that these textbooks are written with idiosyncratic pseudocode. In my opinion, many of these authors lose their grasp of common implementation difficulties if they don’t provide students with working code that will compile and run. It’s easy to throw down the theory and some okay-ish pseudocode while in effect saying, “...and the rest is just a minor implementation detail, which I leave as an exercise to the reader...”

The criticism of Knuth's use of MIX seems a bit off because:

+ Assembly language level instruction execution is a good way of talking about the running time of algorithms at a finer level of detail than Big O notation. Finer grain than Big O is helpful when analyzing and optimizing programs.

+ MIX is a good abstraction of the Von Neumann architecture and that's where the analysis of actual programs occurs.

+ MIX programs are still accessible to a general auidence 50 years after they were written. No actual programming language available in 1967 is still similarly accessible to such a degree.

+ MMIX is the successor of MIX...but in so far as learning MIX is an issue, it's more complex child probably is not an improvement.

The art of MIX is that it keeps the reader's focus on the fact that computer programs ultimately load registers, read memory, execute mathematical primatives, and branch no matter what object-oriented, functional, or type safe abstractions a high level language might offer.

Also, as I counted when this came up a few months ago[1], only a very tiny part of the TAOCP books is in MIX. For example, in Volume 4A, there are a grand total of 3 programs in MIX (and 2 of these in Answers to Exercises), over the 883 pages of the volume. Even in Volume 1 which has the most, there are only 36 small MIX programs over the 652 pages.

Knuth gives MIX programs only when it makes sense for a specific purpose (“…makes it possible to carry out meaningful studies of the effects of cache and RAM size and other hardware characteristics (memory speed, pipelining, multiple issue, lookaside buffers, the size of cache blocks, etc.) when comparing different schemes.”). He even gives C code sometimes, e.g. in Volume 2 when presenting a summary of the chapter on random numbers, there are five C snippets on pages 185–188.

Anyone who doesn't want to learn MIX can just ignore those few parts of TAOCP; there's enough value in those books without them. A good place to start may be the most recent fascicles[2].

[1]: https://news.ycombinator.com/item?id=14520230

[2]: http://www.cs.utsa.edu/~wagner/knuth/

Kleinberg/Tardos book that I am reading right now needs trimming for brevity. A good math text editor could, probably, easily lop off 1/3 of it without affecting its content. Otherwise I prefer it to most other algo books because its proofs are closest to how mathematicians approach their proofs. By contrast, I am confused as to why CLRS contains proofs at all. At the beginning of the book, the authors say something to the effect of actual proofs being too messy/hard so they simply wave their hands through them. But if most any intro discrete math books can do these proofs, why can't CLRS? To me it's a turn-off.

This seems to be a point where reasonable people may differ. I generally go to Knuth when I'm really stuck--not just how to do something but sometimes how to frame the problem so it can be solved. In that sense MIX does not make much difference since it's the discussion and backing mathematics that are most interesting.

On the other hand outside of OS and embedded systems people very few people regularly look at assembler, so for many people it's no longer an effective lingua franca for sample implementations. It's a bit like reading Principia Mathematica in the original Latin--sure, some people can do it but it's not the best way to transfer information to a broad audience. Personally I would be happy with some variant of C--the syntax is very broadly understood and the language is close enough to the hardware that implementation concepts come across clearly.