This is the schedule for the Fall 2018 version Schedule for Fall 2019 will be posted on the summer.
Fall 2018 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|