Syllabus |
Schedule |
| # | Date | Topic | Reading | HW |
|---|---|---|---|---|
| 1 | M 1/7 | Course Overview, Induction Slides |
--- | |
| 2 | W 1/9 | Stable Matching: Gale-Shapley Algorithm, Proof by Contradiction Slides: Unannotated. Annotated |
KT 1.1,1.2,2.3 | HW1 Out (pdf, tex) |
| 3 | M 1/14 | Stable Matching, Asymptotic Analysis, Insertion Sort Slides: Unannotated. Annotated |
KT 2.1-2.2 | --- |
| 4 | W 1/16 | Divide and Conquer: Mergesort Slides: Unannotated. Annotated |
KT 5.1, 5.2 Erickson II.1-3 |
HW1 Due |
| -- | M 1/21 | No Class (MLK Birthday) | --- | --- |
| 5 | W 1/23 | Divide and Conquer: Mergesort, Recurrences Slides: Unannotated Annotated |
--- | HW2 Out (pdf, tex) |
| 6 | M 1/28 | Divide and Conquer: Karatsuba Slides: Unannotated. Annotated |
KT 5.5, 5.4 | |
| 7 | W 1/30 | Divide and Conquer: Binary Search. Dynamic Programming: Key Concepts, Interval Scheduling Slides: Unannotated Annotated |
HW2 Due HW3 Out (pdf, tex, Images for tex) |
|
| 8 | M 2/4 | Dynamic Programming: Key Concepts, Interval Scheduling Slides: Unannotated Annotated. |
KT 6.1-6.2 | --- |
| 9 | W 2/6 | Dynamic Programming: Interval Scheduling Slides: Unannotated Annotated |
KT 6.3-6.4 | HW3 Due |
| 10 | M 2/11 | Dynamic Programming: Knapsack Slides: Unannotated Annotated |
KT 6.5-6.7 | --- |
| 11 | W 2/13 | Midterm I Review Slides: Annotated |
--- | |
| -- | M 2/18 | No Class (Presidents' Day) | --- | --- |
| -- | W 2/20 | Midterm I (In Class) | --- | HW4 Out (pdf,tex) |
| 12 | M 2/25 | Graph Algorithms: Graphs, BFS Slides: Unannotated Annotated |
KT 3.1-3.4 | |
| 13 | W 2/27 | Graph Algorithms: Breadth First Search Slides: Unannotated Annotated |
KT 3.5-3.6 | HW4 Due *REVISED* HW5 Out (pdf, tex) |
| -- | M 3/4 | No Class (Spring break) | --- | --- |
| -- | W 3/6 | No Class (Spring break) | --- | --- |
| 14 | M 3/11 | Graph Algorithms: 2-Coloring, Connected Components, DFS Slides:Unannotated Annotated |
KT 4.4, 2.5 | --- |
| 15 | W 3/13 | Graph Algorithms: Depth First Search, Topological Ordering Slides: Unannotated Annotated |
--- | HW5 Due HW6 Out (pdf, tex) |
| 16 | M 3/18 | Graph Algorithms: Correctness of Dijkstra's Algorithm Slides: Unannotated Annotated |
KT 6.8-6.10 | --- |
| 17 | W 3/20 | Graph Algorithms: Implementation of Dijkstra's Algorithm Slides: Unannotated Annotated |
KT 6.8-6.10 | HW6 Due |
| 18 | M 3/25 | Midterm II Review Slides: Unannotated Annotated |
--- | --- |
| -- | W 3/27 | Midterm II (In Class) | --- | --- |
| 19 | M 4/1 | Bellman-Ford Algorithm. Slides: Unannotated Annotated |
KT 7.1-7.2 | --- |
| 20 | W 4/3 | None Slides: |
HW7 Out (pdf, tex) | |
| 21 | M 4/8 | Network Flow: Flows, Cuts, Augmenting Paths Slides: Unannotated Annotated |
KT 7.5-7.6 | --- |
| 22 | W 4/10 | Network Flow: Choosing Good Augmenting Paths Slides: Unannotated Annotated |
KT 7.8-7.12 | HW7 Due HW8 Out (pdf, tex) |
| -- | M 4/15 | No Class (Patriots' Day) | --- | --- |
| --- | W 4/17 | Final Review. Unannotated Annotated | --- | HW8 Due |
| -- | R 4/25 | Final Exam (Churchill Hall 103, 1-3PM) | --- | --- |