CIS-385 Theory of Computation

This course provides an introduction to the classical and contemporary theory of computation. Topics include theory of automata and formal language, computing by Turing machines, Church's thesis, and decision problems. Nondeterminism and NP-hard problems will be considered. Prerequisites: CIS-336 and MAT-254.