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.