Schedule

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

The textbook can be found at introtcs.org.

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

The midterm exams are listed below (during lecture time) and the final exam will be on December 13th 2-5pm.

See the reading guidelines for each chapter to know what parts you can skip or skim.

Lecture # Day Date Lectures Pset published
0 (before course) Math background 0
1 Tue Tuesday, September 4, 2018 Introduction
2 Thu Thursday, September 6, 2018 Representing objects as strings 1
3 Tue Tuesday, September 11, 2018 Defining computation
4 Thu Thursday, September 13, 2018 Syntactic sugar and computing every function 2
5 Tue Tuesday, September 18, 2018 Code as data
6 Thu Thursday, September 20, 2018 Loops and infinity 3
7 Tue Tuesday, September 25, 2018 Equivalence to other models
8 Thu Thursday, September 27, 2018 Uncomputability 4 (two weeks)
9 Tue Tuesday, October 2, 2018 Recap, regroup, and prepare
10 Thu Thursday, October 4, 2018 Midterm 1 (lectures 1-8)
11 Tue Tuesday, October 9, 2018 Restricted computational models
12 Thu Thursday, October 11, 2018 Godel’s Incompleteness Theorem 5
13 Tue Tuesday, October 16, 2018 Efficient computation
14 Thu Thursday, October 18, 2018 Formally defining running time 6
15 Tue Tuesday, October 23, 2018 Polynomial time reductions
16 Thu Thursday, October 25, 2018 Cook Levin Thm 7
17 Tue Tuesday, October 30, 2018 discussion of P vs NP
18 Thu Thursday, November 1, 2018 Review of probability 8
19 Tue Tuesday, November 6, 2018 Randomized algorithms
20 Thu Thursday, November 8, 2018 Modeling randomized computation 9 (10 days)
21 Tue Tuesday, November 13, 2018 Recap, regroup, and prepare
22 Thu Thursday, November 15, 2018 Midterm 2 (lectures 11-21)
23 Tue Tuesday, November 20, 2018 Crypto (pset 9 due)
Thu Thursday, November 22, 2018 No lecture - Thanksgiving
24 Tue Tuesday, November 27, 2018 Proofs and Algorithms (see these notes)
25 Thu Thursday, November 29, 2018 Quantum computing 10 (cumulative, final prep)
26 Tue Tuesday, December 4, 2018 Algorithms and society, course summary