Design & Analysis of Algorithms
COMPSCI 530
Fall 2012
Gregor Reisch: Madame Arithmatica, 1508
Administration
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) |
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, 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
Prerequisite
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.
Textbook
| [KT] | J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005. |
Reference Books
| [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 |
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.
