Design and Analysis of Algorithms (EI6303)
Spring Semester
to graduates, School of Software
[DPV07] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms, McGraw-Hill, 2007.
[KT05] J. Kleinberg and E. Tardos. Algorithm Design, Addison-Wesley, 2005.
[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 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. Dynamic Programming III. Treewidth.
Lecture 8. Network flows I: Ford-Fulkson, revisited.
Lecture 9. Network flows II: More Extension on Ford-Fulkson Networks.
Lecture 10. Network flows III: Simple Unit-Capacity Networks.
Lecture 11. Linear programming I. LP and Duality.
Lecture 12. Linear programming II. Simplex.
Lecture 13. Linear programming III. Applications.
Lecture 14. NP problems I. Various Problems.
Lecture 15. NP problems II. Complexity Classes.
Lecture 16. NP problems III. Beyond NP.
Lecture 17. NP problem IV. DPLL Algorithm.
Lecture 18. Approximation algorithms I. Greedy Approaches.
Lecture 19. Approximation algorithms II. Eular Tour.
Lecture 20. Approximation algorithms III. PTAS.
Lecture 21. Approximation algorithms IV. LP-Based AA.
Lecture 22. Approximation algorithms V. MAXSAT.
Guoqiang Li
Last modified: Thusday, Jan. 25, 2024.