600.471
Theory of Computation

Course Home Page
General Information/Policies
Course Materials by Lecture Date


Please note that this schedule is subject to change.

Exams

Quiz 1, on Wed Sep 23
Quiz 2, on Mon Oct 26
Quiz 3, on Wed Dec 02
Final, on Thu Dec 17

All exams are open book.

Homeworks

H1 LaTeX, out 09/09, due 09/21
H2 LaTeX, out 09/30, due 10/07
H3 LaTeX, out 10/07, due 10/19
H4 LaTeX, out 11/02, due 11/16
H5 LaTeX, out 11/16, due 11/23

Lecture Topics and Readings

Part 1: Automata and Languages

Lecture 1 (Wed Sep 02): Introduction, models of computers, languages, finite automata.
-- Book: 0, 1.1

Lecture 2 (Mon Sep 07): Labor Day.
-- No class today, enjoy the holiday.
Lecture 3 (Wed Sep 09): DFAs, NFAs, regular expressions and the languages they recognize.
-- Book: 1.2, 1.3

Lecture 4 (Mon Sep 14): Non-regular languages, the pumping lemma for regular languages.
-- Book: 1.4

Lecture 5 (Wed Sep 16): Context-free languages, pushdown automata.
-- Book: 2.1, 2.2

Lecture 6 (Mon Sep 21): Non-context-free languages. Introduction to Turing machines.
-- Book: 2.3

Lecture 7 (Wed Sep 23): Quiz 1.
-- In-class quiz covering lectures 1-6, book chapters 1, 2.

Part 2: Computability Theory

Lecture 8 (Mon Sep 28): Review of Quiz 1. The Church-Turing Thesis.
-- Book: 3.1.

Lecture 9 (Wed Sep 30): Basic Turing machines and variations.
-- Book: 3.1-3.3

Lecture 10 (Mon Oct 05): Decidable, recognizable, and enumerable languages.
-- Book: 4.1, 4.2

Lecture 11 (Wed Oct 07): Undecidability. The Halting Problem. Non-Turing recognizability.
-- Book: 4.2, 5.1

Lecture 12 (Mon Oct 12): Undecidability of a simple game.
-- Book: 5.2.

Lecture 13 (Wed Oct 14): Computable functions. Mapping reducibility.
-- Book: 5.3.

Lecture 14 (Mon Oct 19): Self-referencing machines. The Recursion Theorem. Computer viruses.
-- Book: 6.1.

Lecture 15 (Wed Oct 21): Review of Part 2 material.
-- Book: 3-5, 6.1.

Lecture 16 (Mon Oct 26): Quiz 2.
-- In-class quiz focusing on lectures 8-14, book chapters 3-5, 6.1.

Part 3: Complexity Theory

Lecture 17 (Wed Oct 28): Review of Quiz 2. Time complexity. Asymptotic function notation. P. EXPTIME.
-- Book: 7.1, 7.2.

Lecture 18 (Mon Nov 02): Hierarchy Theorems. Nondeterministic polynomial time, NP. P vs NP.
-- Book: 7.3, 9.1.

Lecture 19 (Wed Nov 04): NP-completeness. The Cook-Levin Theorem. Polynomial-time reducibility.
-- Book: 7.4

Lecture 20 (Mon Nov 09): Examples of NP-complete languages.
-- Book: 7.5.

Lecture 21 (Wed Nov 11): Optimization vs decision problems. Higher-order and oracle complexity classes.
-- Book: 9.2, 10.1.

Lecture 22 (Mon Nov 16): Space complexity. Savitch's Theorem. PSPACE-completeness.
-- Book: 8.1-8.3

Lecture 23 (Wed Nov 18): The classes L and NL. Log space reducibility and NL-completeness.
-- Book: 8.4, 8.5

Lecture 24 (Mon Nov 23): Probabilistic Turing machines. The classes BPP and RP.
-- Book: 10.2.

Lecture 25 (Wed Nov 25): Thanksgiving Break.
-- No class today, enjoy the holiday

Lecture 26 (Mon Nov 30): Interactive Proof Systems. The classes IP and ZK.
-- Book: 10.4, 10.6

Lecture 27 (Wed Dec 02): Quiz 3.
-- In-class quiz focusing on lectures 16-26, book chapters 7-10.6.

Lecture 28 (Mon Dec 07): Review of Quiz 3. Wrap Up.
-- This is the last day of classes.


The cumulative final exam is Thursday, December 17 in Shaffer 202 from 9-12.

Last modified: Monday, November 16, 2009