What background is needed to understand The Art of Computer Programming, Volume 4A?

Question

I recently made the investment in the newly-printed four-volume set of Donald Knuth's The Art of Computer Programming. Like this poster, I probably do not have the time right now to read the entire set, with a full-time programming job, spending time with my girlfriend, doing housework, etc., though I have no doubt I would find it fascinating. Public transit is not available for my commute, and unless there is a "books-on-CD" version, consuming the material during my commute is probably out of the question.

After reading this review of Volume 4A, I realized that at least some of the information may be of great help in my thesis. Incidentally, the thesis is for my doctorate in music, which has been on the back burner for a little longer than I would like. It sounds like, from the reviewer's description, combinatorial algorithms could be of great help in solving the problem I am attempting to solve.

Am I going to need to read the first three volumes to understand the fourth? While I have no computer science degrees per se, I do have a reasonable amount of experience, and I have succeeded in graduate coursework in algorithms, compilers, and databases. Have any of you read some or all of Volume 4A? What background did you feel you had (or lacked) that helped (or would have helped) you understand the material?

Answer 1

Generally, you only need to read chapter 1 of volume 1 to understand the "MIX" programming language that's used. Without this, some of the algorithm explanation can be hard to follow.

The MIX machine (like all virtual machines) has quirks that are reflected in optimization decisions in the text.

Everything else is designed to either stand alone or have explicit references so you can track down the relevant material.

With an undergraduate degree in CS, I can work out the fine points of most of the algorithms and some (but not all) of the foundational mathematical exposition. The math is not tutorial in nature, it's reference material, so it often relies heavily on the references.

If you're not extending or building on the algorithms, you don't need all of the math.

However, for working out test cases, you will need some of it.

Answer 2

Knuth was trying to make the chapters relatively independent of each other, and succeeded to a large degree in the first three volumes (I haven't caught up on 4A yet). He put the necessary background in the first half of volume 1. You may already know most of this, but if you want to read the machine language stuff you'll need to read about the MMIX virtual computer he uses.

My advice would be to take a quick skim over Chapter 1, so you know more or less what's there, and then dive into 4A. You will find stuff difficult because, well, some of it is difficult. You will likely find other stuff difficult because you need something from Chapter 1, but you can then go and read about the specific stuff you need. You may not hit perfect comprehension that way, but you should pick up a lot of useful stuff.

I think TAOCP would be incredibly useless as a book on CD. It's too dense, and too reliant on diagrams. I've got Feynman's Lectures on CD, and some of the lectures are great and some I really need to see the blackboard, preferably without obscuring my view of the road. Also, there's that thing about Bose-Einstein statistics I missed due to that tricky merge. TAOCP would be worse.