Date | Topic | Suggested Readings | Homework notes |
---|---|---|---|
06/27 | Course Overview and the basics of Asymptotic Analysis, Recurrences, and Master Theorem |
[KT]: 2.1, 2.2., 2.4, 5.1, 5.2 [CLRS]: 3 (1 and 2 optional), 4.3, 4.4, 6, Appendices A and C.1 |
|
Divide and Conquer | |||
06/28 | Counting Inversions, Median Select, Convex Hulls*, Closest Points*, Huffman Encoding* |
[KT]: 4.8, 5.3, 5.4 [CLRS]: 9.1–9.3, 16.3, 33.4, 33.3 |
HW 1 Out |
Dynamic Programming | |||
06/29 | Interval Scheduling, Knapsack, Longest Increasing Subsequence and Least Common Subsequence |
[KT]: 4.1, 6.1, 6.2, 6.4 [CLRS]: 15.3, 15.4 |
|
06/30 | Sequence Alignment* and Matrix Multiplication*, and Practice |
[KT]: 6.6, 6.7 [CLRS]: 15.2 Come with questions! |
|
07/04 | No class: university holiday | - | |
Graph Algorithms | |||
07/05 | Basic Graph Theory and Graph Traversals, Topological Sort, SCCs |
[KT]: 3.1–3.4, 3.6, 4.5 [CLRS]: 22.1–22.5 |
HW1 Due HW2 Out |
07/06 | Computing Shortest Paths and Matchings |
[KT]: 3.5, 4.4, 6.8–6.10 [CLRS]: 24, 25.1, 25.3 |
|
07/07 | More on Matchings + Practice |
[KT]: 7.1–7.3, 7.5–7.7 [CLRS]: 26.1–26.3 |
|
07/11 | Flows and Cuts |
[KT]: 7.1–7.3, 7.5–7.7 [CLRS]: 26.1–26.3 |
HW 2 Due |
Advanced topics | |||
07/12 | Class Canceled |
[KT]: - [CLRS]: - |
HW 3 Out |
07/13 | Linear Programming |
[KT]: - [CLRS]: 29.1, 29.2, 29.4, 29.5* |
|
07/14 | Linear Programming and Flows in Practice |
[KT]: - [CLRS]: - |
|
07/18 | Introduction to NP-completeness |
[KT]: 8.1–8.10 [CLRS]: 34 |
HW 3 Due HW 4 Out |
07/19 | Fast Fourrier Transforms |
[KT]: - [CLRS]: 30.1, 30.2 |
|
Final phase | |||
07/20 | Class Presentations I | Come with questions! | |
07/21 | Class Presentations II | Come with questions! | HW 4 Due on 07/24 |