| | DFAs, NFAs, Regular Expressions |
| | Regular languages, Pumping lemma for Regular Languages, Myhill-Nerode |
| | CFGs, PDAs, Pumping Lemma for CFGs, CKY algorithm |
| | Turing Machines, (Un)decidability |
| | P, NP, and NP-completeness |
| | coNP, PSPACE, PSPACE-completeness |
| | L, NL, logspace reductions |
| | Oracles, Alternation |
| | Proabilistic computation |
| | Approximation and optimization |