CSCI 5454: Design and Analysis of Algorithms, Spring, 2002
Time
M W 4:00 -- 5:15, ECCS 1B28
Instructor
Hal Gabow, ECOT 624,
hal@cs.colorado.edu
Prerequisites
Undergraduate courses in both data structures & discrete mathematics
e.g., CSCI 2270 & former CSCI 2224,
or their equivalents
Requirements
Weekly problem sets (with 1 or 2 small programming assignments).
Texts
Introduction to Algorithms, 2nd Ed.
by T.H. Cormen, C.E. Leiserson, R.L. Rivest & C. Stein,
McGraw-Hill, New York, NY, 2001.
A collection of class notes written by the instructor
Topical Outline
Our goal is to learn how to design and analyze efficient algorithms.
We achieve this by studying
general techniques of algorithm design and analysis
specific areas of combinatorial computing,
and the associated algorithms
Unit 1. Fundamentals
sample unit: the technique of depth-first search
in graphs
asymptotic estimates, RAMs, polynomial time
introduction to public key cryptosystems
Unit 2. The divide-and-conquer technique
computational geometry, Fast Fourier Transform,
selection
introduction to randomized algorithms
Unit 3. The dynamic-programming technique
1- & 2-dimensional algorithms from text processing, computational
biology, etc.
Unit 4. The greedy technique
data compression (Huffman's algorithm), minimum spanning trees, etc.
Unit 5. Halving & Amortization
set merging, dynamic graph algorithms
credits, potential functions
Unit 6. Approximation algorithms
vertex cover & set cover, Travelling Salesman Problem
CSCI 3104:
The list of topics in CSCI 5454 has substantial
overlap
with CSCI 3104. The main new material is Unit 2 (long) & 5.
Also, the problem sets in CSCI 5454 are on a higher level.
If you have taken CSCI 3104 and plan to
also take CSCI 5454, please contact the instructor (email is fine).
Special arrangements will be made to supplement the
material you have already seen.