Week 75 of 125

TAOCP 5.1.3 Runs

Sign up or sign in to tick these off and give this week a due date.

• Knuth Knuth 5.1.3 Runs

  Ascending runs in a permutation, the Eulerian numbers that count permutations by number of runs, and the distribution of run lengths in random data.

  Time About 6 hours this week

  Why it matters

  Natural merge sort and Timsort exploit runs in real data. Knowing how long runs are in random input tells you when that pays off.

  Before you start

  • 5.1.1 Inversions
  • 1.2.6 Binomial Coefficients

  How to approach it

  Generate random permutations and histogram the run lengths, then compare with the formulas. Build a small table of Eulerian numbers by recurrence.

  Exercises

  Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

  Traps

  • Confusing runs up with alternating runs (up-down sequences). They are different statistics.

  Reading guide

• NeetCode LeetCode: 2 NeetCode 150 problems

  Two problems from the NeetCode 150, in order. One box for the pair.