Knuth · Weeks 118 to 133
TAOCP Volume 4A: Combinatorial Algorithms, Part 1
Volume 4A is Knuth at his most playful: puzzles, graphs, Boolean functions, bit tricks, binary decision diagrams, and efficient ways to generate every tuple, permutation, combination, partition and tree. It uses MMIX instead of MIX where it shows machine code, but most of it is plain algorithm steps.
Every section, week by week
| Section | Week | Exercises | Picked | Time |
|---|---|---|---|---|
| 7 Combinatorial Searching intro (part 1) | 118 | 145 (M00 to 50) | 8 | 7 h |
| 7 Combinatorial Searching intro (part 2) | 119 | 145 (M00 to 50) | 8 | 8 h |
| 7.1.1 Boolean Basics (part 1) | 120 | 133 (05 to M48) | 8 | 7 h |
| 7.1.1 Boolean Basics (part 2) | 121 | 133 (05 to M48) | 8 | 8 h |
| 7.1.2 Boolean Evaluation | 122 | 88 (15 to 47) | 8 | 7 h |
| 7.1.3 Bitwise Tricks and Techniques (part 1) | 123 | 218 (10 to 47) | 8 | 8 h |
| 7.1.3 Bitwise Tricks and Techniques (part 2) | 124 | 218 (10 to 47) | 8 | 8 h |
| 7.1.4 Binary Decision Diagrams (part 1) | 125 | 267 (05 to M47) | 8 | 8 h |
| 7.1.4 Binary Decision Diagrams (part 2) | 126 | 267 (05 to M47) | 8 | 8 h |
| 7.2.1.1 Generating All n-Tuples | 127 | 112 (10 to HM48) | 8 | 8 h |
| 7.2.1.2 Generating All Permutations | 128 | 113 (M15 to 48) | 8 | 8 h |
| 7.2.1.3 Generating All Combinations | 129 | 111 (M01 to M49) | 8 | 7 h |
| 7.2.1.4 Generating All Partitions | 130 | 73 (15 to 47) | 8 | 7 h |
| 7.2.1.5 Generating All Set Partitions | 131 | 82 (14 to HM46) | 8 | 6 h |
| 7.2.1.6 Generating All Trees | 132 | 124 (05 to HM46) | 8 | 8 h |
| 7.2.1.7 History and Further References | 133 | 32 (10 to M40) | 7 | 4 h |
| Vol 4A review | 133 | 1498 (M00 to 50) | 8 | 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
- Use bitwise and broadword tricks fluently in C.
- Build and use BDDs and ZDDs.
- Generate combinatorial objects in Gray-code orders and test code exhaustively with them.
- Solve 2SAT and Horn satisfiability in linear time.
Before you start
- Vols 1 to 3.
- MMIX basics from Vol 1 Fascicle 1 or Knuth's MMIX page, mainly for 7.1.3.
Getting the book
The current edition is the first edition (2011), ISBN 0-201-03804-8.
Vol 4A is about $64 new from InformIT. It is too new to be dirt cheap used. The paperback Fascicles 0 to 4 contain earlier drafts of the same material and sometimes turn up cheap used. 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
- Vol 4A is huge; you are reading selected sections, not all of it.
- The exercises are full of puzzles. Pick the ones that make you curious.
Questions
How long does TAOCP Volume 4A take?
On the cracked.guide path it takes 16 weeks (weeks 118 to 133), about 4 months, and the reading guides budget about 122 hours in all.
How many exercises are in TAOCP Volume 4A?
1498 in the sections the path covers, rated M00 to 50, and 452 of them carry Knuth's triangle for recommended. Each reading guide picks the ones worth your time.
Which edition of Volume 4A do I need?
The current one is the first edition (2011). 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.