Wilfrid Laurier University Undergraduate Academic Calendar - 2011/2012
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.