Exams
Quiz 1, on Tue Sep 23
Quiz 2, on Tue Oct 21
Quiz 3, on Tue Nov 25
Final, on Dec 13 at 2-5
All exams are open book.
|
Homeworks
H1, due Thu Sep 18
H2, due Tue Oct 07
H3, due Thu Oct 16
H4, due Tue Nov 11
H5, due Thu Nov 20
|
Lecture Topics and Readings
Part 1: Automata and Languages
- Lecture 1 (Thu Sep 04): Introduction, models of computers, languages, finite automata.
- -- Book: 0, 1.1
- -- Homework 1 is handed out
- Lecture 2 (Tue Sep 09): DFAs, NFAs, regular expressions and the languages they recognize.
- -- Book: 1.2, 1.3
- Lecture 3 (Thu Sep 11): Non-regular languages, the pumping lemma for regular languages.
- -- Book: 1.4
- Lecture 4 (Tue Sep 16): Context-free languages, pushdown automata.
- -- Book: 2.1, 2.2
- Lecture 5 (Thu Sep 18): Non-context-free languages. Introduction to Turing machines.
- -- Book: 2.3
- -- Homework 1 is due
- Lecture 6 (Tue Sep 23): Quiz 1.
- -- In-class quiz covering lectures 1-5, book chapters 1, 2.
Part 2: Computability Theory
- Lecture 7 (Thu Sep 25): The Church-Turing Thesis. Basic Turing machines and variations.
- -- Book: 3.1-3.3
- -- Homework 2 is out
- Lecture 8 (Tue Sep 30): Decidable, recognizable, and enumerable languages.
- -- Book: 4.1, 4.2
- Lecture 9 (Thu Oct 02): Undecidability. The Halting Problem. Non-Turing recognizability.
- -- Book: 4.2, 5.1
- Lecture 10 (Tue Oct 07): Computable functions. Mapping reducibility.
- -- Book: 5.3.
- -- Homework 2 is due; Homework 3 is out
- Lecture 11 (Thu Oct 09): No class today.
- -- No class today, enjoy the fall leaves
- Lecture 12 (Tue Oct 14): Undecidability of a simple game.
- -- Book: 5.2.
- Lecture 13 (Thu Oct 16): Self-referencing machines. The Recursion Theorem. Computer viruses.
- -- Book: 6.1
- -- Homework 3 is due
- Lecture 14 (Tue Oct 21): Quiz 2.
- -- In-class quiz focusing on lectures 7-13, book chapters 3-5, 6.1.
Part 3: Complexity Theory
- Lecture 15 (Thu Oct 23): Time complexity. Asymptotic function notation. Hierarchy Theorems. P. EXPTIME.
- -- Book: 7.1, 7.2, 9.1.
- Lecture 16 (Tue Oct 28): Nondeterministic polynomial time, NP. P vs NP.
- -- Book: 7.3
- -- Homework 4 is out
- Lecture 17 (Thu Oct 30): NP-completeness. The Cook-Levin Theorem. Polynomial-time reducibility.
- -- Book: 7.4
- Lecture 18 (Tue Nov 04): Examples of NP-complete languages.
- -- Book: 7.5.
- Lecture 19 (Thu Nov 06): Optimization vs decision problems. Higher-order and oracle complexity classes.
- -- Book: 9.2, 10.1.
- Lecture 20 (Tue Nov 11): Space complexity. Savitch's Theorem. PSPACE-completeness.
- -- Book: 8.1-8.3
- --Homework 4 is due; Homework 5 is out
- Lecture 21 (Thu Nov 13): The classes L and NL. Log space reducibility and NL-completeness.
- -- Book: 8.4, 8.5
- Lecture 22 (Tue Nov 18): Probabilistic Turing machines. The classes BPP and RP.
- -- Book: 10.2.
- Lecture 23 (Thu Nov 20): Probabilistically checkable proofs.
- -- Homework 5 is due
- Lecture 24 (Tue Nov 25): Quiz 3.
- -- In-class quiz focusing on lectures 15-23, book chapters 7-10.2.
- Lecture 25 (Thu Nov 27): Thanksgiving Break.
- -- No class today, enjoy the holiday
- Lecture 26 (Tue Dec 02): Interactive Proof Systems. The classes IP and ZK. Cryptography.
- -- Book: 10.4, 10.6
- Lecture 27 (Thu Dec 04): No class today.
- -- This is the last day of classes.
- -- See Rebecca about extra office hours on Thursday, December 11 from 10:30am-11:30am.
The cumulative final exam is on Saturday, Dec 13 from 2-5pm in Shaffer 202.
|
