TAOCP 7.1.4 Binary Decision Diagrams (part 1): reading guide

Part 1 covers what BDDs are (compressed, shared decision trees for Boolean functions), why reduced ordered BDDs are canonical, and basic algorithms for counting solutions and finding optimal solutions from a BDD.

Time About 8 hours this week

Why it matters

BDDs are used in hardware verification, model checking, and configuration tools. Knuth has praised them as one of the few truly fundamental data structures to appear in recent decades.

Before you start

7.1.1 Boolean Basics
2.3 Trees

How to approach it

Build BDDs by hand for small functions with different variable orders. Implement a BDD with a unique table (hash consing) and a solution counter.

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 the unique table, which is what makes nodes shared and the BDD canonical.