TAOCP 7 Combinatorial Searching intro (part 1): reading guide

Part 1 covers the opening of chapter 7: what combinatorial searching is (finding, counting, generating and optimizing arrangements), illustrated with classic puzzles like Langford pairs and Latin squares, and the warning that clever reformulation can beat brute force by astronomical factors.

Time About 7 hours this week

Why it matters

Combinatorial search is behind schedulers, compilers' register allocators, puzzle solvers and test generators. This intro sets the mindset for the last 26 weeks.

Before you start

Vol 1 to 3
Basic graph vocabulary

How to approach it

Read slowly and play with the puzzles. Write a brute-force Langford pair finder for small n before reading Knuth's smarter ideas. Vol 4 uses MMIX (Knuth's 64-bit RISC machine) instead of MIX where it shows machine code, and much of it is written in plain algorithm steps. You will want MMIX basics (from Vol 1 Fascicle 1 or the MMIX page) for 7.1.3 especially.

Exercises

Vol 4 has a huge number of exercises, many of them fun puzzles. Do the 10 to 20 rated ones for the puzzles you just read about; they are lighter than Vol 1 math.

Traps

Being intimidated by the size of Vol 4A. You are reading selected sections, not all 900 pages.