TAOCP Mathematical Preliminaries Redux: reading guide

Vol 4B opens with extra probability tools needed for analyzing randomized and combinatorial algorithms: inequalities that bound how far random quantities stray from their means, and martingales.

Time About 8 hours this week

Why it matters

Tail bounds are how you reason about randomized algorithms, load balancing and hashing guarantees. This is advanced but very useful math.

Before you start

1.2 Mathematical Preliminaries
Probability: expectation, variance

How to approach it

Make a one-page sheet of each inequality with a tiny example. Simulate one in code (e.g. flips of a coin) and compare the actual tail to the bound.

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

Applying an inequality whose conditions (independence, bounded differences) do not hold.