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.
Here is this semester's tentative schedule; we will update it as the semester progresses.
Please note that lecture notes are provided as a supplement, and are NOT a substitute for attending lecture. In particular, these are not guaranteed, so expect technical difficulties to prevent them from being posted at least a few times in the semester; they also will not contain exercises whose solutions are worked out on the board in class. Please plan accordingly to either take notes or get them from a friend if necessary.
Date Topic Reading Lecture Notes Homework (if any) Monday Jan. 13 Introduction and review Lecture notes HW0 released Wednesday Jan. 15 Review: induction Lecture notes Friday Jan. 17 Review: pseudocode and runtime Chapter 0 (on Persuall) Lecture notes Wednesday Jan. 22 Recursion Sections 1.1-1.4 Lecture notes HW0 due, HW1 released Friday Jan. 24 Solving recurrences Sections 1.5-1.7 Lecture notes Monday Jan. 27 Recursion (cont) Sections 1.8-1.10 Lecture notes Wednesday Jan. 29 Backtracking Sections 2.1-2.4 Lecture notes Friday Jan. 31 Backtracking Sections 2.5-2.8 Lecture notes HW1 due, HW2 released Monday Feb. 3 Backtracking
Intro to Dynamic ProgrammingLecture notes Wednesday Feb. 5 Dynamic Programming Sections 3.1-3.5 Lecture notes Friday Feb. 7 Dynamic Programming Sections 3.6-3.7 Lecture notes Monday Feb. 10 Dynamic Programming Sections 3.7-3.8 Lecture notes HW2 due, HW3 released Wednesday Feb. 12 Dynamic Programming Finish up Chater 3 Lecture notes Friday Feb. 14 Greedy Algorithms Sections 4.1-4.3 Lecture notes Monday Feb. 17 Greedy Algorithms Subtitute - see lecture recording Wednesday Feb. 19 Greedy Algorithms Sections 4.3-4.4 Lecture notes HW 3 due, HW 4 released Friday Feb. 21 Greedy Algorithms
Intro to graphsEnd of Chapter 4, Sections 5.1-5.3(ish) Lecture notes Monday Feb. 24 Graphs: Intro Sections 5.3-5.5 Lecture notes Wednesday Feb. 26 Graph: WFS Sections 5.5-5.7 Lecture notes Friday Feb. 28 Graphs: Connected components and reductions End of chapter 5
Sections 6.1-6.2Lecture notes HW 4 due Monday March 1 Review session
Exam on Tuesday, 8am, in 138 DeBartoloPractice problems Wednesday March 3 Graphs: Strong Connectivity Sections 6.3-6.5 Lecture notes HW 5 released Friday March 5 Graphs: Topological sort End of chapter 6
Sections 7.1-7.2Lecture notes Monday March 17 MSTs Chapter 7 Lecture notes Wednesday March 19 MSTs
Intro to SSSPEnd of Chapter 7
Section 8.1Lecture notes Friday March 21 Shortest paths Sections 8.2-8.5 Lecture notes HW 5 due Monday March 24 Dijkstra's algorithm
Bellman-FordSections 8.6-8.7 Lecture notes HW 6 released Wednesday March 26 Bellmen-Ford
MSSPChapter 9 Lecture notes Friday March 28 MSSP
Intro to flowsLecture notes Monday March 31 Max flow Lecture notes Wednesday April 2 Flows: algorithms Lecture notes HW6 due, HW 7 released Friday April 4 Applications of flows Lecture notes Monday April 7 No class today Wednesday April 9 Complexity and algorithms Friday April 11 NP-Hardness HW 7 due, HW 8 released Monday April 14 NP-Hardness Wednesday April 16 Linear Programming HW 8 due, HW 9 released Wednesday April 23 LP: Duality Friday April 25 LP: Simplex Monday April 28 Approximation Wednesday April 30 Review in class HW 9 due