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

• Lecture Time: 11:00am-12:30pm in 32-144.
• Reading: Chapter 0
• Handout 0, Student Survey, [ ps | pdf ]
• Handout 1, General Information [ps | pdf ]
• Homework 1 [ ps | pdf | LaTeX source] out, due February 12 at 5PM. 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. One more useful LaTeX website is this one.

Recitation 1 (Thurs Feb 08): Math Review

• Reading: Chapter 0
• Recitation 1: Discussion Materials [ ps | pdf ]

Finite Automata, Regular Languages, Regular Expressions

Lecture 2 (Mon Feb 12): Deterministic Finite Automata

• Reading: Section 1.1
• Deterministic Finite Automata (DFA) and the languages they accept.
• Homework 1 due. (Solutions [ ps | pdf ])
• Homework 2 out ( [ ps | pdf | LaTeX source ]); will be due on Tue Feb 20. You might want to use the Xfig program to generate some of the figures (of the FAs etc.). Here is a comprehensive Xfig manual.

Lecture 3 (Wed Feb 14): Nondeterministic Finite Automata

• Nondeterministic Finite Automata (NFA) and the languages they accept.

Recitation 2 (Thurs Feb 15): DFAs and NFAs

• Reading: Sections 1.1, 1.2
• Automata
• Recitation 2: Discussion Materials ([ ps | pdf ])

Lecture 4 (Tue Feb 20): Regular Expressions and FA-recognizable languages.

• Reading: Section 1.3
• Regular Expressions describe Regular Languages
• Homework 2 due. (Solutions [ ps | pdf ])
• Homework 3 handed out [ ps | pdf | LaTeX source ]; will be due on Monday, February 26.

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

• Reading: Section 1.4
• Handout 4: Practice Quiz 1 [ pdf ]
• Non-regular Languages, Pumping Lemma

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

• Reading: Sections 1.3, 1.4
• Recitation 3: Discussion Materials [ ps | pdf ]

Lecture 6 (Mon Feb 26): Algorithms that answer questions about FAs and regular expressions.

• Reading: Chapter 1, Section 4.1
• Homework 3 due. Solutions [ ps | pdf ].
• Homework 4 [ pdf | Latex source ] out; will be due on Monday, March 5.
• Fake Homework 3.1 [ pdf ] handed out
• Solutions to Fake Homework 3.1 [ pdf ]
• Solutions to Practice Quiz 1 [ pdf ]

Lecture 7 (Wed Feb 28): Quiz 1

• Quiz 1, closed-book, closed-notes. However, you are allowed to bring one sheet of paper with review notes.
• Material covered: Lectures 1 through 6; Chapters 0 and 1.

Recitation 4 (Thurs Mar 1): Quiz Questions & Automata Wrap-up

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

Computability Theory

Lecture 8 (Mon Mar 05): Turing Machines

• Reading: Chapter 3 (Sections 3.1, 3.3, and 3.2 - except Nondeterminism)
• Introduction to Turing Machines and computability. Basic Turing machines. Some variations.
• Homework 4 due. Solutions [ ps | pdf ].
• Homework 5 handed out [ ps | pdf | Latex ] out; will be due on Monday, March 12.

Lecture 9 (Wed Mar 07): Nondeterministic Turing Machines

• Reading: Section 3.2 (especially pages 138-141), Section 4.2 (especially pages 160-164)
• Decidable languages vs. recognizable languages. Enumerable languages.
• Nondeterministic Turing machines.
• Turing machines that answer questions about FAs and regular expressions.

Recitation 5 (Thurs Mar 08): 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 12): Undecidability

• Reading: Chapter 4 (skip pages 156-158 on context-free languages), Section 5.1 (up to 176)
• Undecidability. The Halting Problem. A non-Turing-recognizable language.
• Homework 5 due. Solutions [ ps | pdf ]
• Homework 6 handed out [ ps | pdf | Latex source ] out; will be due on Monday, March 19. The Halting Problem is Undecidable

Lecture 11 (Wed Mar 14): 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. NOT AVAILABLE ON THE WEB.
• Undecidability. Computation histories. Post Correspondence Problem.

Recitation 6 (Thurs Mar 15): 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 19): Counter and Stack Machines

• Reading: Handout 6 on Counter and Stack machines
• Undecidability. Counter machines. Stack machines.
• Homework 6 due. Solutions [ ps | pdf ].
• Homework 7 out [ ps | pdf | LaTeX source ]. Will be due on Monday, April 2.

Lecture 13 (Wed Mar 21): Reducibility

• Reading: Section 5.3
• Computable functions. Mapping reducibility.
• Applications of mapping reducibility to show undecidability and non-recognizability.
• Rice's Theorem. Applications of Rice's Theorem to show undecidability.
• Handout 8: Practice Quiz 2 [ pdf ]
• Practice Quiz 2 Solutions [ pdf ]

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

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

Lecture 14 (Mon Apr 2): Recursion Theorem

• Reading: Section 6.1
• Self-referencing machines. The Recursion Theorem. Applications of the Recursion Theorem.
• Homework 7 due. Solutions [pdf ].
• Fake Homework 7.1 handed out [ pdf ].
• Solutions to Fake Homework 7.1 [ pdf ].
• Homework 8 out [ pdf | LaTeX source ]. Will be due on Monday, April 9.

Lecture 15 (Wed Apr 4): Quiz 2

• Quiz 2, in class.
• Check out the Quiz 2 Solutions [ 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).

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

• Oracle Turing Machines.
• Recitation 8: Discussion Materials [ ps | pdf ].

Complexity Theory

Lecture 16 (Mon Apr 9): Time Complexity

• Reading: Sections 7.1, 7.2
• Complexity theory. Time complexity analysis. Asymptotic function notation. Time complexity classes.
• P, Polynomial time.
• Homework 8 due. Solutions [ ps | pdf ].
• Homework 9 out. [ ps | pdf | LaTeX source ]. Will be due Wednesday, Apr 18.

Lecture 17 (Wed Apr 11): Nondeterministic Time Complexity

• Reading: Section 7.3
• Hierarchy theorems.
• NP, Nondeterministic Polynomial time. Examples of NP problems.
• P vs. NP.

Recitation 9 (Thurs Apr 12): 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 (Wed Apr 18): NP-Completeness

• Reading: Sections 7.4 (Except Theorem 7.30)
• Polynomial-time reducibility.
• Examples: Clique and Vertex Cover. NP-completeness.
• Homework 9 due. Solutions to Homework 9 out. [ ps | pdf ].
• Homework 10 out [ ps | pdf| LaTeX source ]. Will be due Monday, April 23. Solutions to the fake homework out.

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

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

Lecture 19 (Mon Apr 23): Cook-Levin Theorem

• Reading: Section 7.4 (Theorem 7.30)
• SAT, 3SAT, and CLIQUE are NP-Complete
• Homework 10 due. Solutions [ ps | pdf ]
• Homework 11 out. [ pdf| LaTeX source ].

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

• Reading: Section 7.5, Optional Reading: CLR Chapter 36.5
• More NP-complete problems. Traveling Salesman, Multiprocessor Scheduling

Recitation 11 (Thurs Apr 26): NP-Completeness III

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

Lecture 21 (Mon Apr 25): Advanced Time Complexity

• Reading: Sections 9.1, 9.2
• Still more NP-complete problems.
• Survey of other topics in computability: Optimization vs. decision problems. Higher-order complexity classes. Oracle complexity classes.
• Homework 11 due. Solutions [ pdf ]
• Homework 12 handed out. [ pdf| LaTeX source ].
• Fake Homework 11.1 handed out [ pdf]
• Solutions to fake Homework 11.1 [ pdf]
• Practice Quiz 3. [ pdf].
• Solutions to Practice Quiz 3. [ pdf].

Lecture 22 (Wed May 02): Quiz 3

• Quiz 3, in class.
• Check out the Quiz 3 Solutions [ pdf ].
• Material covered: Lectures 16 through 21; Chapter 7, Sections 9.1, 9.2.

Recitation 12 (Thurs May 03): Quiz 3 Questions & End of Time Complexity

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

Lecture 23 (Mon May 07): Space Complexity

• Reading: Sections 8.4, 8.5, 8.6
• Space complexity. Deterministic vs. nondeterministic space complexity classes (Savitch's Theorem).
• Polynomial space and Pspace-completeness. TQBF. TQBF is Pspace-complete.
• Homework 12 due. Solutions [ pdf ].
• Fake Homework 12.1 handed out [ pdf ].
• Solutions to Fake Homework 12.1 [ pdf ].

Lecture 24 (Wed May 09): Space Complexity II

• Reading: Sections 8.4, 8.5, 8.6
• L, Log space. NL, Nondeterministic Log space.
• Extension of Savitch's theorem to smaller space bounds.
• Log space reducibility and NL-completeness. PATH is NL-complete. NL vs. P and coNL.

Recitation 13 (Thurs May 10): Space Complexity III

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

Lecture 25 (Mon May 14): Probabilistic Complexity

• Reading: Section 10.2
• Probabilistic Turing machines. PPT Turing machines.
• Probabilistic time complexity classes, BPP and RP.
• Example: Primality testing.
• Fake Homework 12.2 handed out [ pdf ].
• Solutions to Fake Homework 12.2 [ pdf ].

Lecture 26 (Wed May 16): Probabilistic Complexity

• Reading: Section 10.2
• Probabilistic time complexity classes.
• Example: Branching-program equivalence.
• Relationships among classes.
• Wrapup.
• Handout 16: Sample Final [ pdf ].
• Handout 17: Sample Final Solutions [ pdf ].

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

• Optional Reading: Section 10.4

Final Exam Review Session (Wed May 23):

• Optional final exam review session will be held on Wed May 23rd from 5-7pm ( Place: 6th floor of Stata -the usual office hours place).
• Study beforehand; come with questions!

Final Exam (Fri May 25)

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