2013-2014 Undergraduate and Graduate Catalog (without addenda) 
    
    Aug 14, 2020  
2013-2014 Undergraduate and Graduate Catalog (without addenda) [ARCHIVED CATALOG]

Add to Portfolio (opens a new window)

CS 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 6003  or instructor’s permission.
Weekly Lecture Hours: 3 | Weekly Lab Hours: 0 | Weekly Recitation Hours: 0



Add to Portfolio (opens a new window)