CPS 230: The Design and Analysis of Algorithms
Fall 2000
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:
Wed and Fri 2:20-3:35 in D106 (class was previously announced to
be Mon/Wed/Fri 2:20-3:10)
We will have classes a few Mondays 2:20-3:35 in order to make up for
cancelled Wed/Fri classes.
Instructor:
Lars Arge
Office: D205 LSRC Bldg
Phone: 660-6557
E-mail: large@cs.duke.edu
TA:
Lipyeow Lim
Office: D325 LSRC Bldg
Phone: 660-6586
E-mail: lipyeow@cs.duke.edu
Office Hours:
-
Thursday: 1:00pm - 2:30pm
-
Friday : 10:30am - 12:00pm
-
by appointment (call or email).
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.
-
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
Lars Arge
Last modified: Mon Nov 20 17:01 EDT 2000