An overview of formal models of computation and complexity classes. Topics include formal languages (finite automata, regular expressions, push-down automata, context-free grammars, and Turing machines), Church's thesis, computability, non-determinism, and NP-completeness. Same as MATH 200 Formal Languages and Automata.

*Prerequisite(s): Grade of "C" or better in either CMPSC 100 Discrete Mathematics or MATH 111 Introduction to Higher Mathematics and junior standing.*

(Normally offered alternate years.)

MATH 200 Formal Languages and Automata (3 hours)

See CMPSC 200 Formal Languages and Automata.

CMPSC 100 Discrete Mathematics (3 hours)

An introduction to fundamental concepts of discrete mathematics with application to computer science. Topics include sets, relations, functions, sequences, Boolean algebra, difference equations, combinatorics, and graph theory.

*Prerequisite(s): Placement into MATH 105 Calculus I or grade of "C" or better in MATH 050 Pre-Calculus. *

(Normally offered each year.)

MATH 111 Introduction to Higher Mathematics (3 hours)

A study of mathematical induction and other methods of proof, recursion, formal logic, and set theory.

*Prerequisite(s): Grade of "C" or better in MATH 105 Calculus I.*

(Normally offered each spring semester.)