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 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