Theory of Computation

Sipser, Michael. Introduction to the Theory of Computation . 3 rd ed. Cengage Learning, 2012. ISBN: 9781133187790.

We will cover Chapters 1, 2 (except 2.4), 3, 4, 5, 6.1, 7, 8, 9.1, 9.2, 10.2 (except the part on Primality), and 10.4 through Theorem 10.33.

This course is taught using Professor Sipser’s textbook:

Sipser, Michael. Introduction to the Theory of Computation . 3rd ed. Cengage Learning, 2012. ISBN: 9781133187790.

LEC #: 1 · TOPICS: Introduction, Finite Automata, Regular Expressions · READINGS: Section 1.1

LEC #: 2 · TOPICS: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata · READINGS: Sections 1.2 and 1.3

LEC #: 3 · TOPICS: The Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs · READINGS: Sections 1.4, 2.0, and 2.1

LEC #: 4 · TOPICS: Pushdown Automata, CFG ↔ PDA · READINGS: Section 2.2

LEC #: 5 · TOPICS: The CF Pumping Lemma, Turing Machines · READINGS: Sections 2.3 and 3.1

LEC #: 6 · TOPICS: TM Variants, the Church-Turing Thesis · READINGS: Sections 3.2 and 3.3

LEC #: 7 · TOPICS: Decision Problems for Automata and Grammars · READINGS: Section 4.1

LEC #: 8 · TOPICS: Undecidability · READINGS: Section 4.2

LEC #: 9 · TOPICS: Reducibility · READINGS: Section 5.1

LEC #: 10 · TOPICS: The Computation History Method · READINGS: Section 5.2

LEC #: 11 · TOPICS: The Recursion Theorem and Logic · READINGS: Sections 6.1 and 6.2

LEC #: 12 · TOPICS: Time Complexity · READINGS: Section 7.1

LEC #: 14 · TOPICS: P and NP, SAT, Poly-time Reducibility · READINGS: Sections 7.2 and 7.3

LEC #: 15 · TOPICS: NP-Completeness · READINGS: Section 7.5

LEC #: 16 · TOPICS: Cook-Levin Theorem · READINGS: Section 7.4

LEC #: 17 · TOPICS: Space Complexity, PSPACE, Savitch’s Theorem · READINGS: Sections 8.1 and 8.2

LEC #: 18 · TOPICS: PSPACE-Completeness · READINGS: Section 8.3

LEC #: 19 · TOPICS: Games, Generalized Geography · READINGS: Section 8.3

LEC #: 20 · TOPICS: L and NL, NL = coNL · READINGS: Section 8.4

LEC #: 21 · TOPICS: Hierarchy Theorems · READINGS: Section 9.1

LEC #: 22 · TOPICS: Provably Intractable Problems, Oracles · READINGS: Section 9.2

LEC #: 23 · TOPICS: Probabilistic Computation, BPP · READINGS: Section 10.2

LEC #: 24 · TOPICS: Probabilistic Computation (cont.) · READINGS: Section 10.2

LEC #: 25 · TOPICS: Interactive Proof Systems, IP · READINGS: Section 10.4

LEC #: 26 · TOPICS: coNP ⊆ IP · READINGS: Section 10.4