MTH 307Discrete Structure II
Computer Science & Mathematics · 3 credits
Description
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. Course Learning Outcomes:
Common questions about MTH 307
What is MTH 307 at LAU?
MTH 307 Discrete Structure II is a 3-credit course at Lebanese American University (LAU), in the Computer Science & Mathematics department. 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…
How many credits is MTH 307?
MTH 307 Discrete Structure II is worth 3 credits at LAU.