| SES # | TOPICS | READINGS |
|---|---|---|
| Introduction and Review | ||
| L1 | Introduction | Chapter 0 |
| R1 | Math Review | Chapter 0 |
| Finite Automata, Regular Languages, Regular Expressions | ||
| L2 | Deterministic Finite Automata (DFA) | Section 1.1 |
| L3 | Nondeterministic Finite Automata (NFA) | |
| R2 | DFAs and NFAs | Sections 1.1, 1.2 |
| L4 | Regular Expressions | Section 1.3 |
| L5 | Non-Regular Languages | Section 1.4 |
| R3 | Regular Expressions and Non-Regular Languages | Sections 1.3, 1.4 |
| L6 | Algorithms for Automata | Chapter 1, Section 4.1 |
| L7 | Quiz 1 | |
| R4 | Quiz Questions and Automata Wrap-up | |
| Computability Theory | ||
| L8 | Turing Machines | Chapter 3 (Sections 3.1, 3.3, and 3.2 - except Nondeterminism) |
| L9 | Nondeterministic Turing Machines | Section 3.2 (especially pp. 138-141), Section 4.2 (especially pp. 160-164) |
| R5 | Turing Machines | Chapter 3 |
| L10 | Undecidability | Chapter 4 (skip pp. 156-158 on context-free languages), Section 5.1 (up to p. 176) |
| L11 | PCP | Computation histories (see p. 176) and Section 5.2 |
| R6 | Undecidability | Chapter 4 (up to p. 176), Sections 5.1 (except pp. 181-182), 5.2 |
| L12 | Counter and Stack Machines | Hopcroft, John, Rajeev Motwani, and Jeffrey Ullman. Introduction to Automata Theory, Languages and Computation. 2nd ed. Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241. |
| L13 | Reducibility | Section 5.3 |
| R7 | Counter and Stack Machines, Reducibility, Rice's Theorem | Section 5.3 Hopcroft, John, Rajeev Motwani, and Jeffrey Ullman. Introduction to Automata Theory, Languages and Computation. 2nd ed. Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241. |
| L14 | Recursion Theorem | Section 6.1 |
| L15 | Quiz 2 | |
| R8 | Quiz 2 Questions and Computability Wrap-up | |
| Complexity Theory | ||
| L16 | Time Complexity | Sections 7.1, 7.2 |
| L17 | Nondeterministic Time Complexity | Section 7.3 |
| R9 | P and NP | Sections 7.1, 7.2, 7.3 |
| L18 | NP-Completeness | Section 7.4 (except Theorem 7.30) |
| L19 | Cook-Levin Theorem | Section 7.4 (Theorem 7.30) |
| R10 | Poly-Time Reductions | |
| L20 | NP-Completeness II | Section 7.5 Optional Reading: Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. Cambridge, MA: MIT Press, 1990, chapter 36.5. ISBN: 0262530910. |
| R11 | NP-Completeness | Section 7.5 |
| L21 | Advanced Time Complexity | Sections 9.1, 9.2 |
| L22 | Quiz 3 | |
| R12 | Quiz 3 Questions and End of Time Complexity | |
| L23 | Space Complexity | Sections 8.4, 8.5, 8.6 |
| L24 | Space Complexity II | Sections 8.4, 8.5, 8.6 |
| R13 | Space Complexity III | Sections 8.4, 8.5, 8.6 |
| L25 | Probabilistic Complexity | Section 10.2 |
| L26 | Probabilistic Complexity (cont.) | Section 10.2 |
| R14 | Probabilistic Complexity and Interactive Proofs | Optional Reading: Section 10.4 |
| Final Exam Review Session (Optional) | ||
| Final Exam | ||
Table of Contents
Study Materials
Readings
 Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses. |
This section contains the weekly reading assignments for the course. Most of the reading assignments refer to the required textbook: Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.