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 02): Introduction

• Lecture Time: 11:00am-12:30pm in 37-212.
• Reading: Chapter 0
• Handout 0, Student Survey, [ ps | pdf ]
• Handout 1, General Information [ps | pdf ]
• Homework 1 [ ps | pdf | LaTeX source] out, due February 9 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 03): Math Review

• Reading: Chapter 0
• Recitation 1: Discussion Materials [ ps | pdf ]
• Some solutions and notes from the recitation. [ ps | pdf ]

Finite Automata, Regular Languages, Regular Expressions

Lecture 2 (Mon Feb 07): Deterministic Finite Automata

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

Lecture 3 (Wed Feb 9): Nondeterministic Finite Automata

• Nondeterministic Finite Automata (NFA) and the languages they accept.
• Homework 1 due. (Solutions [ ps | pdf ])
• Homework 2 out ( [ ps | pdf | LaTeX source ]); will be due on Wednesday Feb 16. You might want to use the Xfig program to generate some of the figures (of the FAs etc.). Here is a comprehensive Xfig manual.

Recitation 2 (Thurs Feb 10): DFAs and NFAs

• Reading: Sections 1.1, 1.2
• Automata
• Recitation 2: Discussion Materials ([ ps | pdf ])
• Solutions to some problems from the recitation ([ps | pdf ])

Lecture 4 (Mon Feb 14): Regular Expressions

• Reading: Section 1.3
• Regular Expressions describe Regular Languages

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

• Reading: Section 1.4
• Non-regular Languages, Pumping Lemma
• Homework 2 due. (Solutions [ ps | pdf ])
• "Fake" Homework 2.5 [ ps | pdf ] 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 [ ps | pdf ].
• Handout 2: Quiz 1 Information and Review Material [ ps | pdf ].
• Handout 3: Sample Quiz 1 [ ps | pdf ].
• Handout 4: Sample Quiz 1 Solutions [ ps | pdf ].

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

• Reading: Sections 1.3, 1.4
• Recitation 3: Discussion Materials [ ps | pdf ]
• Solutions to some problems from Recitation 3 [ ps | pdf ]

Lecture 6 (Tue Feb 22): Algorithms for Automata

• Reading: Chapter 1, Section 4.1

Lecture 7 (Wed Feb 23): Quiz 1

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

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

• Check out the Quiz 1 Solutions [ ps | pdf ].
• Discuss algorithms for automata.
• Recitation 4: Discussion Materials [ ps | pdf ]

Computability Theory

Lecture 8 (Mon Feb 28): Turing Machines

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

Lecture 9 (Wed Mar 02): Nondeterministic Turing Machines

• Reading: Section 3.2 (especially pages 138-141), Section 4.2 (especially pages 160-164)
• Homework 3 due. Solutions [ ps | pdf ].
• Homework 4 [ ps | pdf | Latex source ] out; will be due on Wednesday, March 9.
• 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 03): Turing Machines

• Reading: Chapter 3
• Turing Machines
• Recitation 5: Discussion Materials [ ps | pdf ]
• Handout 5: Excerpts from Turing's original paper

Lecture 10 (Mon Mar 07): 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 09): PCP

• Reading: Computation histories (see page 176) and Sections 5.2
• Handout 6 : A photocopy of Section 8.5 from "Introduction to Automata Theory, Languages and Computation" by Hopcroft, Motwani and Ullman will be distributed in the class.
• Homework 4 due. Solutions [ ps | pdf ].
• Homework 5 [ ps | pdf | Latex ] out; will be due on Wednesday, March 16.
• The Post Correspondence Problem is Undecidable

Recitation 6 (Thurs Mar 10): 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 [ ps | pdf ]

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

• Reading: Handout 6 on Counter and Stack machines
• Other machines and undecidability

Lecture 13 (Wed Mar 16): Reducibility

• Reading: Section 5.3
• Reductions, Mapping Reducibility, Rice's Theorem
• Homework 5 due. Solutions [ ps | pdf ]
• Fake Homework 5.5 [ ps | pdf ] out. Solutions [ ps | pdf ]; 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 [ ps | pdf ]
• Handout 8: Sample Quiz 2 [ ps | pdf ]
• Handout 9: Sample Quiz 2 Solutions [ ps | pdf ]

Recitation 7 (Thurs Mar 17): Counter and Stack Machines, Reducibility, Rice's Theorem

• Reading: Section 5.3, Handout 6
• Recitation 7: Discussion Materials [ ps | pdf ]

Lecture 14 (Mon Mar 28): Recursion Theorem

• Reading: Section 6.1
• The Recursion Theorem

Lecture 15 (Wed Mar 30): Quiz 2

• Quiz 2, in class.
• Check out the Quiz 2 Solutions [ ps | pdf ].
• 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 [ ps | pdf | Latex source ] out; will be due on Wednesday, April 6.

Recitation 8 (Thurs Mar 31): Quiz 2 Questions & Computability Wrap-up

• Return Quiz 2 and answer questions.
• Oracle Turing Machines.
• Recitation 8: Discussion Materials [ ps | pdf ].

Complexity Theory

Lecture 16 (Mon Apr 04): Time Complexity

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

Lecture 17 (Wed Apr 06): Nondeterministic Time Complexity

• Reading: Section 7.3
• The Class NP, Examples of NP Problems, P vs NP
• Homework 6 due. Solutions [ ps | pdf ].
• Homework 7 out [ ps | pdf | LaTeX source ]. Will be due on Wednesday, April 13.

Recitation 9 (Thurs Apr 07): P and NP

• Reading: Sections 7.1, 7.2, 7.3
• Definitions and Examples of P and NP Problems
• Recitation 9: Discussion Materials [ ps | pdf ]

Lecture 18 (Mon Apr 11): NP-Completeness

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

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

• Reading: Section 7.4 (Theorem 7.30)
• SAT, 3SAT, and CLIQUE are NP-Complete
• Homework 7 due. Solutions [ ps | pdf ].
• Homework 8 out [ ps | pdf | LaTeX source ]. Will be due on Wednesday, April 20.

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

• Practicing Polynomial-Time Reductions
• Languages vs Functions
• Recitation 10: Discussion Materials [ ps | pdf ]

Lecture 20 (Wed Apr 20): 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 [ ps | pdf ].
• Fake Homework 8.5 out [ ps | pdf ]. The solutions to the fake homework [ ps | pdf ]. 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 Materials [ ps | pdf ].
• Handout 13: Sample Quiz 3 [ ps | pdf ].
• Handout 14: Sample Quiz 3 Solutions [ ps | pdf ].
• More Practice Problems [ ps | pdf ] 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 21): NP-Completeness

• Reading: Section 7.5
• 3-Dimensional Matching is NP-complete

Lecture 21 (Mon Apr 25): 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 27): Quiz 3

• Quiz 3, in class.
• Check out the Quiz 3 Solutions [ ps | pdf ].
• Material covered: Lectures 16 through 21; Chapter 7, Sections 9.1, 9.2.
• Homework 9 out. [ ps | pdf | LaTeX source ]. Will be due Wednesday, May 4.

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

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

Lecture 23 (Mon May 02): Space Complexity

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

Lecture 24 (Wed May 04): Space Complexity II

• Reading: Sections 8.4, 8.5, 8.6
• Homework 9 due. Solutions to Homework 9 out. [ ps | pdf ].
• "Fake" Homework 10 out [ ps | pdf ]. These problems should be used to practice the material covered in lectures 23, 24, and 25; they will not be due. Solutions to the fake homework out. [ ps | pdf ]

Recitation 13 (Thurs May 05): Space Complexity III

• Reading: Sections 8.4, 8.5, 8.6
• Space Complexity
• Discussion Material [ps | pdf ]

Lecture 25 (Mon May 09): Probabilistic Complexity

• Reading: Section 10.2
• The Class BPP

Lecture 26 (Wed May 11): Probabilistic Complexity

• Reading: Section 10.2
• The Classes BPP, RP, coRP
• Handout 15: Final Information and Review [ ps | pdf ].
• Handout 16: Sample Final [ps | pdf ].
• Handout 17: Sample Final Solutions [ ps | pdf ].
• Fake Homework 10.5 out. [ ps | pdf ]. These problems should be used to practice the material covered in lectures 25 and 26; they will not be due. Solutions to fake homework 10.5 out. [ ps | pdf ]

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

• Optional Reading: Section 10.4

Final Exam Review Session (Sun May 15):

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

Final Exam (Friday May 20):

• Friday, May 20, 9:00am-12:00pm (Noon) at Walker. Be on time!