Theoretical / proof-based
Theory of computation · Undergraduate · CS / Programming
Topics
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)
Pricing calculator
Choose materials, tutoring, or both — or book a single session as needed. Customize your plan on the subscribe page.
$1,162 · Theory of computation · 18 tutoring hrs
Study guides, worksheets, reviews, practice tests, and answer keys for 1 class. 18 tutoring hours (1 hr / week · semester). Bundle discount applied vs buying separately. Pay in full via Zelle.