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 (软件学院) 14022

Textbook
Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, McGrawHill Education.
News
Lecture Notes
See here for the lecture notes last year.
[May 27][notes] Proof of NPhardness (Chapter 8 of the textbook, also the notes)
[May 20][notes] P, NP, NPcomplete, Reductions (See the notes)
[May 13][notes] Some further applications of Maxflow (See the references)
[May 06][notes] Maxflow, Mincut, FordFulkerson, EdmondsKarp (See this note)
[Apr 29][notes] Linear Programming and Rounding (See this note and this note)
[Apr 22][notes] DP on trees, Treedecomposition, More Examples on DP (See this note)
[Apr 15][notes] Chain Matrix Multiplication, FloydWarshall, TSP, Colorcoding (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, UnionFind Set (Chapter 5.1 of the textbook)
[Mar 18][notes] BFS, Dijkstra's Algorithm, BellmanFord (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