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.

page top