CS 372 - Computability and Computational Complexity

Credits: 4
Emphasis on the limits to the power of computation and a systematic analysis of the algorithms that harness it. Topics include the Chomsky hierarchy, several automata and language models, and demonstrations of uncomputable problems, and various design strategies.

Prerequisite(s): CS 158 or ECE 252; MATH 220, MATH 126, or MATH 131; and at least 10 credits in CS.
General Education: Fulfills the Capstone Writing Assignment (CWA) requirement.