CS 273
Intro to Theory of Computation

Credit: 3 hours.

This course satisfies the General Education Criteria for a
Quant Reasoning II course.

Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; computability and the halting problem; undecidable problems; computational complexity and NP-completeness. Prerequisite: CS 125 and either CS 173 or MATH 213.