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 slides
15 Thursday, 10/19/17 Efficient computation slides HW6
16 Tuesday, 10/24/17 Formally defining running time slides prezi
17 Thursday, 10/26/17 Polynomial time reductions python notebook HW7
18 Tuesday, 10/31/17 Cook Levin Thm notebook
19 Thursday, 11/2/17 discussion of P vs NP powerpoint HW8
20 Tuesday, 11/7/17 Review of probability slides
21 Thursday, 11/9/17 Randomized algorithms slides HW9
22 Tuesday, 11/14/17 Modeling randomized computation slides
23 Thursday, 11/16/17 Crypto slides HW10
24 Tuesday, 11/21/17 Proofs and Algorithms (see these notes) slides
Thursday, 11/23/17 Thanksgiving (no lecture)
25 Tuesday, 11/28/17 Quantum computing slides HW11
26 Thursday, 11/30/17 Course summary powerpoint