Gregor Reisch: Madame Arithmatica, 1508
Administration
Design & Analysis of Algorithms
COMPSCI 532 • Fall 2019
Instructor: Pankaj K. Agarwal
TA: Erin Taylor
Time: Mon, Wed 1:25-2:40 pm
Location: LSRC D106
Office Hours:
Agarwal: Mon, Wed 2:50-3:50 pm
Taylor: (in D301) Tues 3-4, Fri 11-12
Course Synopsis
This course covers design and analysis of efficient algorithms at a graduate level. Topics include:
- Linear Programming: Polyhedral combinatorics, LP algorithms, duality, multiplicative weight method
- Network Optimization Problems: Max flow, min cut, min cost flow, bipartite matching
- Approximation Algorithms: Greedy algorithms, local-search, primal-dual method
- Randomized Algorithms: Tail bounds, hashing, global min-cut, LP rounding, SDP rounding, metric embedding
- Similarity Search: Nearest neighbor searching in low dimensions, dimension reduction, locality sensitive hashing
- Algebraic and Numerical Algorithms: Graph Laplacian, Markov chains, basic optimization techniques
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. |
Reference Books
| [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. |
| [WS] | D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. |
Grading
- Assignments (four out of five): 40%
- Two midterm exams: 60%
- Both midterms will be in-class closed-book exams.
- Students are required to use Latex or MS-Word for writing their assignments and to submit the pdf files of their assignments.
- No credit is given for late solutions.
Collaboration Policy
For assignments, collaboration among students is permitted, but students MUST write up solutions independently on their own and LIST your collaborators for each problem. The assignment questions may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.