MTH307 Discrete Structures II

[3–0, 3 cr.]

This course covers computational complexity and order analysis, recurrence relations and their solutions, graphs and trees, elementary computability, classes P and NP problems, NP-completeness (Cook’s theorem), NP-complete problems, reduction techniques, automata theory including deterministic and nondeterministic finite automata, equivalence of DFAs and NFAs, regular expressions, the pumping lemma for regular expressions, context-free grammars, Turing machines, nondeterministic Turing machines, sets and languages, uncomputable functions, the halting problem, implications of uncomputability, Chomsky hierarchy, and the Church-Turing thesis.

Prerequisites: MTH207 Discrete Structures I, and MTH201 Calculus III