This course introduces the theory of computation. Topics: Formal languages and automata theory. Deterministic and non-deterministic finite automata, regular expressions, regular languages, context-free languages. Pumping theorems for regular and context-free languages. Turing machines, recognizable and decidable languages. Limits of computability: the Halting Problem, undecidable and unrecognizable languages, reductions to prove undecidability. Time complexity, P and NP, Cook-Levin theorem, NP completeness.
Prerequisites: Graduate standing and CS 6003 (or instructor’s permission).