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. |
Official electronic version updated at 10:33 a.m. March 31, 2005