Fall 2019 Schedule: (this schedule is still tentative, and can change)
The textbook can be found at introtcs.org.
The midterm exams are listed below and will be held at 7pm. Lecture that day will be a review lecture. See the syllabus for policies on missing midterms and make ups.
You will need to do the reading corresponding to each lecture the same week it is given, and do a short weekly multiple-choice quiz on the reading. The weekly quizzes will be available on the Ed platform.
See the reading guidelines for each chapter to know what parts you can skip or skim.
Click here for a Google calendar of all CS 121 sections/office hours/activities.
Links below are to the PDF versions of the chapters. You can get HTML versions as well as a PDF of the entire book on introtcs.org.
See Madhu’s posts on Ed for all information and schedule of the project.
|Lecture #||Day||Date||Lectures||Pset out||Pset due|
|1||Tue||Tuesday, September 3, 2019||Introduction|
|2||Thu||Thursday, September 5, 2019||Review math background|
|3||Tue||Tuesday, September 10, 2019||Representing objects as strings||0|
|4||Thu||Thursday, September 12, 2019||Defining computation|
|5||Tue||Tuesday, September 17, 2019||Syntactic sugar and computing every function||1|
|6||Thu||Thursday, September 19, 2019||Code as data|
|7||Tue||Tuesday, September 24, 2019||Loops and infinity|
|8||Thu||Thursday, September 26, 2019||Equivalence to other models||2||1|
|9||Tue||Tuesday, October 1, 2019||Uncomputability|
|10||Thu||Thursday, October 3, 2019||Godel's Incompleteness Theorem|
|--||Sun||Sunday, October 6, 2019||Problem set 2 due on midnight||2|
|11||Tue||Tuesday, October 8, 2019||Restricted computational models (regular languages)|
|12||Thu||Thursday, October 10, 2019||_Recap, regroup, and prepare_ , __Midterm 1 at 7pm__|
|13||Tue||Tuesday, October 15, 2019||Introduction to efficient computation||3|
|14||Thu||Thursday, October 17, 2019||Formally defining running time|
|15||Tue||Tuesday, October 22, 2019||Polynomial time reductions|
|16||Thu||Thursday, October 24, 2019||More reductions||4||3|
|17||Tue||Tuesday, October 29, 2019||Cook Levin Thm|
|18||Thu||Thursday, October 31, 2019||discussion of P vs NP|
|19||Tue||Tuesday, November 5, 2019||Review of probability||5||4|
|20||Thu||Thursday, November 7, 2019||Introduction to randomized algorithms (see also the first few pages of Chapter 19)|
|21||Tue||Tuesday, November 12, 2019||Modeling randomized computation|
|22||Thu||Thursday, November 14, 2019||_Recap, regroup, and prepare_, __Midterm 2 at 7pm__||--||--|
|23||Tue||Tuesday, November 19, 2019||Space complexity (Madhu)||6||5|
|24||Thu||Thursday, November 21, 2019||Crypto|
|25||Tue||Tuesday, November 26, 2019||Quantum computing||7 (cumulative, final prep);||--|
|--||--||Sunday, December 1, 2019||Pset 6 due||6|
|--||Thu||Wednesday, November 27, 2019||No lecture: thanksgiving|
|26||Tue||Tuesday, December 3, 2019||Algorithms and society, course summary|
|--||Thu||Thursday, December 5, 2019||Pre final recap and review session|
|--||--||Saturday, December 7, 2019||Pset 7 due||7|