Knuth
Knuth's exercise ratings explained
Every exercise in The Art of Computer Programming carries a rating from 00 to 50 that estimates how hard it is, roughly on a logarithmic scale. A prefix of M means it is mathematically oriented, HM means it needs higher math such as calculus, and a triangle (▶) means Knuth especially recommends it.
The scale
This is the scale in our own words. Knuth's exact wording is in the "Notes on the Exercises" at the front of each volume, which is worth reading once.
| Rating | What it means | Rough time |
|---|---|---|
| 00 | Immediate if you understood the text; do it in your head | Seconds |
| 10 | Simple; makes you think about what you just read | A minute or so |
| 20 | Average; tests real understanding | Fifteen or twenty minutes |
| 30 | Moderately hard or long | A couple of hours or more |
| 40 | Hard; suitable for a term project | Days |
| 50 | A research problem with no known satisfactory solution when written | Unknown |
The units digit interpolates: a 25 sits between average and moderately hard. The ratings are Knuth's estimate for a reader who has just studied the section, and he says himself that they are personal. Many 20s feel like 30s the first time.
The marks
- M: mathematically oriented. Expect proofs and algebra rather than programming.
- HM: needs higher mathematics, usually calculus or complex analysis, beyond what the book develops. Safe to skip on a first pass if you lack the background.
- ▶ (triangle): recommended. Knuth marks the ones he thinks are especially instructive. If you only do some exercises, do these.
Ratings combine: "▶ M22" is a recommended math exercise of average difficulty.
How many there are
A lot. Using the counts in the cracked.guide reading guides: Volume 1 has 932 exercises, Volume 2 has 918, Volume 3 has 964, Volume 4A has 1498 and Volume 4B has 1202, about 5,500 in all, with a little over a quarter marked recommended. Nobody does them all. See what 5,500 Knuth exercises look like for the breakdown.
How to choose
A rule that keeps you moving:
- Read every 00 to 10 and answer it in your head.
- Do the recommended exercises up to about 25 on paper.
- Pick one 30-ish exercise a week as the stretch, and give it an evening before reading the answer.
- Skip HM unless you have the math and the time.
Each cracked.guide reading guide lists specific picks for that section (number, rating, and why it is worth doing) and lets you log what you solved, with the rating, so you can see the shape of your own progress. Start with §1.1, Algorithms.
Questions
What does HM mean in Knuth's exercises?
Higher mathematics: the exercise needs math beyond the book itself, typically calculus or complex analysis.
What does the triangle mean in TAOCP?
The exercise is recommended: Knuth considers it especially instructive or important.
Has anyone solved a 50?
Some research problems in the books have since been solved by readers, and Knuth updates the exercises and answers in later printings when that happens.
Are the answers in the book?
Yes. Each volume has answers to almost all its exercises at the back, often with extra material. Try first, then read them.