Readings

This course is taught using Professor Sipser's textbook:

Buy at Amazon 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