Tue/Thr 9am-10:15am LWSN 1106
Elena Grigorescu, elena-g purdue.edu
Office Hours: Tue 10:30-11:30
TA: Ruiqi Gao
Office Hours: Wed 12-1pm.
Welcome to CS 584!
Our main class website is on Brighspace
- Introduction to the Theory of Computation
(3rd edition) by Michael Sipser, Cengage Learning.
- Recommended: Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press.
Theory of computation by Dexter Cozen, Springer.
This is an introductory, graduate-level course on the theory of computation.
We will focus on the fundamental mathematical model of a Turing Machine, discuss its powers and limitations,
discuss computational resources that a TM might use (time, space, randomness)
and the complexity classes associated with them (P, NP, PSPACE, BPP, RP, etc).
In the second part of the course we'll cover more advanced topics, possibly including Interactive Proofs (IP, PCP).
- 20% for homework(expect bi-weekly)
- 30% for the midterm
- 35% for the final
- 15% for project