CP414 Foundations of Computing 0.5 |
Deterministic and nondeterministic finite automata (DFAs and NFAs), regular expressions, context-free grammars, relationship of push-down automata and context-free grammars, definition of the classes P and NP, NP-completeness (Cook's theorem), standard NP-complete problems, reduction techniques, Turing machines. The halting problem. |
Prerequisite: CP312, MA238. |
DRAFT electronic version updated at 1:45 p.m. January 30, 2003