May 25, 2024  
College Catalog 2019-2020 
College Catalog 2019-2020 [ARCHIVED CATALOG]

MATH 361 - Theory of Computation

Cross-Listed as   
This course examines the theoretical foundations of computation. It explores different mathematical models that try to formalize our informal notion of an algorithm. Models include finite automata, regular expressions, grammars, and Turing machines. The course also discusses ideas about what can and cannot be computed. In addition, the course explores the basics of complexity theory, examining broad categories of problems and their algorithms, and their efficiency. The focus is on the question of P versus NP, and the NP-complete set. Prerequisite(s): (COMP 128  or COMP 221 ) and  , or permission of instructor. Alternate spring semesters. (4 Credits)