Algorithm Design and Analysis (EI6303)
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. 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. Linear programming IV. Verfiication on DNNs. Lecture 15. NP problems I. Reductions on Various Problems. Lecture 16. NP problems II. Complexity Classes. Lecture 17. NP problems III. Beyond NP. Lecture 18. NP problem IV. DPLL Algorithm. Lecture 19. Approximation algorithms I. Greedy Approaches. Lecture 20. Approximation algorithms II. Eular Tour. Lecture 21. Approximation algorithms III. PTAS. Lecture 22. Approximation algorithms IV. LP-Based AA. Lecture 23. Approximation algorithms V. MAXSAT. Guoqiang Li
Materials
Last modified: Sunday, Feb. 16, 2025.