Design & Analysis of Algorithms

COMPSCI 532

Fall 2014

Gregor Reisch: Madame Arithmatica, 1508

Administration

Design and Analysis of Algorithms
COMPSCI 532 • Fall 2014

Instructor: Pankaj K. Agarwal

TA: Abhinandan Nath

Time: Tue Thu 1:25-2:40 pm

Location: LSRC D106

Office Hours

Agarwal: Tue 3:00-4:00, Fri 2:00-3:00
Nath: Mon 1:45-2:45, Thu 10:30-11:30

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

Prerequisite

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

Textbook

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

Reference Books

[CLRS]T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
[DPV]S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.
[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.
  • 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.

page top