Advice on how to approach The Art of Computer Programming?

Question

Any advice on how to appoach The Art of Computer Programming Vol 1?

I currently have Volume 1 with me. Should I go through the Math part fully before getting in to the Data Structures part?

Answer 1

I would:

• buy all volumes
• put in big plastic bag with some lumps of coal and shake vigourously for 20 mins
• you should now have authentically used looking copies
• go through them all. underlining paragraphs and writing things like "how true!" in the margins
• put them in an obvious place in your office bookshelf.

Answer 2

Take it step by step, like hiking up a mountain. Pick stuff up along the way, and don't dismiss things outright that seem like they won't be useful, they just might.

I've found my "gut" instinct on how to solve a problem and create a solution is frequently overshadowed by learning something I didn't have when I first considered the problem. I like to let my mind "chew" on a problem for a while in the back of my mind, let myself fall back and recharge after hyperfocusing on something for too long, in addition to looking for alternative ways to do something.

Sometimes it can be very helpful to know about as many possible paths you can take towards solving a given problem.

Answer 3

I think you have to be careful with Knuth. He gives a "Procedure for Reading This Set of Books" on page xiii, where he recommends at least scanning the first two chapters. Sections marked "*" can be omitted. Unless you are "mathematically inclined" (I'd say a graduate Math student) then you can skip the derivations.

I'd be very careful about recommending these books to anyone, I'm only on page 260 of Volume 1, but I'm too stubborn to skip anything even though I'm not "mathematically inclined". It isn't that they aren't good, they are near perfect. But it is slow going and not as immediately rewarding as reading a "light" book on algorithms that explains things in easier language. To see what I mean, compare the descriptions of the heap sort algorithm in Volume 3 (page 145, section 5.2.3) versus wikipedia's version. These books demand the right kind of student.

However, the answers are so canonical that if someone is ready for them, then there is nothing else like Knuth. And the books remain suprisingly relevant despite their age. A couple years ago I consulted the algorithms on how to sort on tape drives, as I was having to do sort data that did not fit in memory, and so I had to do the sort using the two disk drives that were available. There is also a new Volume 4, broken up into Fascicles, that might be more relevant to modern algorithms.

Knuth is as close to a perfect, abstract truth as computer science gets. Rather like how "1+1=2" is true regardless of which planet you are on, the material in TAOCP is true regardless of the platform that you may be dealing with even if in some cases it may not be terribly relevant... at least not directly relevant. See the section on sorting with multiple tape drives.

If you are interested in it for what it can teach you about your problem today, then you probably want to consult something else. Reading Knuth is a deep dive into algorithms; it is not a quick fix for what ails you.

Another answer's comment might be taken to suggest that Knuth is not useful. Heresy! Here's my list of times I've used it.. admittedly not a long list, but I'm young yet:

• 1.2.11.1 The O notation: Hopefully you already know this before you read Knuth.
• 1.4.2 Coroutines: What Python means by the "yield" statement.
• 5.3 Optimum Sorting: Which sort algorithm as a function of what your bottleneck is.
• 5.4 External Sorting: for when you don't have enough memory to store your set in memory, but you still need it sorted fast.

One final note: be sure you don't skip the exercises: that is were a lot of the material lies.

Answer 4

Do not start with Chapter 1. In fact, I'd recommend you not even start with Volume 1.

In my opinion, the best place for newcomers to start is Volume 4, Fasciscle 0. The concepts there are more closely related to the kinds of algorithms you are probably used to in your daily programming, and you can later go back in fill in the lower levels.

If you do want to start with Volume 1, I'd begin with Chapter 2, and refer back to Chapter 1 if you need to brush up with the math fundamentals. (Alternately, Knuth's "Concrete Mathematics" will help here, since things are fleshed out there differently.)

Don't get too wrapped up in the MIX implementations-- those are being replaced by MMIX implementations in some future edition; you can see Volume 1 Fascicle 1 for the details there.

Finally: do at least some of the exercises. For those you don't do, read the exercise and the answer carefully, and try to follow the details.

Edit, added 6/26

Since the original question has been rephrased to ask specifically about Volume 1, I'll add some more advice specific to that volume.

Chapter 2 is structured as follows:

• 2.1 Introduction
• 2.2 Linear Lists
• 2.3 Trees
• 2.4 Multilinked Structures
• 2.5 Dynamic Storage Allocation
• 2.6 History and Bibliography

As you can guess, the meat of the chapter is found in sections 2.2 and 2.3.

You'll notice that Knuth tends to divide things into chunks of about 5 pages, followed by Exercises. For example, Section 2.1 is pages 232-237, including 9 exercises. The first part of 2.1, section 2.2.1 (on Stacks, Queues and Deques) is pages 238-243, including 14 exercises. And so on.

It helps to focus on each chunk separately. In the case of Chapter 2, Knuth has flagged two of these (2.3.4.3, on The "infinity lemma", and 2.3.4.6 History and Bibliography on Trees) as "specialized topics that are interesting but not essential." I'd recommend taking his advice, and not spending much time on those two chunks the first time through.

Now, in approaching each chunk, first read through the text quickly, to get the main concepts. Don't worry at this point if you don't fully grok things-- just try to get the flow. In doing so, you'll probably notice which notation (either mathematical or MIX/MMIX-related) you aren't familiar with. Look these things up in Chapter 1 or Fascicle 1, as appropriate.

Now, read through a second time, and actually try to understand the details. I find it useful to work through the Algorithms on paper with a pencil, on a simple test case. It might not be a bad idea to implement them in your favorite language, which I'm guessing is not MIX/MMIX. (There are 8 algorithms in the text prior to hitting trees. There are 13 for trees, and then 9 in the remainder of the chapter.)

An aside about MIX/MMIX: a common response to MIX is "Why does Knuth insist on using something so low-level? I don't write code like that!" The obvious response, of course, is "Yes, you do-- you're just shielded from it by your tools." If you're a .NET programmer, take a look at the IL code the compiler emits for your C#/VB/F#/Python/Ruby/Whatever implementation of your algorithm. There you go.

At this point, you should try your hand at some of the exercises. Read all of the exercises and answers carefully-- there's a lot of good stuff there.

If, at this point, you're still confused, post a question to StackOverflow about it.

And then, move on to the next chunk.

Answer 5

Approach it with an eye to the long-term. Alexander Stepanov, creator of STL recommends it as one of only two books for his students:

"The books that I recommend to my students are The Art of Computer Programming by Donald Knuth, which is the great encyclopedia of programming techniques. ... It is something that they should keep studying for the rest of their lives. The other book that I urge my students to read is The Textbook of Algebra by George Chrystal. It is a massive two volume work covering most of elementary algebra. Sadly enough, nowadays even people with graduate degrees in Mathematics do not know most of the material in Chrystal."