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