2016-17 Academic Catalog

An introduction to the theory of computation. What problems can and cannot be solved efficiently by computers? What problems cannot be solved by computers, period? Topics include formal models of computation, including finite-state automata, pushdown automata, and Turing machines; formal languages, including regular expressions and context-free grammars; computability and uncomputability; and computational complexity, particularly NP-completeness. Prerequisite: Computer Science 200 or 201 and Computer Science 202 (Mathematics 236 will be accepted in lieu of Computer Science 202)