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

• Reading: Chapter 0
• Lecture Time: 11:00am in 37-212.
• Handout 0, Student Survey (LaTeX source)
• Handout 1, General Information (LaTeX source)
• Homework 0 out, due February 12 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 0, this should make it easier to LaTeX your homework solutions. The LaTex shell requires the use of 6045preamble.tex.
• Homework solutions for this class MUST be typed. We 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 you want to learn LaTeX. One more useful LaTeX website is this one .

Recitation 1 (Thurs Feb 06): Math Review

• Reading: Chapter 0
• Recitation 1: Discussion Questions ( Answers )
• Recitation Times: 10:00am in 34-302. 1:00pm and 4:00pm in 34-304.
• TA Office Hours are Monday 5-6pm, Tuesday 1-2pm and Tuesday 4:30-6:00pm. Office Hours will meet in the 3rd floor lounge in building NE43.

Finite Automata, Regular Languages, Regular Expressions

Lecture 2 (Mon Feb 10): Deterministic Finite Automata

• Reading: Chapter 1.1
• Lecture is now in room 37-212.
• Deterministic Finite Automata (DFA) and the languages they accept.

Lecture 3 (Wed Feb 12): Nondeterministic Finite Automata

• Reading: Chapter 1.2
• Nondeterministic Finite Automata (NFA) and the languages they accept.
• Homework 0 due. (Homework 0 Solutions)
• Homework 1 out, due February 19 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 1.

Recitation 2 (Thurs Feb 13): DFAs and NFAs

• Reading: Chapter 1.1, 1.2
• Recitation 2: Discussion Questions

Lecture 4 (Tues Feb 18): Regular Expressions

• Note: This Lecture was Canceled Due to Snow

Lecture 5 (Wed Feb 19): More Regular Expressions

• Reading: Section 1.3
• Regular Expressions
• Lemma 1.29 (Regular Expressions describe Regular Languages)
• Theorem 1.28, Lemma 1.32
• Homework 1 due. (Solutions)
• Here is a copy of Last Year's Quiz 1. (Solutions)

Recitation 3 (Thurs Feb 20)

• Reading: Section 1.3
• Review of regular languages, expressions
• Recitation 3: Discussion Questions. ( Answers )

Lecture 6 (Mon Feb 24): End of Automata

• Reading: Section 1.4
• Non-regular languages
• Pumping lemma
• Helpful Information on Quiz #1.

Lecture 7 (Wed Feb 26): Quiz 1

• Quiz 1, in class.
• Covers Lectures 1 through 6
• Covers Chapters 0 and 1 in the text
• Homework 2 out, due March 5 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 2. You will need this file, 6045-hw2file.txt to do the last problem on the assignment.

Recitation 4 (Thurs Feb 27)

• Reading: Section 1.4
• Review of non-regular languages
• Review of questions from Quiz 1

Computability Theory

Lecture 8 (Mon Mar 03): Turing Machines

• Reading: Chapter 3
• Introduction to Turing Machines
• Church-Turing Thesis
• Multi-tape Turing Machines

Lecture 9 (Wed Mar 05): Decision, Enumeration and Non-determinism

• Reading: Section 4.1
• Definition of decidable languages
• Definition of enumerable languages
• Non-deterministic Turing Machines are no more powerful than regular Turing Machines
• Homework 2 due.
• Homework 3 out, due March 12 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 3.

Recitation 5 (Thurs Mar 06)

• Reading: Chapter 3 and 4.1
• Turing Machines
• Recitation 5: Discussion Questions.
• Excerpts from Turing's original paper

Lecture 10 (Mon Mar 10): Undecidability

• Reading: Section 4.2
• The halting problem
• The halting problem is undecidable

Lecture 11 (Wed Mar 12): Undecidability II

• Post correspondence problem is undecidable
• Reading: Section 5.2
• Homework 3 due. (Solutions)
• Homework 4 out, due March 19 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 4.

Recitation 6 (Thurs Mar 13)

• Reading: Chapter 4.2 and 5.2
• Decidable and Undecidabile Languages
• Recitation 6: Discussion Questions.

Lecture 12 (Mon Mar 18): Undecidability III - Counter Machines

• Counter Machines: A photocopy of Section 8.5 from Hoptcroft, Motwani and Ullman was passed out.

Lecture 13 (Wed Mar 19): Reductions

• Reading: Section 5.3
• Reductions and Mapping Reducibility
• Rice's Theorem: A photocopy of Lecture 34 from Kozen was passed out.
• Homework 4 due. (Solutions)
• Here is a copy of Last Year's Quiz 2. (Solutions)

Recitation 7 (Thurs Mar 20)

• Reading: Section 5.3 and Handouts
• Reducibility
• Recitation 7: Discussion Questions.

Lecture 14 (Mon Mar 31): End of Computabillity

• Reading: Section 6.1
• The Recursion Theorem
• Helpful Information on Quiz #2.

Lecture 15 (Wed Apr 02): Quiz 2

• Quiz 2, in class.
• Homework 5 out, due April 9 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 5.

Recitation 8 (Thurs Apr 03)

• Review of Questions from Quiz 2

Lecture 16 (Mon Apr 7): Intro to Complexity

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

Lecture 17 (Wed Apr 9): Non-Deterministic Complexity

• Reading: Section 7.3
• The Class NP. Examples of NP Problems
• P vs NP
• Homework 5 due.
• Homework 6 out, due April 16 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 6.

Recitation 9 (Thurs Apr 10)

• Reading: Sections 7.4 (Except Theorem 7.30)
• Definitions and Examples of P and NP
• Recitation 9: Discussion Questions.

Lecture 18 (Mon Apr 14): NP-Completeness

• Reading: Sections 7.1 and 7.2
• Polynomial Time Reductions
• Definition of NP-Completeness

Lecture 19 (Wed Apr 16): The Cook-Levin Theorem

• Reading: Section 7.4 (Theorem 7.30)
• SAT is NP-Complete
• Homework 6 due.
• Homework 7 out, due April 23 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 7.

Recitation 10 (Thurs Apr 17)

• Examples of Polynomial-Time Reductions

Lecture 20 (Wed Apr 23): More NP-Completeness

• Reading: Section 7.5
• 3SAT is NP-Complete
• CLIQUE is NP-Complete
• Lecture Interrupted To Celebrate Ron's Turing Award
• Here is a copy of Last Year's Quiz 3. (Solutions)

Recitation 11 (Thursday Apr 24)

• Hamiltonian Path is NP-Complete
• Helpful Information on Quiz #3.

Lecture 21 (Mon Apr 28): End of NP-Completeness

• Reading: Section 7.5
• SUBSET-SUM is NP-Complete
• Partition is NP-Complete
• Optimization vs Decision

Lecture 22 (Wed Apr 30): Quiz 3

• Quiz 3 in Class
• Homework 8 out, due May 7 at the beginning of class: Postscript, LaTeX source of assignment. A LaTeX shell for Homework 8.

Recitation 12 (Thurs May 1)

• Review of Questions from Quiz 3

Special Topics

Lecture 23 (Mon May 5): 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 7): Randomness II

• Reading: Section 10.2
• Randomized Complexity Classes
• BPP is contained in P/Poly
• Additional material can be found in Section 2 of the scribe notes at http://icg.harvard.edu/~cs225/Scribenotes/feb25.pdf
• Homework 8 Due. (Solutions)

Recitation 13 (Thurs May 8)

• Randomized Complexity Classes
• Recitation 13: Handout on Randomized Complexity Classes.

Lecture 25 (Mon May 12): Space Complexity

• Reading: Sections 8.4, 8.5, 8.6
• Space-Bounded Computation and the Class Log-Space (L)
• NL = Co-NL

Lecture 26 (Wed May 14): Space Complexity

• Reading: Sections 8.4, 8.5, 8.6
• More on Space Complexity
• Here is a copy of Last Year's Final Exam.

Recitation 14 (Thurs May 8)

• Final Review
• Here is another practice final: Conflict Version of This Year's Final

Last modified: Wednesday Feb 5 2003