Week 30 of 125
TAOCP 1.3.3 Applications to Permutations
Sign up or sign in to tick these off and give this week a due date.
-
Permutations written in cycle notation, how to multiply them, and how to invert a permutation in place in memory, with MIX programs and analysis. It mixes the math from 1.2 with the programming from 1.3.
Time About 8 hours this week
Why it matters
In-place permutation and cycle-following are real techniques: think in-place array rotation, transposing matrices, and shuffling. The analysis also introduces counting cycles in random permutations.
Before you start
- 1.3.2 The MIX Assembly Language
- 1.2.5 Permutations and Factorials
How to approach it
Do several cycle-notation multiplications by hand until you can do them fast. Then implement in-place inversion of a permutation array in C or Python before reading the MIX version. Compare approaches.
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
- Multiplying permutations in the wrong order. Knuth composes left to right; many textbooks do the opposite.
- Forgetting to mark visited elements when following cycles in place.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.