Gregor Reisch: Madame Arithmatica, 1508

## Administration

Design & Analysis of Algorithms

COMPSCI 532 • Fall 2016

Instructor: Pankaj K. Agarwal

TA: Reza Alijani

Time: Tue, Thu 4:40-5:55 pm

Location: LSRC D106

Office Hours:

Agarwal:Tue 3:30-4:30, Fri 3:00-4:00

Alijani:Mon 4:00-5:00, Wed 1:30-2:30 in LSRC D301

## Course Synopsis

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

- Linear Programming: Polyhedral combinatorics, simplex algorithm, duality, Farka's lemma, primal dual method,
polynomial-time algorithms
- Network Optimization Problems: Shortest paths, network flow, min cut, min cost flow, bipartite matching
- Intractability: NP-Completeness, polynomial-time reduction, PSPACE and beyond
- Greedy Algorithms: Set cover, vertex cover, multiplicative weight method, clustering
- Randomized Algorithms: Tail bounds, hashing, global min-cut, polynomial identity testing, Rabin-Karp finger
printing, LP rounding, SDP rounding, metric embedding
- Geometric Algorithms: Voronoi diagram, Delaunay triangulation, nearest neighbor searching, dimension reduction,
locality sensitive hashing
- Large Scale Computation: Streaming, sublinear algorithms, dimension reduction

## 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): 30%
- Midterm exams: 30%
- Final exam: 40%
- Both midterm and final 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