600.471
Theory of Computation

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


Exams

Quiz 1, on Mon Oct 01
Quiz 2, on Mon Oct 29
Quiz 3, on Mon Dec 03
Final, on Sat Dec 15, 9am-12pm

All exams are open book.
Held in Maryland 310.

Homeworks

H1, due Wed Sep 19
H2, due Wed Sep 26
H3, due Wed Oct 17
H4, due Wed Oct 24
H5, due Mon Nov 19
H6, due Wed Nov 28

Lecture Topics and Readings

Part 1: Automata and Languages

Lecture 1 (Mon Sep 10): Introduction, models of computers, languages, finite automata.
-- Book: 0, 1.1
-- Homework 1 is handed out

Lecture 2 (Wed Sep 12): DFAs and the languages they recognize.
-- Book: 1.1, 1.2

Lecture 3 (Mon Sep 17): NFAs, regular expressions and the languages they recognize.
-- Book: 1.2, 1.3

Lecture 4 (Wed Sep 19): Non-regular languages, the pumping lemma for regular languages.
-- Book: 1.4
-- Homework 1 is due; Homework 2 is out

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

Lecture 6 (Wed Sep 26): Non-context-free languages. Introduction to Turing machines.
-- Book: 2.3
-- Homework 2 is due

Lecture 7 (Mon Oct 1): Quiz 1.
-- In-class quiz covering lectures 1-6, book chapters 1, 2.

Part 2: Computability Theory

Lecture 8 (Wed Oct 3): The Church-Turing Thesis. Basic Turing machines and variations.
-- Book: 3.1-3.3

Lecture 9 (Mon Oct 8): Decidable, recognizable, and enumerable languages.
-- Book: 4.1, 4.2
-- Homework 3 is out

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

Lecture 11 (Mon Oct 15): Fall Break Day
-- No class today, enjoy the fall leaves

Lecture 12 (Wed Oct 17): Undecidability. Computation histories.
-- Book: 5.2.
-- Homework 3 is due; Homework 4 is out

Lecture 13 (Mon Oct 22): Computable functions. Mapping reducibility. Turing reducibility.
-- Book: 5.3, 6.3.

Lecture 14 (Wed Oct 24): Self-referencing machines. The Recursion Theorem. Computer viruses.
-- Book: 6.1
-- Homework 4 is due

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

Part 3: Complexity Theory

Lecture 16 (Wed Oct 31): Time complexity. Asymptotic function notation. Hierarchy Theorems. P. EXPTIME.
-- Lecturer: Omar Zaidan
-- Book: 7.1, 7.2, 9.1.
-- Happy Halloween!

Lecture 17 (Mon Nov 5): Nondeterministic polynomial time, NP. P vs NP.
-- Book: 7.3
-- Homework 5 is out

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

Lecture 19 (Mon Nov 12): Examples of NP-complete languages.
-- Book: 7.5.

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

Lecture 21 (Mon Nov 19): Space complexity. Savitch's Theorem. PSPACE-completeness.
-- Book: 8.1-8.3
--Homework 5 is due; Homework 6 is out

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

Thanksgiving break

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

Lecture 24 (Wed Nov 28): Probabilistically checkable proofs.
-- Homework 6 is due

Lecture 25 (Mon Dec 3): Quiz 3.
-- In-class quiz focusing on lectures 16-24, book chapters 7-10.2.

Lecture 26 (Wed Dec 5): Interactive Proof Systems. The classes IP and AM. Cryptography.
-- Lecturer: Seny Kamara
-- Book: 10.4, 10.6
-- See Seny's excellent slides!

Lecture 27 (Mon Dec 10): Review. Survey of advanced topics.
-- This is the last day of classes.

The cumulative final exam is Saturday, December 15 from 9am-12pm in Maryland 310.

Last modified: Monday, December 10, 2007