Gregor Reisch: Madame Arithmatica, 1508


Introduction to Algorithms
COMPSCI 531 • Fall 2021

Instructors: Pankaj K. Agarwal Alex Steiger

TA: Lu Wang

Lecture: Tu/Th 1:45-3:00 pm in LSRC B101

Discussion: Mo 1:45-3:00 pm in Physics 130

Office Hours (Virtual): Zoom Link on Sakai
Agarwal: Tu/Th @ 4-5pm
Steiger: Mon @ 4-5pm, Wed @ 3-4pm
Wang: Tu @ 10-11am, Fri @ 1-2pm

Course Synopsis

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

  • Ranking: Mergesort, Quicksort, order statistics, rank aggregation, fair ranking
  • Graphs: Shortest paths, breadth-first search, Dijkstra's algorithm, Floyd's algorithm, dynamic programming, similarity and edit distance
  • Clustering: Minimum spanning trees, k-center clustering, k-means clustering, fair clustering, expectation-maximization algorithm, local search, algebraic views of graphs, spectral clustering
  • Network Problems: Max-flow min-cut theorem, bipartite matchings, flow and matching algorithms, online matchings & auctions
  • Optimization: Linear programming, duality, LP algorithms and rounding, gradient descent
  • Hashing: Universal hashing, Bloom filters, consistent hashing, locality sensitive hashing


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


[Er]J. Erickson, Algorithms, self-published, 2019. [online]

Additional algorithms lecture notes by Erickson are found at the link above, which we cite collectively as [Er2]. For example, the notes on Linear Programming are [Er2 H].

Reference Books and Notes

[DVP]S. Dasgupta, U. Vazirani, C. Papadimitriou, Algorithms, McGraw-Hill, 2006.
[Ed]H. Edelsbrunner, Design and Analysis of Algorithms, lecture notes, 2008. [online]
[KT]R. Kleinberg, È. Tardos, Algorithm Design, Pearson, 2009.
[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.
[WS]D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. [online]


  • Assignments (best six of eight): 20%
  • Two projects: 30%
  • Midterm exam: 20%
  • Final exam: 30%
  • Both exams are closed-book and in-person (unless policies change). See the Assignments page for more info about assignments and projects.

Additional Platforms

  • Sakai: Accessed here. This works as the hub to Gradescope and Ed. Any course resources (e.g. lecture notes, solutions) will be hosted on Sakai under Resources.
  • Gradescope: Accessed via Sakai. All assignments and project documents will be submitted here. See Assignments for more info.
  • Ed Discussions: Accessed via Sakai. Ed is a questions-and-answers message board (similar to Piazza) that is easy to use and allows for all participants to help answer each other's questions. Please ask all course-related questions on Ed by creating a new post, not only those about assignments.
  • page top