Algorithm Design and Analysis (EI6714)
Spring Semester
to graduates, School of Computer Science
[KT05] J. Kleinberg and E. Tardos. Algorithm Design, Addison-Wesley, 2005.
[DPV07] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms, McGraw-Hill, 2007.
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, The MIT Press, 2009.
[Vaz04] V. V. Vazirani. Approximation Algorithms, Springer-Verlag, 2004.
[WS11] D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011.
Lecture 1. Introduction. Lecture 2. Graph theory revisited I: SCC. Lecture 3. Graph theory revisited II: MST. Lecture 4. Graph theory revisited III: Algorithmic Verification. Lecture 5. Dynamic Programming I. Sequence Alignment. Lecture 6. Dynamic Programming II. Shortest Path. Lecture 7. Network flows I: Ford-Fulkson, revisited. Lecture 8. Network flows II: More Extension on Ford-Fulkson Networks. Lecture 9. Network flows III: Simple Unit-Capacity Networks. Lecture 10. NP problems I. Reductions on Various Problems. Lecture 11. NP problems II. Complexity Classes. Lecture 12. NP problems III. Beyond NP. Lecture 13. Approximation algorithms I. Greedy Approaches. Lecture 14. Approximation algorithms II. Eular Tour. Lecture 15. Approximation algorithms III. PTAS. Guoqiang Li
Materials
Last modified: Monday, Oct. 19, 2026.