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