CPS 230: The Design and Analysis of Algorithms
Fall 1999
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 2:15-3:30 in D106
Instructor:
Lars Arge
Office: D205 LSRC Bldg
Phone: 660-6557
E-mail: large@cs.duke.edu
TA:
Michail G. Lagoudakis
Office: D239 LSRC Bldg
Phone: 660-6598
E-mail: mgl@cs.duke.edu
People:
Click here for a picture and the names of
the students in the class.
Course material:
The course will be based on:
-
Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw
Hill, 1990 (bugs).
-
D. Kozen, The Design and Analysis of Algorithms, Springer Verlag,
1991 (not required).
-
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.
-
C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994.
Course Synopsis:
-
Mathematical foundation: Growth of functions, summations, recurrences
-
Divide-and-conquer
-
Sorting and 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, network flow
-
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%).
Grades and statistics can be found here.
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:
-
John Reif's CPS130
page - contains links to some nice algorithmic animations.
Lars Arge
Last modified: Tue Sep 7 18:05:04 EDT
1999