Week 118 of 125
TAOCP 7.2.2 Backtrack Programming (part 2)
Sign up or sign in to tick these off and give this week a due date.
-
Part 2 covers making backtracking practical: estimating the size of a search tree before running it (with random probes), symmetry breaking, and larger case studies.
Time About 8 hours this week
Why it matters
Estimating search cost is a superpower: you can tell in seconds whether a search will take a minute or a million years.
Before you start
- 7.2.2 part 1
- Mathematical Preliminaries Redux
How to approach it
Implement random-probe estimation for your n-queens search and compare estimates to real counts.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Trusting a single random estimate; average many.