Week 73 of 125

TAOCP 5.1.1 Inversions

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

• Knuth Knuth 5.1.1 Inversions

  An inversion is a pair of elements that are out of order. Knuth studies the inversion table of a permutation, which encodes it uniquely, and counts how many permutations have a given number of inversions, with generating functions.

  Time About 7 hours this week

  Why it matters

  The number of inversions is exactly how much work insertion sort and bubble sort do, and counting inversions is a classic merge-sort interview problem.

  Before you start

  • 1.2.5 Permutations
  • 1.2.9 Generating Functions
  • 1.3.3 Applications to Permutations

  How to approach it

  Compute inversion tables for several permutations of 1..5 by hand and convert back. Write code for both directions. Then count inversions in O(n log n) with a modified merge sort.

  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

  • There are several conventions for inversion tables. Stick to Knuth's within this volume.

  Reading guide

• NeetCode LeetCode: 2 NeetCode 150 problems

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