## Instructors:Yuhao Zhang, Biaoshuai Tao |
## Teaching Assistants:Zonghan Yang, Jinyi Wang |
## Time:Week 1 - 16: Friday 14:00 - 15:40Week 9 - 16: Tuesday 8:00 - 9:40 |
## Location:DongShangYuan (东上院) 111 |

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

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