Week 115 of 125
TAOCP 7.2.1.7 and Vol
Sign up or sign in to tick these off and give this week a due date.
-
The long and surprising history of combinatorial generation, going back centuries to poetry, music and bell ringing.
Time About 3 hours this week
Why it matters
A genuinely fun read that shows these ideas are old and human.
Before you start
- 7.2.1.1 to 7.2.1.6
How to approach it
Read for enjoyment. Look up change ringing; it is literally permutation generation with church bells.
Exercises
History sections usually have few or no exercises. Use the week to go back to one earlier exercise you gave up on and finish it.
-
Knuth Knuth Vol 4A review
A review week for Volume 4A: Boolean functions, bitwise tricks, BDDs and generating combinatorial objects.
Time About 5 hours this week
Why it matters
Vol 4B builds directly on backtracking over these objects, and bit tricks and BDD ideas return in dancing links and SAT.
Before you start
- All of Vol 4A
How to approach it
Collect your generators and bit-trick tests into one library. Write a short summary of when to use BDDs.
Exercises
Finish one puzzle-style exercise from 7.2.1 that you skipped.