CSCI 5110 - Theory of Computation (3 Credit Hours)In this course we will seek to understand what is and is not possible with modern daycomputers by using mathematical models to fine-grainly 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.
Lecture Hours: 3
Repeatability: May not be repeated for credit.
Grade Mode: Normal, Audit
Schedule Type (Primary): Lecture
Click here for the Schedule of Classes.
Add to Catalog Bookmarks (opens a new window)
|
