Operating-Systems

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.

Peterson's algorithm and Lamport's bakery. Correct mutual exclusion from plain reads and writes, and why modern hardware still breaks it (see Memory models and...

Four conditions, all necessary for deadlock; break any one. The cleanest example of a characterization theorem doing engineering work.