Gregor Reisch: Madame Arithmatica, 1508
Administration
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
Prerequisites
COMPSCI 201 and 230, or equivalent courses. This course requires undergraduate background in discrete mathematics.
Textbook
| [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] |
Grading
- 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.