Sep 27, 2023  
College Catalog 2023-2024 
    
College Catalog 2023-2024

COMP 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  or COMP 124 if previously taken) and  , or permission of instructor. Alternate years. (4 Credits)