Design & Analysis of Efficient Algorithms — Summer 2022

Tentative Schedule

This schedule is subject to change based on the class's pace. Any change will be announced in class and will be reflected here.
DateTopicSuggested ReadingsHomework 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

*: If time permits.