COMPSCI 532 Graduate Algorithms
COMPSCI 532 Graduate Algorithms
Fall 2023
Fall 2023
Class overview
This course will cover algorithm design techniques at a graduate level. The topics include network flows, linear programming, randomized algorithms, approximation algorithms, spectral graph theory and some short special topics.
Announcements
Homework 1 is posted, due 9/14/2023.
Basic Information
Instructor: Rong Ge
Time: WF 3:05 PM - 4:20 PM
Location: Gross Hall 107
Textbooks
There are many related books but no textbook is required.
[BE] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1st ed., 1998
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd ed., 2001
[DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006
[KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 1st ed., 2005
[MR] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[V] V. V. Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.
[WS] D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
Logistics
Course materials will be posted to sakai.
We use Ed discussions for discussions and questions.
Homework will be posted on sakai, and submitted through gradescope. Homework solutions must be typed (ideally using LaTeX).
Reading Materials
If you are looking for reading materials before the lectures, in addition to the textbooks you can look at lecture notes/slides from previous versions of this course, e.g., https://courses.cs.duke.edu/fall15/compsci532/, https://courses.cs.duke.edu//fall19/compsci532/, https://sites.google.com/view/compsci532-kamesh , https://sites.google.com/view/duke-compsci-532-fall21/home, https://courses.cs.duke.edu/compsci532/fall22/