Tentative schedule: (this schedule is a very rough outline, and can and will change)

All lecture notes can be found at introtcs.org. See also preface to the notes.

Note that you will need to read the lecture notes for each lecture before it is given.

The midterm exam is as listed below (during lecture time) and the final exam will be on Thursday, December 14th at 2:00 pm.

Lecture # Date Lectures Slides Pset out
0 (before course) Math background
1 Thursday, 8/31/17 Introduction lec 1 slides HW0
2 Tuesday, 9/5/17 Refreshing some math lec 2 slides
3 Thursday, 9/7/17 Representing objects as strings lec 3 slides HW1
4 Tuesday, 9/12/17 Defining computation lec 4 slides python notebook
5 Thursday, 9/14/17 Syntactic sugar and computing every function notebook HW2
6 Tuesday, 9/19/17 Code as data notebook lec 6 slides
7 Thursday, 9/21/17 Physical implementation lec 7 slides notebook HW3
8 Tuesday, 9/26/17 Loops and infinity lecture 8 slides notebook
9 Thursday, 9/28/17 Universality and indirection slides notebook HW4
Fifth Monday Monday, 10/2/17
10 Tuesday, 10/3/17 Equivalence to other models slides lambda notebook
11 Thursday, 10/5/17 Uncomputability slides halting proof powerpoint no pset (midterm)
12 Tuesday, 10/10/17 Godel’s Incompleteness Theorem slides
13 Thursday, 10/12/17 Midterm HW5
Seventh Monday Monday, 10/16/17
14 Tuesday, 10/17/17 Restricted computational models
15 Thursday, 10/19/17 Efficient computation HW6
16 Tuesday, 10/24/17 Formally defining running time
17 Thursday, 10/26/17 NP HW7
18 Tuesday, 10/31/17 Cook Levin Thm
19 Thursday, 11/2/17 More on NP reductions HW8
20 Tuesday, 11/7/17 discussion of P vs NP
21 Thursday, 11/9/17 Review of probability HW9
22 Tuesday, 11/14/17 Randomized algorithms
23 Thursday, 11/16/17 Modeling randomized computation HW10
24 Tuesday, 11/21/17 Derandomization
Thursday, 11/23/17 Thanksgiving (no lecture)
25 Tuesday, 11/28/17 Crypto Some make up?
26 Thursday, 11/30/17 Quantum computing