TAOCP Vol 4A: Combinatorial Algorithms, Part 1 · Week 104
TAOCP 7.1.2 Boolean Evaluation: reading guide
Computing Boolean functions with as few gates as possible: Boolean chains, the minimum cost of all functions of four variables, and circuits for specific functions like addition.
Time About 7 hours this week
Why it matters
This is how hardware designers think, and it is the same skill as writing branch-free code. The game Shenzhen I/O touches the same instincts.
Before you start
- 7.1.1 Boolean Basics
How to approach it
Design a full adder with the fewest gates you can, then compare to Knuth. Write a brute-force search for the cheapest chain computing a 3-variable function.
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.