# 6.045/18.400Automata, 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.
• 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

• 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

• 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

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

### Lecture 4 (Mon Feb 14): Regular Expressions

• Regular Expressions describe Regular Languages

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

• 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

• 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

• 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

• 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

• 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

• Time Complexity, The Class P

### Lecture 17 (Wed Apr 06): Nondeterministic Time Complexity

• 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

• 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

• 3-Dimensional Matching is NP-complete

### Lecture 21 (Mon Apr 25): Advanced Time Complexity

• 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

• The Class BPP

### Lecture 26 (Wed May 11): Probabilistic Complexity

• 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 ]