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.
|