ABCDEFGHIJKLMNOPQRSTUVWX
1
NOTE: If a link is broken, it's because last year's files were zipped to avoid confusion. Download the zip file here to access old content.
2
Course Website (with links to Ed, Gradescope, Canvas, Github, etc.)GithubEdRecommended reading
3
DateDayLecturesLecturerTopic(s)Psets - OutPset - DueExams
SREs (College, Extension)
HolidaysSectionCLRSRoughgardenMacCormickLewis & ZaxOther
4
2023-08-31RLecture 0BothCourse overview (slides)Pset 01I, 1.11
5
Storing and Searching
6
2023-09-05TLecture 1Adam
Sorting Algorithms and Computational Problems (notes, with details, scribe)
2.1I, 1.4, 1.5CS50 Week 3
7
2023-09-07RLecture 2AnuragMeasuring efficiency (notes, with details, scribe)03, 8.1I, 221
8
2023-09-12TLecture 3AnuragReductions (notes, with details, scribe)Pset 1Pset 0: 09-13
Counting sort (receiver, sender)
9
2023-09-14RLecture 4AdamData structures (notes, details, scribe)110II, 10.0, 10.1, 11.1CS50 Week 5
10
2023-09-19TLecture 5AdamBinary Search Trees (notes, details)Pset 2Pset 1: 09-2012.0 - 12.3II, 11.2 - 11.4
11
Computational Models
12
2023-09-21RLecture 6AdamRAM Model (notes, details, scribe)
BST deletion (receiver, sender)
22.2
13
2023-09-26TLecture 7AnuragRAM and Word-RAM Simulations (notes, details)Pset 3Pset 2: 09-27I, 6.0-6.2
14
2023-09-28RLecture 8AnuragRandomized Algorithms (notes, details, scribe)39.0-9.2, 11.0-11.4I,6.0-6.2; II,12.0-12.426-29
15
2023-10-03TLecture 9AdamDictionaries (notes, details)Pset 4Pset 3: 10-04
16
Algorithms
17
2023-10-05RLecture 10AnuragGraphs and Graph Search (notes , details, scribe)4 (review), recording22.2II, 8.1-8.2
18
2023-10-10TLecture 11AdamGraph Coloring (notes, details)
Connected components (receiver, sender)
III, 13.118
19
2023-10-12R
Midterm (covering "Storing & Searching" and "Computational Models", i.e. through lecture 9 (except graphs))
Midterm5
20
2023-10-17TLecture 12AnuragIndependent Sets (notes, details)Pset 5Pset 4: 10-18
Coloring (receiver, sender)
16.1, 16.2
21
2023-10-19RLecture 13AdamMatching (notes, details, scribe)625.1
22
2023-10-24TLecture 14GuestEmbedded EthiCS Module (notes)Pset 6Pset 5: 10-25
23
2023-10-26RLecture 15AdamLogic (notes, details, scribe)7IV, Sec. 21.5, Ch. 249-10
24
2023-10-31TLecture 16AnuragSAT solving (notes, details)Pset 7Pset 6: 11-01
25
Computational Complexity
26
2023-11-02RLecture 17AnuragThe Church-Turing Thesis (notes, details, scribe)
SAT reduction (receiver, sender)
8
5.6-5.7, 7.7-7.9
27
2023-11-07TLecture 18AdamComputational Complexity (notes, details)
5.3-5.5, Ch 10, 11
28
2023-11-09RLecture 19AnuragNP-completeness (notes, details, scribe)9
Ch. 12.0 - 12.3, 13
29
2023-11-14TLecture 20AnuragNP-completeness (notes, details)Pset 8Pset 7: 11-15Ch. 14, 17
30
2023-11-16RLecture 21AnuragThe P vs. NP Problem (notes , details, scribe)
NP reduction (receiver, sender)
10, Recording
14.4, 14.6, 14.8
31
Uncomputability
32
2023-11-21TLecture 22AdamUnsolvable Problems via Reduction (notes, details)6.0, 7.0-7.6
De Moura & Bjørner
33
2023-11-23R
University Holiday
Ch 3, 7.7 - 7.9
34
2023-11-28TLecture 23AdamComputational Complexity of Games (notes, details)Pset 9Pset 8: 11-29
35
Wrap Up
36
2023-11-30RLecture 24AnuragUnsolvability (notes, details)
Unsolvability (receiver, sender)
11
De Moura & Bjørner
37
2023-12-05TLecture 25BothConclusions (notes, details)Pset 9: 12-06
38
2023-12-16SatFinal ExamFinal Exam12
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100