Courses:

Theory of Computation >> Content Detail



Study Materials



Readings

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

This course is taught using Professor Sipser's textbook:

Amazon logo 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 #TOPICSREADINGS
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.
4Pushdown Automata, CFG ↔ PDASection 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.
7Decision Problems for Automata and GrammarsSections 4.0 and 4.1.
8UndecidabilitySection 4.2.
9ReducibilitySections 5.0, 5.1, and 5.3.
10

Linearly Bounded Automata, PCP

Section 5.1 and 5.2.
11Recursion Theorem and LogicSections 6.0, 6.1, and 6.2 (first part).
12Time ComplexitySections 7.0 and 7.1.
13Midterm Exam
14

P and NP, SAT, Poly-time Reducibility

Sections 7.2 and 7.3.
15NP-completenessSection 7.4 (first part).
16Cook-Levin TheoremSections 7.4 and 7.5.
17Space ComplexitySection 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.
20L and NL, NL= coNLSections 8.4, 8.5 and 8.6.
21Hierarchy TheoremsSections 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).
24Probabilistic Computation (cont.)Section 10.2.
25Interactive Proof Systems, IPSection 10.4.
26Topic
27Final Exam

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.