Wilfrid Laurier University Undergraduate Academic Calendar - 2007/2008
Canadian Excellence

Foundations of Computing
0.5 Credit

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.

Additional Course Information
CP312, MA238.