Theory of Computation

A course that covers basics of Automata and Language Theory, Computation Theory, and Complexity Theory. Topics include regular expressions, finite automata, context-free grammars and parsing, pushdown automata, closure properties, Turing machines, Church’s thesis, reductions and decidability, time complexity and NP-completeness, space complexity, polynomial-space and log-space computations, circuit complexity, probabilistic computations and complexity classes, approximation algorithms, and selected topics as time permits.