Knuth · Weeks 134 to 145
TAOCP Volume 4B: Combinatorial Algorithms, Part 2
The final stretch: probability tools for analyzing search, backtracking, dancing links for exact cover problems (sudoku, polyominoes and much more), and a deep dive into SAT solving, the technology behind modern verification and constraint solving. You end the path implementing ideas that are still at the research frontier.
Every section, week by week
| Section | Week | Exercises | Picked | Time |
|---|---|---|---|---|
| Mathematical Preliminaries Redux | 134 | 147 (10 to HM34) | 10 | 8 h |
| 7.2.2 Backtrack Programming (part 1) | 135 | 48 (10 to HM42) | 8 | 8 h |
| 7.2.2 Backtrack Programming (part 2) | 136 | 31 (M15 to 41) | 8 | 8 h |
| 7.2.2.1 Dancing Links (part 1) | 137 | 77 (M04 to 47) | 9 | 9 h |
| 7.2.2.1 Dancing Links (part 2) | 138 | 122 | 4 | 5 h |
| 7.2.2.1 Dancing Links (part 3) | 139 | 101 | 4 | 5 h |
| 7.2.2.1 Dancing Links (part 4) | 140 | 150 (10 to HM46) | 8 | 9 h |
| 7.2.2.2 Satisfiability (part 1) | 141 | 118 (01 to M46) | 9 | 9 h |
| 7.2.2.2 Satisfiability (part 2) | 142 | 130 (05 to HM49) | 9 | 9 h |
| 7.2.2.2 Satisfiability (part 3) | 143 | 108 (10 to HM46) | 9 | 10 h |
| 7.2.2.2 Satisfiability (part 4) | 144 | 170 (M10 to M49) | 9 | 8 h |
| Vol 4B review | 145 | 1202 (01 to HM49) | 9 | 5 h |
Each section links to its reading guide: what it covers, how to approach it, exercises picked from the book with their ratings, common traps and links. Picked is how many exercises the guide recommends; time is its budget for the week.
What you will be able to do
- Write fast backtracking searches and estimate their running time before you run them.
- Implement dancing links and use exact cover to model real puzzles and scheduling problems.
- Encode problems as SAT and understand how modern CDCL solvers work.
Before you start
- Vol 4A, especially 7.1.1 and 7.2.1.
- Probability basics (the volume opens with a week reviewing them).
Getting the book
The current edition is the first edition (2023), ISBN 0-201-03806-4.
Vol 4B (2022) is about $64 new from InformIT; used copies are not much cheaper yet. The paperback Fascicles 5 and 6 cover earlier drafts of the same material. Borrow before you buy: many public and university libraries give you free access to O'Reilly Learning, which carries TAOCP; Libby/OverDrive and interlibrary loan (search WorldCat) work too. Older used editions are fine for Vols 1 to 3; section numbers barely changed. If you buy the eBook, get the PDF from InformIT. Knuth himself warns that the Kindle and ePUB versions mangle the math.
What you need has every option with prices, and which edition do I need covers the differences.
Tips
- Watch a couple of Knuth's annual Christmas lectures on dancing links; they are free on YouTube.
- Install a real SAT solver early and play with encodings.
Questions
How long does TAOCP Volume 4B take?
On the cracked.guide path it takes 12 weeks (weeks 134 to 145), about 3 months, and the reading guides budget about 93 hours in all.
How many exercises are in TAOCP Volume 4B?
1202 in the sections the path covers, rated 01 to HM49, and 387 of them carry Knuth's triangle for recommended. Each reading guide picks the ones worth your time.
Which edition of Volume 4B do I need?
The current one is the first edition (2023). There is only one edition; the earlier paperback fascicles are drafts of the same material. Buy the PDF, not Kindle, if you want an eBook.