Automata & Formal Languages
Regular and context-free languages: the machines that recognise them and the limits of each.
Computability
Turing machines and the halting problem: what no program can decide, and why.
Computational Complexity
P, NP and NP-hard: what a problem class says about the algorithm you can expect.