Algorithm Design and Analysis (AI1401)

Autumn Semester

to undergraduates, School of Mathematics

Textbook

[DPV07] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms, 2007. [a local copy]

Lectures

Lecture 1. Prologue.

Lecture 2. Algorithms with Numbers I.

Lecture 3. Algorithms with Numbers II.

Lecture 4. Divide-and-Conquer I.

Lecture 5. Divide-and-Conquer II.

Lecture 6. Graph Algorithms I: decompositions of graphs.

Lecture 7. Graph Algorithms II: distances in graphs.

Lecture 8. Greedy Algorithms.

Lecture 9. Advanced Data Structures.

Lecture 10. Dynamic Programming I.

Lecture 11. Dynamic Programming II.

Lecture 12. Linear Programming I.

Lecture 13. Linear Programming II.

Lecture 14. Linear Programming III.

Lecture 15. NP Problem I.

Lecture 16. NP Problem II.

Lecture 17. NP Problem III.

Lecture 18. Coping with NP I: approximation algorithms.

Lecture 19. Coping with NP II: backtracking (CDCL algorithms).

Lecture 20. Coping with NP III: local search.

Lecture 21. Advanced Algorithms I: quantum algorithms.

Lecture 22. Advanced Algorithms II: geometric algorithms.

Lecture 23. Advanced Algorithms III: randomized algorithms.

Lecture 24. Conclusion.

Materials

Guoqiang Li
Last modified: Sunday, June 1, 2025.