MA 315 - Theory of Computation (CSC 315)
(3 cr.) This course provides an introduction to the classical theory of computer science with the aim of developing a mathematical understanding of the nature of computing by trying to answer one overarching question: What are the fundamental capabilities and limitations of computers? Specific topics include finite automata and formal languages (How do we define a model of computation?), computability (What can be computed? and How do we prove something cannot be computed?) and complexity (What makes some problems so much harder than others to solve? and What is the P versus NP question and why is it important?). Prerequisite: MA 301 or CSC 215; Minimum grade C-; Every Other Year, Fall

Fall 2016