Theory of computation
Undergraduate · CS / Programming
Syllabus focus
Topics typically covered
Theoretical / proof-based
Automata and languages
- Deterministic and nondeterministic finite automata
- Regular expressions and equivalence with DFAs/NFAs
- Pumping lemma for regular languages
- Context-free grammars and pushdown automata
- Pumping lemma for CFLs; closure properties
Computability
- Turing machines and Church–Turing thesis
- Decidable vs undecidable problems
- Reductions and Rice's theorem (intro)
- Recursion theorem overview (optional)
- Post correspondence problem (intro)
Complexity
- Time complexity classes: P, NP, co-NP
- NP-completeness and Cook–Levin theorem (statement)
- Classic NP-complete problems and reductions
- Space complexity: L, NL, PSPACE (intro)
- Approximation and randomized classes (optional survey)
Proof techniques and reductions
- Constructing explicit automata and grammars from specs
- Using pumping lemmas to prove non-regularity/non-CFLness
- Mapping reductions between decision problems
- Diagonalization arguments at introductory level
- Relating decidability, recognizability, and co-recognizability
- Writing reduction proofs with clear correctness arguments
Complexity problem practice
- Proving NP membership via verifiers
- Classic NP-complete problems: SAT, clique, vertex cover, Hamiltonian path
- Polynomial-time reductions as homework craft
- Space vs time tradeoffs with examples
- Approximation algorithms motivation from hardness
- Connecting TOC ideas to compilers and crypto (survey)
Notes
Proof-heavy course for CS majors. Often prerequisite for graduate algorithms and cryptography.