Theory of Computation

3 Credits.

This course covers the theoretical foundations of computer science. Topics included will be models of computation from automata to Turing machines, computability, complexity theory, randomized algorithms, inapproximability, interactive proof systems and probabilistically checkable proofs. Students may not take both 601.231 and 601.431/601.631, unless one is for an undergrad degree and the other for grad.