CS483 Intro to Theory of Computation

Tue/Thr 12-1:15pm

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: TBD

TA: TBD TBD

Office Hours
Announcements

Welcome to CS 483!


Our main class website will be 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, undergraduate level course on the theory of computation. We will start with simple models of computation (DFAs, NFA, PDAs), which would lead into the fundamental mathematical model of a Turing Machine. We will then study computational resources that a TM might use (time, space, randomness) and see many examples of natural problems classified according to their relative complexity.Time permitting, we will also introduce basic notions of quantum computation. Prerequisites: CS 381 or equivalent.
Grading
  • 30% for homeworks(expect bi-weekly)
  • 35% for the midterm
  • 30% for project (read and present papers in the area)
  • 5% for class participation
Schedule (Subject to change)
  • Jan. 10 1. Introduction. Deterministic finite automata. Chap 0, 1.1
  • Jan. 12 2. Nondeterminism. Equivalence of NFAs and DFAs. Closure under regular operations Chap 1.2
  • Jan. 17 3. Pumping Lemma for regular languages
  • Jan. 19 4. Context Free Languages, PDAs, Closure properties.
  • Jan. 24 5. Pumping Lemma for CFL
  • Jan. 26 6. TMs. Robustness of TMs Turing's paper
  • Jan. 31 7. Nondeteministic TMs. Enumerators.
  • Feb. 2 8. Decidability. Decidable langs about DFAs/NFAs/CFGs
  • Feb. 7 8. Undecidability. A diagonalization proof.
  • Feb. 9 9. The undecidability of the halting problem
  • Feb. 14 10. Reductions
  • Feb. 16 11. Mapping reductions. Computational history method
  • Feb. 21 12. Recursion theorem
  • Feb 23 13. Intro to complexity theory.
  • Feb 28 14. P vs NP. Poly-time reducibility
  • Mar 2 15. NP-completeness
  • Mar 7 16. Cook-Levin's theorem
  • Mar 9 17 Space complexity. Savitch's theorem
  • Mar. 14 Spring break
  • Mar. 16 Spring break
  • Mar. 21 18 Review (in class); MIDTERM (8-10pm)
  • Mar. 23 19 PSPACE compleness
  • Mar. 28 20 PSPACE games. Log space computation
  • Mar. 30 21. NL=coNL
  • Apr 4 22. Hierarchy theorems
  • Apr 6 23. Oracles and limits to diagonalization
  • Apr 11 24. Probabilistic complexity classes
  • Apr. 13 25 Polynomial identity testing. Schwarz-Zippel lemma.
  • Apr. 18 26 Quantum computing basics
  • Apr. 20 27 No class-make up for evening midterm
  • Apr. 25 29 Projects
  • Apr. 27 30 Projects