Here is this semester's tentative schedule; I will update it as the semester progresses. The listed sections refer to chapters or sections in the course textbook, Algorithms. Note that you are expected to complete some of these readings on Perusall as well! I'm just noting sections here for ease of later reference.
Please note that all lectures notes are provided as a resource, not a substitution for attending class! In particular, my tablet will inevitably fail at least a few times this semester, and you should be prepared to do extra reading and/or meet with a friend to get notes that you missed if you are gone. (And if anyone complains about my handwriting, then I'll stop posting them!)
Date Topic Reading Lecture Notes Worksheets (if any) Mon Aug. 26 -
Fri Aug 30No class
(see email for details)Chapters 0 and 1
(check Perusall dates)Wednesday, Sept. 4 Recursion Sections 1.6 and 1.7 Lecture Notes Friday, Sept. 6 More recursion Sections 1.6 and 1.7 Lecture Notes Monday, Sept. 9 Recursion:
Recursion trees
fast multiplicationSections 1.7, 1.9 Lecture Notes Wednesday, Sept. 11 Recursion: Median selection
Backtracking: introSections 1.8, 2.4 Lecture Notes Friday, Sept. 13 Backtracking: subset sum
Text segmentationSections 2.3, 2.5 Lecture Notes Monday, Sept. 16 Dynamic Programming intro
Recap of backgrackingSections 3.1,3.3 Lecture Notes Wednesday, Sept. 18 DP: LIS Sections 3.4-3.6 Lecture Notes Friday, Sept. 20 DP: LIS, Edit distance Sections 3.6,3.7 Lecture Notes Monday, Sept. 23 DP: Edit distance Section 3.7 Lecture Notes Wednesday, Sept. 25 DP: Binary Trees Section 3.9 Lecture Notes Friday, Sept. 27 Greedy: scheduling Section 4.2 Lecture Notes Monday, Sept. 30 Greedy: Huffman trees Section 4.4 Lecture Notes Wednesday, Oct. 2 Greedy: Huffman trees (finishing) Section 4.4 Lecture Notes Friday, Oct. 4 Problem session day Worksheet Monday, Oct. 7 Graphs: intro Sections 5.1-5.4 Lecture Notes Monday, Oct. 14 Graphs: BFS and DFS Section 5.5 and 5.6 Lecture Notes Wednesday, Oct. 16 Graphs: Connected components and reductions Section 5.7 and 5.8 Lecture Notes Friday, Oct. 18 MSTs Section 7.1-7.3 Lecture Notes Wednesday, Oct. 23 MST algorithms Section 7.4 and 7.5 Lecture Notes Friday, Oct. 25 Flows and Cuts Sections 10.1 and 10.2 Lecture Notes Monday, Oct. 28 Max flow and min cut duality Section 10.3 Lecture Notes Monday, Nov. 4 Ford Fulkerson Section 10.4 Lecture Notes Wednesday, Nov. 6 More flow algorithms Section 10.6 and 10.7 Lecture Notes Friday, Nov. 8 Shortest paths Sections 8.1-8.4 Lecture Notes Monday, Nov. 11 Dijkstra's algorithm Sections 8.5-8.6 Lecture Notes Wednesday, Nov. 13 Bellman-Ford Sections 8.7 Lecture Notes Friday, Nov. 15 Hardness and complexity Sections 12.1-12.3 Lecture Notes Monday, Nov. 18 NP-Hardness: Cook's theorem Sections 12.4-12.5 Lecture Notes Wednesday, Nov. 20 NP-Hardness: Reductions Sections 12.6-12.8 Lecture Notes Friday, Nov. 22 More reductions Sections 12.9-12.10 Lecture Notes Monday, Nov. 25 Non-graph reductions Sections 12.11-12.13 Lecture Notes Monday, Dec. 2 Linear programming Dasgupta book (Chapter 7) Lecture Notes Wednesday, Dec. 4 LP: Duality Dasgupta chapter Lecture Notes Friday, Dec. 6 LP: Simplex Lecture Notes