Design and Analysis of Algorithms (Spring 2021)

General Information


Chihao Zhang


12:55 - 15:40


DongShangYuan (东上院) 105

Office Hour:

7:00pm - 10:00pm
School of Software (软件学院) 1402-2


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


Lecture Notes

[Jun 11][manuscript][notes] Fine-grained complexity, ETH, SETH
[Jun 04][manuscript][notes] More examples on proofs of NP-hardness
[May 28][manuscript][notes] P and NP, NP-complete, Reductions, Proof of NP-hardness
[May 21][manuscript][notes] Max-SAT, Max-Cut, Semidefinite Programming
[May 14][manuscript][notes] Max-flow, Min-cut, Ford-Fulkerson, Edmonds-Karp
[May 07][manuscript][notes] Linear Programming, Simplex, Strong Duality Theorem, Minimax Theorem
[Apr 30][manuscript][notes] More examples on DP, Quadrangle Inequalities
[Apr 23][manuscript][notes] Floyd-Warshall, TSP, DP on Trees, Color Coding
[Apr 16][manuscript][notes] Dynamic Programming, LIS, Edit Distance, Knapsack, Chain Matrix Multiplication
[Apr 09][manuscript][notes] Prim, Task Assignment, Huffman Coding, Set Cover
[Apr 02][manuscript][notes] Greedy Algorithms, Minimum Spanning Tree, Kruskal, Union-Find Set
[Mar 26][manuscript][notes] BFS, Shortest Path, Dijkstra's Algorithms, Bellman-Ford Algorithm
[Mar 19][manuscript][notes] Fast Fourier Transform, Graph Search, Strongly Connected Components
[Mar 12][manuscript][notes] Divide and Conquer, Master Theorem
[Mar 05][manuscript][notes] RSA protocol, Algorithms for Arithmetics, Euclidean Algorithm
[Feb 26][manuscript][notes] Introduction to Computability (slides in Chinese), Computing Fibonacci Numbers