Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

closed as primarily opinion-based by durron597, Thomas Owens May 18 at 13:32

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

...wait a minute... you mean you actually plan to read it? I thought those things were just for decorating bookshelves! :P –  FrustratedWithFormsDesigner Apr 15 '11 at 18:32
You had to go ahead and create a tag for Knuth ! –  Aditya P Apr 15 '11 at 18:47
@FrustratedWithFormsDesigner The new edition does look quite elegant on the bookshelf just above my office desk, I think. –  Andrew Apr 15 '11 at 18:51
@AdityaGameProgrammer I actually typed "knuth" when tagging the question, thinking for sure that had to be a tag. It wasn't, so I didn't add it. –  Andrew Apr 15 '11 at 18:51
@Andrew: It was me that created the tag. ;) I'm not sure how much rep you need to create new tags... –  FrustratedWithFormsDesigner Apr 15 '11 at 18:56

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
It's MMIX now. Get with the 21st Century! Of course, since everything I program in the real world is x86 or x64, or maybe ARM sometime, MMIX is about as similar to the CPUs I use nowadays as MIX was back then. –  David Thornley Apr 15 '11 at 20:11
@David Thornley: I propose that a CPU be designed that directly supports MMIX opcodes and conforms to the specifications proposed in 1.3 to remedy this problem! –  greyfade Jun 6 '11 at 20:13
To understand MMIX, I'd suggest you to read Volume 1, fascicle 1. The link points to an old edition, but the differences to the latest editions are not very big. (For instance, the purpose of the rC register changed) –  FUZxxl Nov 6 '11 at 12:18

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.