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 3000 Formal Languages and Automata.
Prerequisite(s): Grade of "C" or better in either CMPSC 1500 Program Design or MATH 2200 Introduction to Higher Mathematics and junior standing.
MATH 3000 Formal Languages and Automata (3 hours)
See CMPSC 3000 Formal Languages and Automata.
CMPSC 1500 Program Design (4 hours)
A disciplined approach to the development of programs to solve problems on a computer. Topics include data types, control structures, abstraction, and software development. A lab component introduces a high-level programming language and software tools.
Corequisite(s): CMPSC 1000 Introduction to Computational Problem Solving or permission of the instructor.
(Normally offered each spring semester.)
MATH 2200 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 1610 Calculus II or permission of the instructor.
(Normally offered each spring semester.)
