Theory of computation
Undergraduate · CS / Programming
Syllabus focus
Theoretical / proof-based
Pricing calculator
Choose materials, tutoring, or both — or book a single session as needed. Customize your plan on the subscribe page.
Billed in 15-minute increments (15-minute minimum, up to 4 hours). No subscription required.
$60.00 · 60 min · Undergraduate · Online ($60/hr)
Book through intake or schedule a session.
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)
Notes
Proof-heavy course for CS majors. Often prerequisite for graduate algorithms and cryptography.