CSC380 Theory of Computation

[3–0, 3 cr.]

This course covers elementary computability, the classes P and NP, NP-completeness (Cook’s theorem), problem-reduction techniques, automata theory including deterministic and nondeterministic finite automata, equivalence of DFAs and NFAs, regular expressions, the pumping lemma for regular expressions, context-free grammars, Turing machines, nondeterministic Turing machines, sets and languages, the halting problem, Chomsky hierarchy, and the Church-Turing thesis. 

Prerequisite: CSC245 Objects and Data Abstraction.