Theory of Computation

Catalog description

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-GY 6003 (or instructor’s permission). | Knowledge of discrete math (equivalent to CS-GY 6003 ). Prerequisite: Graduate Standing.