Algorithms

A stable matching always exists and is findable in O(n^2), but it's optimal for the proposing side. Mechanism design in twenty lines.

The exact structural condition under which greedy is provably correct. Answers "when can I just be greedy?" once and for all.

The bottleneck equals the capacity, exactly. A duality result you can see, and the workhorse behind matching and segmentation.

The constant factors that dominate asymptotics in practice, and cache-oblivious algorithms as the theoretical response.

The unimplementable best cache policy, and the proof that LRU is k-competitive with it. The application of Competitive analysis and ski rental, so it follows it.

How to reason about decisions made without the future, with a provable ratio. Rent-vs-buy shows up in caching, autoscaling, and connection pooling.

A randomized scheduler with a provable bound on both time and space, and why every modern runtime converged on it.

SAT is NP-complete (The Cook–Levin theorem) yet solvers handle millions of variables.

A named theory result sitting in the middle of every compiler backend, plus why the NP-hardness does not stop anyone. Part V's counterweight to all the type theory.

Beyond P vs NP: why your O(n^2) string algorithm is probably optimal too.

"NP-hard" hides that some hard problems are easy when one parameter is small. The most practically useful refinement of Karp's 21 problems.

The positive side: 2-approximate vertex cover, PTAS, and where the approximability cliff sits.

Exact distinct-count needs linear space; approximate needs almost none. HyperLogLog and Count-Min as the constructive half.

What a hash function actually guarantees, as opposed to what it seems to do.

Thousands of unrelated-looking problems are secretly the same problem.

And the proof is an exchange argument you can follow. Opens with Kraft (The Kraft inequality and prefix codes): which length assignments exist at all, then which...

Averages of independent things are exponentially unlikely to stray.

Why a dynamic array's O(n) resize is still O(1) per push, and how to prove it rather than hand-wave it.

Lower bounds by playing against the algorithm: finding max and second-max needs n + ceil(log n) - 2 comparisons.

Expectations add even when events are hopelessly dependent. Averaging as an existence proof: if the mean is 5, some input hits 5.