CPS 130, Spring 2002
Introduction to the Design and Analysis of Algorithms
Lectures: Tue, Thu 12:40-1:55 in B101 LSRC
Recitation sessions: Thursday 9:10-10:00, Friday 10:30-11:20, 1:10-2:00,
and 3:55-5:10
This course builds on the study of the analysis and implementation of
algorithms and data structures from CPS100. The goal is to introduce a
number of important algorithms that are interesting both from a practical
and theoretical point of view. Algorithm design techniques such as divide-and-conquer
and dynamic programming will be discussed, and algorithms for e.g. sorting,
searching, and graph problems will be developed.
Instructor
Lars Arge
Office: D205 LSRC Bldg
Phone: 660-6557
Email: large@cs.duke.edu
Office hours: Tue/Thu 2:00-2:30 (and when otherwise available
in office)
Course Synopsis:
-
Mathematical foundation (Growth of functions, summations, recurrences)
-
Sorting and selection
-
Searching
-
Amortized analysis
-
Algorithm design techniques
-
Graph algorithms
-
Complexity
Course material:
-
Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms,
McGraw Hill, second edition 2001.
-
Handouts.
-
Lecture notes (available after each class).
Other good reference books include:
-
D. Kozen, The Design and Analysis of Algorithms, Springer Verlag,1991.
-
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.
Other undergraduate algorithm classes on the web:
<large@cs.duke.edu>
Last modified: Sat Dec 29 2001 by large.