Course Announcement:

CSCI 5454: Design and Analysis of Algorithms, Spring, 2002

M W 4:00 -- 5:15, ECCS 1B28
Hal Gabow, ECOT 624,
Undergraduate courses in both data structures & discrete mathematics
e.g., CSCI 2270 & former CSCI 2224, or their equivalents
Weekly problem sets (with 1 or 2 small programming assignments).

Topical Outline
Our goal is to learn how to design and analyze efficient algorithms.
We achieve this by studying

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.