Design and Analysis of Algorithms (Fall 2021)

Course Description

This course will cover the basic approaches and mindsets for analyzing and designing algorithms. Topics include the following: divide and conquer, basic graph algorithms, greedy algorithms, dynamic programming, network flow, NP-hardness. Possible additional topics: approximation algorithms, hardness of approximation.

General Information

Instructors:

Yuhao Zhang, Biaoshuai Tao

Teaching Assistants:

Zonghan Yang, Jinyi Wang

Time:

Week 1 - 16: Friday 14:00 - 15:40
Week 9 - 16: Tuesday 8:00 - 9:40

Location:

DongShangYuan (东上院) 111

References

Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, McGraw-Hill Education.

Lecture Slides

Lecture 1 Course Introduction, Integer Multiplications, Divide and Conquer
Lecture 2 Merge Sort, Count Number of Inversions
Lecture 3, 3.5 Quick Selection, Median-of-the-medians, Finding Closest Pair
Lecture 4 Basic Graph Algorithms, DFS and Its Applications
Lecture 5 Shortest Path, BFS, Dijkstra's Algorithm
Lecture 6 Shortest Path, Bellman-Ford Algorithm
Lecture 7 Greedy Algorithms
Lecture 8 Fast Fourier Transform for Polynomial Multiplications
Lecture 9 More Greedy Algorithms
Lecture 10 Dynamic Programming 1
Lecture 11 Dynamic Programming 2
Lecture 12 Dynamic Programming 3
Lecture 13 Network Flow, Ford-Fulkerson Algorithm, Maximum Bipartite Matching
Lecture 14 Max-Flow-Min-Cut Theorem, Maximum Bipartite Matching
Lecture 15 Edmonds-Karp Algorithm, Dinic's Algorithm, Hopcroft-Karp-Karzanov algorithm
Lecture 16 Linear Programming, LP Duality Theorem, LP-Relaxation
Lecture 17 Application of LP Duality Theorem: Max-Flow-Min-Cut Theorem Revisited, von Neumann's Minimax Theorem
Lecture 18 P, NP, Reductions, NP-Completeness
Lecture 19 Techniques for reductions, Proof writing guide, NP-hard optimization problems
Lecture 20 k-Means, Approximation Algorithms
Lecture 21 More Approximation Algorithms: Max-3SAT, Max-k-Coverage, Set Cover, Max-Cut (Local Search)
Lecture 22 LP-Related Algorithms: Hungarian Algorithm, Metric Facility Location