Courses:

Automata, Computability, and Complexity >> Content Detail



Study Materials



Readings

Amazon logo 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.


SES #TOPICSREADINGS
Introduction and Review
L1IntroductionChapter 0
R1Math ReviewChapter 0
Finite Automata, Regular Languages, Regular Expressions
L2Deterministic Finite Automata (DFA)Section 1.1
L3Nondeterministic Finite Automata (NFA)
R2DFAs and NFAsSections 1.1, 1.2
L4Regular ExpressionsSection 1.3
L5Non-Regular LanguagesSection 1.4
R3Regular Expressions and Non-Regular LanguagesSections 1.3, 1.4
L6Algorithms for AutomataChapter 1, Section 4.1
L7Quiz 1
R4Quiz Questions and Automata Wrap-up
Computability Theory
L8Turing MachinesChapter 3 (Sections 3.1, 3.3, and 3.2 - except Nondeterminism)
L9Nondeterministic Turing MachinesSection 3.2 (especially pp. 138-141), Section 4.2 (especially pp. 160-164)
R5Turing MachinesChapter 3
L10UndecidabilityChapter 4 (skip pp. 156-158 on context-free languages), Section 5.1 (up to p. 176)
L11PCPComputation histories (see p. 176) and Section 5.2
R6UndecidabilityChapter 4 (up to p. 176), Sections 5.1 (except pp. 181-182), 5.2
L12Counter and Stack MachinesHopcroft, 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.
L13ReducibilitySection 5.3
R7Counter and Stack Machines, Reducibility, Rice's TheoremSection 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.
L14Recursion TheoremSection 6.1
L15Quiz 2
R8Quiz 2 Questions and Computability Wrap-up
Complexity Theory
L16Time ComplexitySections 7.1, 7.2
L17Nondeterministic Time ComplexitySection 7.3
R9P and NPSections 7.1, 7.2, 7.3
L18NP-CompletenessSection 7.4 (except Theorem 7.30)
L19Cook-Levin TheoremSection 7.4 (Theorem 7.30)
R10Poly-Time Reductions
L20NP-Completeness IISection 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.
R11NP-CompletenessSection 7.5
L21Advanced Time ComplexitySections 9.1, 9.2
L22Quiz 3
R12Quiz 3 Questions and End of Time Complexity
L23Space ComplexitySections 8.4, 8.5, 8.6
L24Space Complexity IISections 8.4, 8.5, 8.6
R13Space Complexity IIISections 8.4, 8.5, 8.6
L25Probabilistic ComplexitySection 10.2
L26Probabilistic Complexity (cont.)Section 10.2
R14Probabilistic Complexity and Interactive ProofsOptional Reading: Section 10.4
Final Exam Review Session (Optional)
Final Exam

 








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