This course is taught using Professor Sipser's textbook:
Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Thomson Course Technology, 2006. ISBN: 0534950973.
Please see the table of contents for both the first and second editions. (PDF)
There is an errata for 2nd edition of textbook.
Key to Notation
Section x.0 refers to chapter x's introductory text appearing prior to the first numbered section (x.1)
SES # | TOPICS | READINGS |
---|---|---|
1 | Introduction, Finite Automata, Regular Expressions |
Review all chapter 0. Read sections 1.0, 1.1, and 1.3 (first part). |
2 | Nondeterminism, Closure Properties, Regular Expressions ↔ FA | Sections 1.2 and 1.3. |
3 | Regular Pumping Lemma, Context Free Languages | Sections 1.4, 2.0, and 2.1. |
4 | Pushdown Automata, CFG ↔ PDA | Section 2.2. |
5 | CF Pumping Lemma, Turing Machines | Sections 2.3, 3.0, and 3.1. |
6 | TM Variants, Church-turing Thesis | Sections 3.2 and 3.3. |
7 | Decision Problems for Automata and Grammars | Sections 4.0 and 4.1. |
8 | Undecidability | Section 4.2. |
9 | Reducibility | Sections 5.0, 5.1, and 5.3. |
10 | Linearly Bounded Automata, PCP | Section 5.1 and 5.2. |
11 | Recursion Theorem and Logic | Sections 6.0, 6.1, and 6.2 (first part). |
12 | Time Complexity | Sections 7.0 and 7.1. |
13 | Midterm Exam | |
14 | P and NP, SAT, Poly-time Reducibility | Sections 7.2 and 7.3. |
15 | NP-completeness | Section 7.4 (first part). |
16 | Cook-Levin Theorem | Sections 7.4 and 7.5. |
17 | Space Complexity | Section 8.0. |
18 | PSPACE, TQBF, Savitch's Theorem | Sections 8.1, 8.2, and 8.3 (first part). |
19 | Games, Generalized Geography | Section 8.3. |
20 | L and NL, NL= coNL | Sections 8.4, 8.5 and 8.6. |
21 | Hierarchy Theorems | Sections 9.0 and 9.1. |
22 | Provably Intractable Problems, Oracles | Sections 9.0 and 9.2. |
23 | Probabilistic Computation, BPP | Section 10.2 (first part). |
24 | Probabilistic Computation (cont.) | Section 10.2. |
25 | Interactive Proof Systems, IP | Section 10.4. |
26 | Topic | |
27 | Final Exam |