Tue/Thr 12-1:15pm Wilmeth Active Learning Center 3132
Instructor
Elena Grigorescu, elena-g purdue.edu
Office Hours: Tue 1:30-2:30 on Zoom
TA: Maoyuan Raymond Song song683 purdue.edu
Office Hours: Wed 1:30-2:30pm on Zoom.
Announcements
Welcome to CS 584!
Our main class website is on Brighspace
Texts
- 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.
Earlier draft
Theory of computation by Dexter Cozen, Springer.
Course description
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).
Grading
- 20% for homeworks (expect bi-weekly)
- 30% for the midterm
- 35% for the final
- 10% for project
- 5% for class participation/quizzes (including LaTeX solutions for requested hw problems--to be shared with the class)