i COMPSCI 230

Administration

Gregor Reisch: Madame Arithmatica, 1508

Design and Analysis of Algorithms
COMPSCI 230 • Fall 2009

Instructor: Pankaj K. Agarwal
TA: Sayan Bhattacharya

Time: Tuesday, Thursday 4:25-5:40
Location: LSRC D106

Office Hours:
Instructor: Friday 1:00-2:00 pm or by appointment. Contact Susan Clear (sclear@cs.duke.edu) to set up an appointment.
TA: Tuesday, Thursday 2:00-3:00 pm in LSRC D343.

Overview

This course covers design and analysis of efficient algorithms at a grdaute level. Topics include:

  • Design Techniques: Divide-and-conquer, recurrence relations, prune and search, greedy algorithms, dynamic programming, randomization, local search.
  • Data structures: Binary search tree, randomized search tree, skip lists, hashing, union-find, amortization.
  • Graph algorithms: graph traversal, minimum spanning tree, shortest path, max flow, minimum cut, matching
  • Geometric algorithms: closest pair, Delaunay triangulation
  • Algebraic algorithms: polynomial identity testing, polynomial multiplication, FFT
  • Linear programming: Examples, geometry, duality, simplex algorithm, interior point methods
  • Intractability: Easy and hard problems, NP-Completeness, reducibility, approximation algorithms, limited space computation

Prerequisite

CPS130 or equivalent

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.
[Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.

Grading

  • Assignments (six) 30%
  • Midterm (October 15) 30%
  • Final (December 11) 40%
  • Both midterm and final will be in-class closed-book exams
  • Students are expected to do assignments on your own
  • Quals grade will be based on midterm and final

page top