Tue/Thr 10:30am-11:45am LWSN B134
Elena Grigorescu, elena-g purdue.edu
Office Hours: TBD
TA: Ruiqi Gao
Office Hours: TBD.
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
- 30% for the final
- 15% for project
- 5% for class participation