Week 108 of 125
TAOCP 7.1.4 Binary Decision Diagrams (part 2)
Sign up or sign in to tick these off and give this week a due date.
-
Part 2 covers combining BDDs (synthesis with a memo cache), the huge effect of variable ordering, and zero-suppressed decision diagrams (ZDDs) for representing families of sets.
Time About 8 hours this week
Why it matters
Variable ordering can make a BDD tiny or exponential, a great lesson in representation choice. ZDDs are excellent for combinatorial families and come back in Vol 4B.
Before you start
- 7.1.4 part 1
How to approach it
Add AND/OR synthesis with a memo cache to your BDD. Try two variable orders on the same function and watch the size change.
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
- Forgetting to memoize synthesis, which turns a fast operation into an exponential one.