Physics & Computer Science

CP414: Foundations of Computing

Deterministic and nondeterministic finite automata (DFAs and NFAs), regular expressions, context-free grammars, relationship of push-down automata and context-free grammars, definintion of the classes P and NP, NP-completeness (Cook's Theorem), standard NP-complete problems, reduction techniques, Turing machines, the halting problem.

3 lecture hours

Credit: 0.50

Prerequisite: CP312, MA238

Section Information
Section Days Times Room Instructor
Lecture B MWF - Dr. Evgueni Zima