Schedule

This is the page for the Fall 2019 offering of CS 121. See the Fall 2020 web page for information about the Fall 2020 offering by Madhu Sudan.

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 #DayDateLecturesPset outPset due
1TueTuesday, September 3, 2019 Introduction  
2ThuThursday, September 5, 2019 Review math background   
3TueTuesday, September 10, 2019 Representing objects as strings 0
4ThuThursday, September 12, 2019 Defining computation   
5TueTuesday, September 17, 2019 Syntactic sugar and computing every function 1 
6ThuThursday, September 19, 2019 Code as data   
7TueTuesday, September 24, 2019 Loops and infinity   
8ThuThursday, September 26, 2019 Equivalence to other models 21
9TueTuesday, October 1, 2019 Uncomputability   
10ThuThursday, October 3, 2019 Godel's Incompleteness Theorem   
--SunSunday, October 6, 2019 Problem set 2 due on midnight  2
11TueTuesday, October 8, 2019 Restricted computational models (regular languages)  
12ThuThursday, October 10, 2019_Recap, regroup, and prepare_ , __Midterm 1 at 7pm__  
13TueTuesday, October 15, 2019Introduction to efficient computation 3 
14ThuThursday, October 17, 2019Formally defining running time   
15TueTuesday, October 22, 2019Polynomial time reductions   
16ThuThursday, October 24, 2019More reductions43
17TueTuesday, October 29, 2019Cook Levin Thm  
18ThuThursday, October 31, 2019discussion of P vs NP  
19TueTuesday, November 5, 2019 Review of probability 54
20ThuThursday, November 7, 2019Introduction to randomized algorithms (see also the first few pages of Chapter 19)  
21TueTuesday, November 12, 2019 Modeling randomized computation   
22ThuThursday, November 14, 2019_Recap, regroup, and prepare_, __Midterm 2 at 7pm__----
23TueTuesday, November 19, 2019Space complexity (Madhu)65
24ThuThursday, November 21, 2019Crypto   
25TueTuesday, November 26, 2019Quantum computing 7 (cumulative, final prep);--
----Sunday, December 1, 2019Pset 6 due6
--ThuWednesday, November 27, 2019No lecture: thanksgiving  
26TueTuesday, December 3, 2019Algorithms and society, course summary
--ThuThursday, December 5, 2019Pre final recap and review session
----Saturday, December 7, 2019Pset 7 due7