Gregor Reisch: Madame Arithmatica, 1508

Administration

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
RecitationsFri 10:05-11:20 am
in LSRC D106

Office Hours

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

Overview

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

Prerequisite

CPS100 and 102, or equivalent courses. This course requires undergraduate background in data as well as a certain amount of mathematical sophistication.

Textbooks

  • [DPV]S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.
  • [KT]J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (optional).

Reference Books

[AHU]A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
[Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.

Grading

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

page top