Week 109 of 125
TAOCP 7.2.1.1 Generating All n-Tuples
Sign up or sign in to tick these off and give this week a due date.
-
Generating all n-tuples (like counting in a mixed radix), Gray codes where successive tuples differ in one position, loopless algorithms, and de Bruijn cycles.
Time About 8 hours this week
Why it matters
Gray codes are used in rotary encoders and error minimization; exhaustive generation is a basic tool for testing. Loopless generation teaches tight algorithm design.
Before you start
- 4.1 Positional Number Systems
- 7.1.3 Bitwise tricks
How to approach it
Implement binary counting, reflected Gray code (n XOR n>>1), and a de Bruijn sequence generator. Verify properties by brute force.
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.