Gregor Reisch: Madame Arithmatica, 1508

Administration

Design & Analysis of Algorithms
COMPSCI 532 • Fall 2024

Instructor: Pankaj K. Agarwal

TA: Rahul Raychaudhury

Time: Mon, Wed 3:05-4:20 pm

Location: French 4233

Office Hours:
Agarwal: Mon 1:45-2:45
Raychaudhury: Tue, Thu 15:00-16:00, LSRC D309

Course Synopsis

This course covers design and analysis of efficient algorithms at a graduate level. Topics include:

  • Linear Programming: Polyhedral combinatorics, LP algorithms, duality
  • Network Optimization Problems: Max flow, min cut, min cost flow, optimal transport
  • Approximation Algorithms: Greedy algorithms, local-search, multiplicative weight updatemethod, primal-dual method
  • Randomized Algorithms: Tail bounds, global min-cut, LP rounding, SDP rounding, probabilistic embeddings
  • Similarity Search: Nearest neighbor searching in low dimensions, dimension reduction, locality sensitive hashing
  • Algebraic and Numerical Algorithms: Polynomial identity testing, gradient descent, graph Laplacian, Markov chains

Prerequisites

COMPSCI 230 and 330, or equivalent courses. This course requires undergraduate background in discrete mathematics and algorithms

Textbook

[KT]J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.
[WS]D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Reference Books

[Er]J. Erickson, Algorithms, 2019.
[HP]S. Har-Peled, Geometric Approximation Algorithms, AMS, 2013.
[MG]J. Matoušek and B. Gärtner, Understanding and Using Linear Programming, Springer, 2007.
[MR]R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press.

Grading

  • Assignments (four out of five): 40%
  • Two midterm exams (in-class, closed book): 60%

page top