6.045/18.400 Automata, Computability, and Complexity

Course Home Page General Information/Policies Contact Info Objectives and Outcomes Calendar Course Materials by Lecture Date

Introduction and Review

Lecture 1 (Wed Feb 04): Introduction

• Lecture Time: 11:00am-12:30pm in 37-212.
• Reading: Chapter 0
• Handout 0, Student Survey
• Handout 1, General Information
• Homework 1 out (LaTeX source), due February 11 at the beginning of class. To get started typing up your solutions, use this LaTeX shell for Homework 1. The LaTex shell requires the use of 6045preamble.tex.
• Homework solutions for this class MUST be typed. We highly recommend that you use LaTeX. Here is a useful document on how to use LaTeX. There is also an Athena Minicourse which you may find helpful. One more useful LaTeX website is this one.

Recitation 1 (Thurs Feb 05): Math Review

• Reading: Chapter 0
• Recitation 1: Discussion Materials

Finite Automata, Regular Languages, Regular Expressions

Lecture 2 (Mon Feb 09): Deterministic Finite Automata

• Reading: Section 1.1
• Deterministic Finite Automata (DFA) and the languages they accept.

Lecture 3 (Wed Feb 11): Nondeterministic Finite Automata

• Reading: Section 1.2
• Nondeterministic Finite Automata (NFA) and the languages they accept.
• Homework 1 due. (Solutions)
• Homework 2 out (LaTeX source); will be due on Wednesday Feb 18.

Recitation 2 (Thurs Feb 12): DFAs and NFAs

• Reading: Sections 1.1, 1.2
• Automata
• Recitation 2: Discussion Materials

Lecture 4 (Tue Feb 17): Regular Expressions

• Reading: Section 1.3
• Regular Expressions describe Regular Languages

Lecture 5 (Wed Feb 18): Non-Regular Languages

• Reading: Section 1.4
• Non-regular Languages, Pumping Lemma
• Homework 2 due. (Solutions)
• "Fake" Homework 2.5 out; these problems should be used to practice the material covered in lectures 4 and 5; they will not be due. Try them on your own first and then check your answers with the homework 2.5 solutions.
• Handout 2: Quiz 1 Information and Review Material.
• Handout 3: Sample Quiz 1.
• Handout 4: Sample Quiz 1 Solutions.

Recitation 3 (Thurs Feb 19): Regular Expressions and Non-Regular Languages

• Reading: Sections 1.3, 1.4
• Recitation 3: Discussion Materials

Lecture 6 (Mon Feb 23): Algorithms for Automata

• Reading: Chapter 1, Section 4.1

Lecture 7 (Wed Feb 25): Quiz 1

• Quiz 1, in class: open book (see handout 2 above for details).
• Check out the Quiz 1 Solutions.
• Material covered: Lectures 1 through 6; Chapters 0 and 1.
• Homework 3 out (LaTeX source); will be due on Wednesday, March 3.

Recitation 4 (Thurs Feb 26): Quiz Questions & Automata Wrap-up

• Return Quiz 1 and answer questions.
• Discuss algorithms for automata.
• Recitation 4: Discussion Materials

Computability Theory

Lecture 8 (Mon Mar 01): Turing Machines

• Reading: Chapter 3 (Sections 3.1, 3.3, and 3.2 - except Nondeterminism)
• Introduction to Turing Machines

Lecture 9 (Wed Mar 03): Nondeterministic Turing Machines

• Reading: Section 3.2 (especially pages 138-141), Section 4.2 (especially pages 160-164)
• Homework 3 due (Solutions).
• Homework 4 out (LaTeX source); will be due on Wednesday, March 10.
• Nondeterministic TMs are no more powerful than regular TMs
• Definition of decidable and enumerable languages
• Counting arguments and Cantor's diagonalization

Recitation 5 (Thurs Mar 04): Turing Machines

• Reading: Chapter 3
• Turing Machines
• Recitation 5: Discussion Materials
• Handout 5: Excerpts from Turing's original paper

Lecture 10 (Mon Mar 08): Undecidability

• Reading: Chapter 4 (skip pages 156-158 on context-free languages), Section 5.1 (up to 176)
• The Halting Problem is Undecidable

Lecture 11 (Wed Mar 10): PCP

• Reading: Computation histories (see page 176) and Sections 5.2
• Homework 4 due (Solutions).
• Homework 5 out (LaTeX source); will be due on Wednesday, March 17. Here is an extra hint for problem 2; try to think about the problem on your own first.
• The Post Correspondence Problem is Undecidable

Recitation 6 (Thurs Mar 11): Undecidability

• Reading: Chapter 4 (up to page 176), Sections 5.1 (except 181-182), 5.2
• Practicing with decidability and undecidability
• Recitation 6: Discussion Materials

Lecture 12 (Mon Mar 15): Reducibility

• Reading: Section 5.3, Handout 6
• Handout 6: A photocopy of Lecture 34 from Kozen on Rice's Theorem will be passed out in class.
• Reductions, Mapping Reducibility, Rice's Theorem

Lecture 13 (Wed Mar 17): Recursion Theorem

• Reading: Section 6.1
• The Recursion Theorem
• Homework 5 due. (Solutions)
• "Fake" Homework 5.5 out (Solutions); these problems should be used to practice the material covered in lectures 12, 13 and 14; they will not be due.
• Handout 7: Quiz 2 Information and Review Material.
• Handout 8: Sample Quiz 2.
• Handout 9: Sample Quiz 2 Solutions.

Recitation 7 (Thurs Mar 18): Reducibility, Rice's Theorem and the Recursion Theorem

• Reading: Section 5.3, 6.1, Handout 6
• Recitation 7: Discussion Materials

Lecture 14 (Mon Mar 29): Counter and Stack Machines

• Reading: Handout 10
• Handout 10: a photocopy of Section 8.5 on counter machines from Hoptcroft, Motwani and Ullman will be passed out in class.
• Other machines and undecidability

Lecture 15 (Wed Mar 31): Quiz 2

• Quiz 2, in class.
• Check out the Quiz 2 Solutions.
• Material covered: Lectures 8 through 14; Chapters 3, 4, 5 and 6.1 (except context-free material on pages 156-158 and 181-182).
• Homework 6 out (LaTeX source); will be due on Wednesday, April 7.

Recitation 8 (Thurs Apr 01): Quiz 2 Questions & Computability Wrap-up

• Return Quiz 2 and answer questions.
• Oracle Turing Machines.
• Recitation 8: Discussion Materials.

Complexity Theory

Lecture 16 (Mon Apr 05): Time Complexity

• Reading: Sections 7.1, 7.2
• Time Complexity, The Class P

Lecture 17 (Wed Apr 07): Nondeterministic Time Complexity

• Reading: Section 7.3
• The Class NP, Examples of NP Problems, P vs NP
• Homework 6 due (Solutions).
• Homework 7 out (LaTeX source); will be due on Wednesday, April 14.

Recitation 9 (Thurs Apr 08): P and NP

• Reading: Sections 7.1, 7.2, 7.3
• Definitions and Examples of P and NP Problems
• Recitation 9: Discussion Materials

Lecture 18 (Mon Apr 12): NP-Completeness

• Reading: Sections 7.4 (Except Theorem 7.30)
• Polynomial Time Reductions, Definition of NP-Completeness

Lecture 19 (Wed Apr 14): Cook-Levin Theorem

• Reading: Section 7.4 (Theorem 7.30)
• SAT, 3SAT, and CLIQUE are NP-Complete
• Homework 7 due (Solutions).
• Homework 8 out (LaTeX source); will be due on Wednesday, April 21.

Recitation 10 (Thurs Apr 15): Poly-Time Reductions

• Practicing Polynomial-Time Reductions
• Languages vs Functions
• Recitation 10: Discussion Materials

Lecture 20 (Wed Apr 21): NP-Completeness II

• Reading: Section 7.5, Optional Reading: CLR Chapter 36.5
• HAMPATH, SUBSET-SUM, 3-DIM-MATCHING and many more languages are NP-Complete
• WARNING: the polynomial time reduction of 3SAT to HAMPATH is incorrect in OLD versions of Sipser (i.e., the first printing). The problem is that the diamond gadgets are missing separator nodes.
• Homework 8 due (Solutions).
• "Fake" Homework 8.5 out (Solutions); these problems should be used to practice the material covered in lectures 19, 20 and 21; they will not be due.
• Handout 12: Quiz 3 Information and Review Material.
• Handout 13: Sample Quiz 3.
• Handout 14: Sample Quiz 3 Solutions.
• More Practice Problems for Quiz 3. These are extra problems to help you study SOME (but not all) of the material covered on Quiz 3. No solutions will be provided.

Recitation 11 (Thurs Apr 22): NP-Completeness

• Reading: Section 7.5
• "Harder" polynomial-time reductions, gadgets, and games
• Recitation 11: Discussion Materials

Lecture 21 (Mon Apr 26): Advanced Time Complexity

• Reading: Sections 9.1, 9.2
• Traveling Salesman Problem: Optimization vs Decision
• The Classes: EXP and NEXP
• Oracle Complexity Classes

Lecture 22 (Wed Apr 28): Quiz 3

• Quiz 3, in class.
• Check out the Quiz 3 Solutions.
• Material covered: Lectures 16 through 21; Chapter 7, Sections 9.1, 9.2.
• Homework 9 out (LaTeX source); will be due Wednesday, May 5.

Recitation 12 (Thurs Apr 29): Quiz 3 Questions & End of Time Complexity

• Review Quiz 3 solutions.
• More practice with NP-completeness.
• Recitation 12: Discussion Materials

Lecture 23 (Mon May 03): Space Complexity

• Reading: Sections 8.4, 8.5, 8.6
• Space-Bounded Computation, The Class L, NL = Co-NL

Lecture 24 (Wed May 05): Space Complexity II

• Reading: Sections 8.4, 8.5, 8.6
• Homework 9 due (Solutions).
• "Fake" Homework 10 out (Solutions); these problems should be used to practice the material covered in lectures 23, 24, and 25; they will not be due.

Recitation 13 (Thurs May 06): Space Complexity III

• Reading: Sections 8.4, 8.5, 8.6
• Space Complexity

Lecture 25 (Mon May 10): Probabilistic Complexity

• Reading: Section 10.2
• The Class BPP

Lecture 26 (Wed May 12): Probabilistic Complexity

• Reading: Section 10.2
• The Classes BPP, RP, coRP
• Handout 15: Final Information and Review Material.
• Handout 16: Sample Final.
• Handout 17: Sample Final Solutions.
• "Fake" Homework 11 out (Solutions); these problems should be used to practice the material covered in lectures 25 and 26; they will not be due.

Recitation 14 (Thurs May 13): Probabilistic Complexity and Interactive Proofs

• Optional Reading: Section 10.4
• Interactive Proofs, IP=PSPACE, Final Exam Review

Final Exam Review Session (Sun May 16):

• Optional final exam review session will be held on Sunday, May 16 from 4-6pm in 34-304.
• Study beforehand; come with questions!

Final Exam (Tues May 18):

• Tuesday, May 18, 9:00am-12:00pm (Noon) in 4-231. Be on time!