Mar 29, 2024  
College Catalog 2018-2019 
    
College Catalog 2018-2019 [ARCHIVED CATALOG]

COMP 261 - 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):   and  , or permission of instructor. Every semester. (4 Credits)