Duke University
Duke University
COMPSCI 532
COMPSCI 532
Design and Analysis of Algorithms
Design and Analysis of Algorithms
Fall 2025
Fall 2025
This course covers topics in the design and analysis of algorithms at a graduate level. Students are expected to have already taken an undergraduate class in algorithms, similar to COMPSCI 330. Topics include linear programming, maximum flow algorithms, randomized algorithms, approximation algorithms, and other special topics.
Office hour: Mondays 1:30 - 2:30 pm in LSRC D203
Anish Hebbar
Office hours: Mondays 11:30 -12:30 PM in LSRC D316
Thursdays 10 - 11 AM in LSRC D316
Linear programming algorithms, MWU, separation oracles
Convex relaxations of discrete problems, relax and round with applications
Weak and strong duality with applications
Max-flow min-cut theorem
Augmenting flows, blocking flows
Scaling techniques, minimum cost flow
Pre-flows, push relabel algorithms
Monte Carlo sampling and applications
Monte Carlo algorithms
Las Vegas algorithms
Applications of randomization: metric embeddings, data streams, random projections
Combinatorial techniques
LP-based techniques: rounding, primal dual techniques
Semi-definite programming
Online algorithms
Continuous optimization: gradient descent
Learning-augmented algorithms
Course website: https://sites.google.com/view/duke-compsci-532-fall-2025
Course pages on Canvas: Design and Analysis of Algorithms| COMPSCI 532.01.Fa25 (duke.edu)
The course will also use Gradescope (for assignment submission and grading) and the Ed discussion forum (for discussions, questions,etc.). These can be accessed via the course Canvas page linked above.
The course does not have a textbook, but most of the material can be found in a subset of the following references:
[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