Theory of Computation

Catalog description

In this course we will seek to understand what is and is not possible with modern day computers by using mathematical models to fine-grain study various forms of computation. We will study languages, Turing machines, undecidability, the time complexity classes such as P, NP, NP-complete, space complexity classes such as L and NL, the Cook-Levin theorem, reductions, poly-time hierarchy, randomized algorithms and randomized complexity classes such as BPP, approximation algorithms and hardness of approximation. Strong understanding of undergraduate-level mathematical structures in computer science and theory of computation are expected. Lecture Hours: 3 Repeatability: May be repeated for credit one time. Grade Mode: Normal, Audit College Restrictions: School of Comp & Cyber Science Course Level Restrictions: Graduate Semester Schedule Type (Primary): Lecture Schedule Type (Additional): Asynchronous Instruction Click here for the Schedule of Classes.