Week 83 of 125
TAOCP 5.3.2 and 5.3.3
Sign up or sign in to tick these off and give this week a due date.
-
The fewest comparisons needed to merge two sorted lists of given sizes, with adversary arguments and a binary merging algorithm for unequal sizes (Hwang-Lin).
Time About 5 hours this week
Why it matters
Merging very unequal lists efficiently is useful for set intersection in search engines and databases. Adversary arguments are a powerful proof tool.
Before you start
- 5.3.1 Minimum-Comparison Sorting
How to approach it
Focus on the adversary argument idea and on the binary merge algorithm. Implement binary merging and compare against linear merge when one list is tiny.
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.
-
Finding the k-th smallest element with as few comparisons as possible, including finding the second largest and the linear-time worst-case selection result.
Time About 5 hours this week
Why it matters
Selection (median, percentiles, top-k) is a common real need. The linear-time median-of-medians idea is a classic.
Before you start
- 5.3.1 Minimum-Comparison Sorting
How to approach it
Work out why finding the second largest takes about n + lg n comparisons using a tournament. Implement quickselect and median of medians and compare their speed.
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
- Median of medians is linear but has a big constant; quickselect usually wins in practice.