2013-2014 Undergraduate and Graduate Bulletin (with addenda) 
    
    Mar 28, 2024  
2013-2014 Undergraduate and Graduate Bulletin (with addenda) [ARCHIVED CATALOG]

CS-GY 6753 Theory of Computation

3 Credits
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.

Prerequisite(s): Graduate status and CS-GY 6003  or instructor’s permission.
Weekly Lecture Hours: 3 | Weekly Lab Hours: 0 | Weekly Recitation Hours: 0