Design and Analysis of Algorithms (Spring 2022)
General Information
Instructor: Chihao Zhang
|
Time:
Friday
12:55 - 15:40
|
Location: 下院 412
|
Office Hour:
Monday
7:00pm - 10:00pm
School of Software (软件学院) 1402-2
|
Textbook
Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, McGraw-Hill Education.
News
Lecture Notes
See here for the lecture notes last year.
[May 27][notes] Proof of NP-hardness (Chapter 8 of the textbook, also the notes)
[May 20][notes] P, NP, NP-complete, Reductions (See the notes)
[May 13][notes] Some further applications of Max-flow (See the references)
[May 06][notes] Max-flow, Min-cut, Ford-Fulkerson, Edmonds-Karp (See this note)
[Apr 29][notes] Linear Programming and Rounding (See this note and this note)
[Apr 22][notes] DP on trees, Tree-decomposition, More Examples on DP (See this note)
[Apr 15][notes] Chain Matrix Multiplication, Floyd-Warshall, TSP, Color-coding (Chapter 6 of the textbook and this note)
[Apr 08][notes] Dynamic Programming, LIS, Edit Distance, Knapsack (Chapter 6 of the textbook)
[Apr 01][notes] Huffman Code, Task Assignments, Set Cover (See here)
[Mar 25][notes] Minimum Spanning Tree, Union-Find Set (Chapter 5.1 of the textbook)
[Mar 18][notes] BFS, Dijkstra's Algorithm, Bellman-Ford (Chapter 4 of the textbook)
[Mar 11][notes] DFS, DAG, Strongly Connected Component (Chapter 3 of the textbook)
[Mar 04][notes] Fast Fourier Transform (Chapter 2.6 of the textbook)
[Feb 25][notes] Divide and Conquer (Chapter 2.1 to 2.5 of the textbook, see here for additional examples)
[Feb 18][notes] Introduction to Computability (slides in Chinese), Computing Fibonacci Numbers