Gregor Reisch: Madame Arithmatica, 1508
Design and Analysis of Algorithms
COMPSCI 130 • Spring 2012
Instructor: Pankaj K. Agarwal
TA: Janardhan Kulkarni
Times & Locations
|Lectures:||Tue, Thu 2:50-4:05 pm|
in LSRC D106
|Recitations||Fri 10:05-11:20 am|
in LSRC D106
|Agarwal:||Tue 4:30-5:30 pm|
Fri 2:00-3:00 pm
|Kulkarni:||Mon 4:00-5:00 pm|
Wed 4:00-5:00 pm
This undergraduate course covers techniques for designing and analyzing algorithms and data structures for a wide range of problems. Topics include:
- Design Techniques: Divide-and-conquer, recurrence relations, prune and search, greedy algorithms, dynamic programming, randomization, local search
- Data structures: Binary search tree, red-black tree, skip list, hashing, union-find, amortization
- Graph algorithms: graph traversal, strongly connected components, minimum spanning tree, shortest path
- Geometric algorithms: closest pair, convex hull, Delaunay triangulation
- Algebraic algorithms: polynomial identity testing, polynomial multiplication, FFT, primality testing, cryptography
- Intractability: Easy and hard problems, NP-Completeness, reducibility, approximation algorithms
CPS100 and 102, or equivalent courses. This course requires undergraduate background in data as well as a certain amount of mathematical sophistication.
- [DPV]S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.
- [KT]J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (optional).
|[AHU]||A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.|
||T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.|
||R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.|
- Assignments (six): 30%
- Midterm exams (two): 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 expected to use Latex or MS-Word for writing their assignments and pdf or ps files to submit their assignments.
- No credit is given for late solutions.