Design and Analysis of Algorithms (Spring 2021)
General Information
Instructor: Chihao Zhang
|
Time:
Friday
12:55 - 15:40
|
Location: DongShangYuan (东上院) 105
|
Office Hour:
Monday
7:00pm - 10:00pm
School of Software (软件学院) 1402-2
|
References
Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, Mcgraw-Hill Education.
News
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