COMPSCI 532 Graduate Algorithms
Fall 2021
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
Office hour on Tuesday 11/16 is moved to 2:30 - 3:30 pm.
Homework 6 (last homework) is now posted.
Since attendance for the Tuesday office hour is much better, I'm moving all future office hours to Tuesdays 3-4 pm.
Homework 5 is now posted.
Homework 4 is now posted.
Homework 3 is now posted, note the due date is Oct. 10 due to Fall break.
Homework 2 is now posted.
Homework 1 is now posted.
Basic Information
Instructor: Rong Ge
Time: MW 1:45 PM - 3:00 PM
Location: Biological Sciences 154
Format: the course is currently scheduled to be in-person. As a proof based course we will mostly use whiteboard. Will record the lectures if possible. Lecture notes will be uploaded.
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 piazza 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