## 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