Instructor
Elena Grigorescu, elena-g purdue.edu
Office Hours: Wed 12:00pm-1
TA: Akash Kumar akash.mnnit gmail.com
Office Hours: Tue 4-5 LWSN 3133.
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).
Prerequisites: A course on discrete math and undergraduate algorithms.