6.045/18.400
Automata, Computability, and Complexity
Course Home Page
Objectives and Outcomes
Contact Info
General Information/Policies
Calendar
Course Materials by Lecture Date
Introduction and Review
Lecture 1 (Wed Feb 06): Introduction
Reading: Chapter 0
Handout 0,
Student Survey
(
LaTeX source
)
Handout 1,
General Information
(
LaTeX source
)
Homework 1 out, due February 13 at the beginning of class:
Postscript
,
LaTeX source of assignment
,
LaTeX shell
. (Note: LaTeX shell uses the file
6045preamble.tex
for some macros.)
Recitation 1 (Thurs Feb 07): Math Review
Reading: Chapter 0
Handout 2: Math review
(
LaTeX source
)
Finite Automata, Regular Languages, Regular Expressions
Lecture 2 (Mon Feb 11): Deterministic Finite Automata
Deterministic Finite Automata (FA) and the languages they accept
Reading: Section 1.1
Lecture 3 (Wed Feb 13): Nondeterministic Finite Automata
Nondeterministic FA & languages they accept.
Equivalence of DFA and NFA.
Reading: Section 1.2
Homework 1 due. Solutions:
Postscript
,
LaTeX source
.
Homework 2 out, due February 20 at the beginning of class.
Postscript
,
LaTeX source
,
LaTeX shell
(Again, the LaTeX shell uses the file
6045preamble.tex
for some macros.)
In general homework covers material covered up to and including the lecture in which it is handed out.
Recitation 2 (Thurs Feb 14)
Review of FA
Lecture 4 (Tues Feb 19): Regular Expressions
Note: This is a TUESDAY.
Regular Expressions
Lemma 1.29 (Regular expressions describe regular languages)
Reading: Section 1.3
Lecture 5 (Wed Feb 20): More Regular Expressions
Theorem 1.28, Lemma 1.32
Homework 2 due. Solutions:
Postscript
,
LaTeX code
,
Handout 3: Quiz practice problems
(
LaTeX source
)
Recitation 3 (Thurs Feb 21)
Review of regular languages, expressions
Handout 4: Recitation Problems
(
LaTeX source
)
Lecture 6 (Mon Feb 25): End of Automata
Non-regular languages
Pumping lemma
Reading: Section 1.4
Handout 5: Solutions to optional problems
Midterm from Spring 2000
(Note: does not directly correspond to material covered this year.)
Lecture 7 (Wed Feb 27): Quiz 1
Quiz 1
, in class. (
Solutions
)
Covers lectures 1 through 6
Homework 3
out, due March 6 (
LaTeX source
) (
LaTeX shell
)
Recitation 4 (Thurs Feb 28)
Quiz review
Computability Theory
Lecture 8 (Mon Mar 04): Turing Machines
Introduction to Turing Machines
Church-Turing Thesis
Multi-tape Turing Machines
Reading: Chapter 3
Lecture 9 (Wed Mar 06): Non-determinism II
Non-deterministic Turing Machines are no better
Definition of decidable languages; examples
Reading: Section 4.1
Homework 3 due. Solutions: (
PostScript
), (
LaTeX source
)
Homework 4 out, due March 13. (
PostScript
), (
LaTeX source
), (
LaTeX shell
)
Recitation 5 (Thurs Mar 07)
Turing Machines
Handout 9:
Recitation Problems
(
LaTeX source
)
Lecture 10 (Mon Mar 11): Undecidability
The halting problem
The halting problem is undecidable
Reading: Chapter 4.2
Lecture 11 (Wed Mar 13): Undecidability II
Post correspondence problem is undecidable
Reading: Section 5.2
Homework 4 due. Solutions: (
PostScript
) (
LaTeX source
)
Homework 5 out, due March 20 (
Postscript
) (
LaTeX source
)
Recitation 6 (Thurs Mar 14)
Undecidability
Lecture 12 (Mon Mar 18): Undecidability III
More undecidable problems
Counter Machines
Lecture I (page 269) of Kozen
The Game of Life (simulation to be found at
http://www.math.com/students/wonders/life/life.html
)
Lecture 13 (Wed Mar 20): Reductions
Reductions and Mapping Reducibility
Reading: Section 5.3
Rice's Theorem: A photocopy of
Lecture 34
from Kozen was passed out. Extras are to be found in the course locker. (See
General Info
.)
Homework 5 due. Solutions: (
PostScript
) (
LaTeX source
)
Example midterms from previous years:
Midterm from 2000 (with solutions)
Example midterm from 1999
Midterm from 1999 (with solutions)
Midterm from 1998
Recitation 7 (Thurs Mar 21)
Undecidability and recursion
Lecture 14 (Mon Apr 01): End of Computabillity
Computer viruses and undecidability
Lecture 15 (Wed Apr 03): Quiz 2
Quiz 2, in class (
PostScript
) (
PDF
) (
LaTeX source
)
Covers lectures 8 through 14
Quiz 2 solutions: (
PostScript
) (
PDF
) (
LaTeX source
)
Quiz 2a, a make-up test not given out in class (
PostScript
) (
PDF
) (
LaTeX source
)
Homework 6 out, due April 10 (
PostScript
) (
PDF
) (
LaTeX source
)
Recitation 8 (Thurs Apr 04)
Canceled!
Complexity Theory
Lecture 16 (Mon Apr 08): Complexity
Introduction to complexity theory
Time complexity
The class P
Readings: Sections 7.1--7.2
Lecture 17 (Wed Apr 10): Nondeterministic Complexity
The class NP; examples
P vs. NP
Reading: Section 7.3
Homework 6 due. Solutions: (
PostScript
) (
PDF
) (
LaTeX source
)
Homework 7 out, due April 17 (
PostScript
) (
PDF
) (
LaTeX source
)
Recitation 9 (Thurs Apr 11)
Complexity classes
Lecture 18 (Wed Apr 17): NP-Completeness
NP completeness
Poly-time reducibility
Reading: Section 7.4
Homework 7 due. (
PostScript
) (
PDF
) (
LaTeX source
)
Homework 8 out, due April 24. (
PostScript
) (
PDF
) (
LaTeX source
)
Recitation 10 (Thurs Apr 18)
Reductions
Handout 14 given out as problems. (
PostScript
) (
PDF
) (
LaTeX source
)
Lecture 19 (Mon Apr 22): Cook-Levin Theorem
Statement and proof of Cook-Levin theorem
Lecture 20 (Wed Apr 24): NP-Completeness II
Additional NP-complete problems
Reading: Section 7.5
Homework 8 due Solutions: (
PostScript
) (
PDF
) (
LaTeX source
)
Tests and homeworks from previous years, to help you prepare for Quiz 3:
Homework 7 from 2000
Homework 8 from 2000
Sample Final from 2000
Sample Final from 1999
Quiz 2 from 1998
Remember, your Quiz 3 will cover only the material presented in Lectures 16 through 21.
Recitation 11 (Thurs Apr 25)
More on NP-completeness
Handout 16 given out as problems. (
PostScript
) (
PDF
) (
LaTeX source
)
Lecture 21 (Mon Apr 29): NP-Completeness III
Additional NP-complete problems
Lecture 22 (Wed May 01): Quiz 3
Quiz 3, in class (
PostScript
) (
PDF
) (
LaTeX source
)
Covers Lectures 16-21
Quiz 3 solutions: (
PostScript
) (
PDF
) (
LaTeX source
)
Homework 9 out, due April 10 (
PostScript
) (
PDF
) (
LaTeX source
, with the diagram in
LaTeX picture
format and
XFig
format.)
Quiz 3a, a make-up test not given out in class (
PostScript
) (
PDF
) (
LaTeX source
)
Recitation 12 (Thurs May 02)
Optional
lecture on complexity classes beyond NP
Special Topics
Lecture 23 (Mon May 06): Randomness
Probabilistic algorithms
More information about the Min-Cut algorithm can be found at
http://www.cs.ucsd.edu/~russell/RANDCLASS/4notes.ps
Lecture 24 (Wed May 08): Randomness II
Probabilistic algorithms
Handout from
Randomized Algorithms
(Motwani and Raghavan)
given out in class. Extras in course drawer.
Additional material can be found in Section 2 of the scribe notes at
http://icg.harvard.edu/~cs225/Scribenotes/feb25.pdf
Homework 9 due. Solutions: (
PostScript
) (
PDF
) (
LaTeX source
)
Recitation 13 (Thurs May 09)
Probabilistic algorithms
Handout 18 given out as problems. (
PostScript
) (
PDF
) (
LaTeX source
)
Lecture 25 (Mon May 13): Cryptography
Cryptography and complexity theory
Readings: Section 10.6, handout
Lecture 26 (Wed May 15): Cryptography II
Cryptography and complexity theory
Recitation 14 (Thurs May 16)
Canceled!
Final Exam (Monday May 20)
Final exam: 3 hours, 7 problems. (
PostScript
) (
PDF
) (
LaTeX source
)
Jonathan Herzog
NE43-336
x3-5971
<jherzog@mit.edu>
Last modified: Mon Jun 3 15:14:37 EDT 2002
