Design & Analysis of Algorithms

COMPSCI 530

Fall 2012

Gregor Reisch: Madame Arithmatica, 1508

Design and Analysis of Algorithms

COMPSCI 530 • Fall 2012

Instructor: Pankaj K. Agarwal

TA: Yuqian Li

Time & Location

Tue, Thu 4:40-5:55 pm

Room LSRC D106

Office Hours

Agarwal: Tue 2:30-3:30, Friday 2:00-3:00 | |

TA: Tue, Fri 3:00-4:00pm (North 306) |

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, local search, 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, parallel/distributed computation

COMPSCI 130, or equivalent courses.This course requires undergraduate background in algorithms. Specifically, it assumes that students are familiar with first two-third of the material in COMPSCI 130 taught in Spring 2012.

[KT] | J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005. |

[DPV] | S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006. |

[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. |

[CLRS] | T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009. |

[PS] | C. Papadimitriou and K. Steigletz, Combinatorial Optimization. |

[DO] | S. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011 |

- Assignments (four out of five): 30%
- Midterm exams: 30%
- Final exam: 40%
- Both midterm and final will be in-class closed-book exams.
- For assignments, discussion among students is permitted, but students MUST write up solutions independently on their own. No materials or sources from prior years' classes or from the Internet can be consulted.
- 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.