Please begin by reviewing the Getting Started Doc. The following represents a tentative schedule for the semester and is subject to change. Lectures are designated with L, and recitations with R. DPV refers to Algorithms by Dasgupta, Papadimitriou, and Vazirani. Assignments are due by 11:59 pm on the scheduled day.
References are provided for your benefit, and you are strongly encouraged to read and review one or both references to get the most out of the course.
| Week | Date | Class | Lecturer | Lecture Topic | References | Due |
|---|---|---|---|---|---|---|
| 1 | W 1/8 | L01 | Panigrahi | Introduction: Algorithms and Analysis | Erickson 0 Erickson Appendix I DPV 0 | |
| F 1/10 | NO MEETING | |||||
| 2 | M 1/13 | L02 | Fain | Introduction: Expected Background | ||
| W 1/15 | L03 | Fain | Divide & Conquer I: Mergesort and Solving Recurrences | Erickson 1 Erickson Appendix II DPV 2 | ||
| F 1/17 | R01 | Background and Recurrences | ||||
| 3 | M 1/20 | NO MEETING | MLK Jr. Holiday | |||
| Tu 1/21 | HW 1 | |||||
| W 1/22 | L04 | Fain | Divide & Conquer II: Quicksort/select, Multiplication | |||
| F 1/24 | R02 | Divide and Conquer | ||||
| 4 | M 1/27 | L05 | Fain | Dynamic Programming I: Memoization and Sequence Alignment | Erickson 3 DPV 6 | HW 2 |
| W 1/29 | L06 | Fain | Dynamic Programming II: Knapsack and Chain Matrix Multiply | |||
| F 1/31 | R03 | Dynamic Programming | ||||
| 5 | M 2/3 | L07 | Fain | Dynamic Programming III: Subset Sum and Increasing Subsequences | HW 3 | |
| W 2/5 | L08 | Fain | Greedy I: Scheduling | Erickson 4 DPV 5 | ||
| F 2/7 | R04 | DP and Greedy | ||||
| 6 | M 2/10 | L09 | Panigrahi | Depth First Search I: Graphs, Paths, Components | Erickson 6 DPV 3 | HW 4 |
| W 2/12 | L10 | Panigrahi | Depth First Search II: Topological Sort, Strong Connectivity | |||
| F 2/14 | R05 | Depth First Search | ||||
| 7 | M 2/17 | L11 | Panigrahi | Shortest Paths I: Breadth-First Search | Erickson 8 DPV 4 | HW 5 |
| W 2/19 | L12 | Panigrahi | Shortest Paths II: Nonnegative Weights and Dijkstra | |||
| F 2/21 | R06 | Shortest Paths | ||||
| 8 | M 2/24 | L13 | Panigrahi | Shortest Paths III: Dynamic Programming | HW 6 | |
| W 2/26 | L14 | Panigrahi | Greedy II: Minimum Spanning Trees | Erickson 7 DPV 5 | ||
| F 2/28 | R07 | Shortest Paths and Greedy | ||||
| 9 | M 3/3 | L15 | MIDTERM EXAM | |||
| W 3/5 | L16 | Fain | Parallel Algorithms | CLRS 27 (on canvas) | ||
| F 3/7 | NO MEETING | Cancelled | ||||
| 10 | M 3/10 | NO MEETING | Spring recess | |||
| W 3/12 | NO MEETING | Spring recess | ||||
| F 3/14 | NO MEETING | Spring recess | ||||
| 11 | M 3/17 | L17 | Fain | Cuts and Flows I: Max-flow, Min-cut, Ford-Fulkerson | Erickson 10 Erickson 11 DPV 7 | |
| W 3/19 | L18 | Fain | Cuts and Flows II: Computing, Reductions, Applications | |||
| F 3/21 | R08 | Cuts and Flows | ||||
| 12 | M 3/24 | L19 | Panigrahi | Linear Programming I: Flows and Matchings | Erickson H DPV 7 | HW 7 |
| W 3/26 | L20 | Panigrahi | Linear Programming II: Duality | |||
| F 3/28 | R09 | Linear Programming | ||||
| 13 | M 3/31 | L21 | Panigrahi | Randomized I: Monte Carlo Algorithms | DPV Randomized Erickson DC 8DC 5, DC 6 | HW 8 |
| W 4/2 | L22 | Panigrahi | Randomized II: Las Vegas Algorithms | |||
| F 4/4 | R10 | Randomized Algorithms | ||||
| 14 | M 4/7 | L23 | Panigrahi | Randomized III: Hashing and Sketching | HW 9 | |
| W 4/9 | L24 | Fain | Hardness & Approximation I | Erickson 12 Erickson J DPV 8-9 | ||
| F 4/11 | R11 | Hashing and Approximation | ||||
| 15 | M 4/14 | L25 | Fain | Hardness & Approximation II | HW 10 | |
| W 4/16 | L26 | Fain | Hardness & Approximation III | |||
| F 4/18 | R12 | Hardness and Approximation | ||||
| 16 | M 4/21 | L27 | LATETERM EXAM | |||
| W 4/23 | L28 | Final review | ||||
| F 4/25 | NO MEETING | Reading period | ||||
| 17 | M 4/28 | NO MEETING | Exam period | |||
| W 4/30 | NO MEETING | Exam period | ||||
| Th 5/1 | FINAL EXAM | 2 pm FINAL EXAM |
