CS483 Intro to the Theory of Computation

Tu/Th 12-1:15 pm, LWSN 1106

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Tue 1:30-2:30 LWSN 1209

Announcements

Welcome to CS 483!

Please sign up on Piazza for class discussions.

Text book
  • Introduction to the Theory of Computation (3rd edition) by Michael Sipser, Cengage Learning.
    • 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). We will then 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).

    Prerequisites: Mathematical maturity.

    Grading
    • 40% for homeworks
    • 25% for the midterm
    • 30% for the final
    • 5% for class participation.
    Schedule
    • Jan. 10 1. Introduction. Deterministic finite automata. Chap 0, 1.1
    • Jan. 12 2. Nondeterminism. Chap 1.2
    • Jan. 17 3. Equivalence of NFAs and DFAs. Closure under regular operations
    • Jan. 19 4. Regular expressions. Equivalence with NFAs.
    • Jan. 24 5. Pumping Lemma for regular languages
    • Jan. 26 6. Context Free Languages, PDAs, Closure properties.
    • Jan 31. 2 7. Pumping Lemma for CFL
    • Feb 2. 2 7. Pumping Lemma for CFL
    • Feb. 7 8. TMs. Robustness of TMs Turing's paper
    • Feb. 9 8. Nondeteministic TMs. Enumerators.
    • Feb. 14 9. Decidability. A diagonalization proof.
    • Feb. 16 10. Decidable langs about DFAs/NFAs/CFGs
    • Feb. 21 11. The undecidability of the halting problem
    • Feb. 23 12. More undecidable languages. Reductions
    • Feb 28
    • Mar 2 13. Mapping reductions
    • Mar 4 14.Recursion theorm
    • Mar 9 15. Review
    • Mar 11 16.Midterm (In class)
    • Mar 16 Spring break
    • Mar. 18 Spring break
    • Mar. 23 17 Intro to complexity theory. HW5
    • Mar. 25 18 P
    • Mar. 30 19 NP
    • Apr. 4 20 Poly-time reducibility
    • Apr. 6 21.NP-completeness
    • Apr 11 22. Cook-Levin's theorem
    • Apr 13 23. More NP-completeness
    • Apr 18 24 Space complexity. Savitch's theorem
    • Apr. 23 25 PSPACE compleness
    • Apr. 25 26 PSPACE games. Log space computation
    • Apr. 30 27 Hierarchy theorems
    • Apr. 28 29 Review
    • May 3 30 FINAL 8-10am LWSN 1106