| 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 |