CPS 230: The Design and Analysis of Algorithms
Fall 1998
Description:
This is a graduate level algorithms class. Algorithm design techniques
such as divide-and-conquer, dynamic programming, and greediness will be
introduced, and algorithms for e.g. sorting, searching, and graph problems
will be developed. Topics such as lower bound techniques and the notion
of NP-completeness will also be covered.
Lectures:
Tuesdays and Thursdays 10.55-12.10 in D106
Instructor:
Lars Arge
Office: D228 LSRC Bldg
Phone: 660-6557
E-mail: large@cs.duke.edu
TA:
Laura Toma
Office: D224 LSRC Bldg
Phone: 660-6583
E-mail: laura@cs.duke.edu
Course material:
The course will be based on:
- Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw
Hill, 1990 (bugs).
- Lecture notes and research papers (handouts).
Other good reference books include:
- A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms,
Addison Wesley 1974.
- G. Brassard and P. Bratley, Algorithmic - Theory and Practice,
Prentice Hall, 1988.
- R. Tarjan, Data Structures and Network Algorithms, SIAM Publications,
1983.
- D. Kozen, The Design and Analysis of Algorithms, Springer Verlag,
1991.
- C. H. Papadimitriou, Computational Complexity, Addison Wesley,
1994.
Course Synopsis:
- Mathematical foundation: Growth of functions, summations, recurrences
- Divide-and-conquer
- Sorting: mergesort, quicksort
- Selection
- Computational models and lower bounds
- Searching: Search trees, red-black trees, augmented search trees,
van Emde Boas trees
- Amortized analysis: Weight-balanced search trees, splay trees
- External memory algorithms: External sorting, (a,b)-trees
- Priority queues: Heaps, binomial heaps, Fibonacci heaps
- Greedy algorithms
- Dynamic programming
- Graph algorithms: Breadth-first search, depth-first search, minimal
spanning trees, shortest paths
- Union-Find structures
- Fast Fourier Transform
- NP-completeness
Summary of Lectures:
A summary of the lectures held so far, a list of the material covered,
handouts, along with information about what is approximately going to happen
in the next lectures, can be found here.
Grading:
Class grade will probably be based on:
- Homework assignments (approx. 40%).
- Two midterm and a final exam (approx. 60%).
Homework Assignments:
Homeworks will be assigned at the first
class meeting of approximately every second week and are always due the
second class of the following week. Collaboration is permitted (in fact,
encouraged) but students must write up solutions on their own. LaTeX should
be used for typesetting.
Newsgroup
Course Feedback
Links:
- Michael Littman's CPS130
page - contains links to some nice algorithmic animations.
Lars Arge
Last modified: Mon Sep 7 21:34:18 1998