Please begin by reviewing the Getting Started Doc. The following represents a tentative schedule for the semester and is subject to change. Assignments are due by 11:59 pm on the scheduled day and accepted late for a small penalty for up to 72 hours after the deadline.
| Week | Date | Class | Topic | References | Due |
|---|---|---|---|---|---|
| 1 | Th 1/11 | L01 | Algorithms, Data Structures, and Asymptotic Analysis | Erickson 0 Start Guide | |
| 2 | M 1/15 | No meeting | MLK DAY | ||
| Tu 1/16 | L02 | Proof by Induction and Algorithms | Erickson Appendix I Start Guide | ||
| Th 1/18 | L03 | Recursive Algorithms and Recurrence Relations | Erickson Appendix II Start Guide | ||
| 3 | M 1/22 | R01 | Introduction and Background | ||
| Tu 1/23 | L04 | Divide & Conquer I: Mergesort and Solving Recurrences | Erickson 1 | ||
| Th 1/25 | L05 | Divide & Conquer II: Quicksort and Randomization | Erickson 1 | HW 1 Introduction | |
| 4 | M 1/29 | R02 | D & C | ||
| Tu 1/30 | L06 | Parallel Algorithms I: Concepts and Analysis | CLRS 27 (on Canvas) | ||
| Th 2/1 | L07 | Parallel Algorithms II: Algorithm Design | CLRS 27 (on Canvas) | HW 2 Divide & Conquer | |
| 5 | M 2/5 | R03 | Parallel | ||
| Tu 2/6 | L08 | Dynamic Programming I: Memoization and Sequence Alignment | Erickson 3 | ||
| Th 2/8 | L09 | Dynamic Programming II: Knapsack and Chain Matrix Multiplication | Erickson 3 | HW 3 Parallel Algorithms | |
| 6 | M 2/12 | R04 | DP | ||
| Tu 2/13 | L10 | Depth-First Search I: Graphs, Paths, Connected Components | Erickson 5 and 6 | ||
| Th 2/15 | L11 | Depth-First Search 2: Topological Sort, Strongly Connected Components | Erickson 6 | HW 4 Dynamic Programming | |
| 7 | M 2/19 | R05 | DFS | ||
| Tu 2/20 | L12 | Shortest Paths I: Breadth-First Search | Erickson 8 | ||
| Th 2/22 | L13 | Shortest Paths II: Nonnegative Weights and Dijkstra | Erickson 8 and 9 | HW 5 Depth-First Search | |
| 8 | M 2/26 | R06 | Midterm Review | ||
| Tu 2/27 | L14 | MIDTERM EXAM (L01-11) | |||
| Th 2/29 | L15 | Shortest Path III: Dynamic Programming, and Midterm Debrief | |||
| 9 | M 3/4 | R07 | Shortest Paths | ||
| Tu 3/5 | L16 | Greedy I: Minimum Spanning Tree | Erickson 7 | ||
| Th 3/7 | L17 | Greedy II: Scheduling | Erickson 4 | HW 6 Shortest Paths | |
| 10 | M 3/11 | No meeting | SPRING BREAK | ||
| Tu 3/12 | No meeting | SPRING BREAK | |||
| Th 3/14 | No meeting | SPRING BREAK | |||
| 11 | M 3/18 | R08 | Greedy | ||
| Tu 3/19 | L18 | Flows and Cuts I: Max-flow, Min-cut, Ford-Fulkerson | Erickson 10 | ||
| Th 3/21 | L19 | Cuts and Flows II: Computing, Reductions, Applications | Erickson 10 and 11 | HW 7 Greedy | |
| 12 | M 3/25 | R09 | Cuts and flows | ||
| Tu 3/26 | L20 | Hardness I: Complexity Classes and NP-Completeness | Erickson 12 | ||
| Th 3/28 | L21 | Hardness II: NP-Complete Problems and Reductions | Erickson 12 | HW 8 Cuts and Flows | |
| 13 | M 4/1 | R10 | Hardness | ||
| Tu 4/2 | L22 | Approximation Algorithms I: Scheduling, Traveling Salesperson | Erickson J | ||
| Th 4/4 | L23 | Approximation Algorithms II: Clustering | Erickson J | HW 9 Hardness | |
| 14 | M 4/8 | R11 | Approximation | ||
| Tu 4/9 | L24 | Randomized Algorithms I: Graph Min Cut | Erickson DC 8 and 5 | ||
| Th 4/11 | L25 | Randomized Algorithms II: Karger-Stein and Hashing | Erickson DC 5 and 6 | HW 10 Approximation Algorithms | |
| 15 | M 4/15 | R12 | Lateterm Exam Review | ||
| Tu 4/16 | L26 | LATETERM EXAM (L12--23) | |||
| Th 4/18 | L27 | Randomized Algorithms III: Hashing and Sketching | |||
| 16 | M 4/22 | R13 | Final Exam Review | ||
| Tu 4/23 | L28 | The End | Erickson H and I | ||
| Th 4/25 | No meeting | Reading Period | |||
| 17 | M 4/29 | No meeting | Reading Period | ||
| Tu 4/30 | No meeting | Reading Period | |||
| Th 5/2 | No meeting | Reading Period | |||
| F 5/3 | Exam | FINAL EXAM 2-5 PM |
