ECS 222A: Design & Analysis of Algorithms

Summary of Course Content
I. Overview of Algorithm Design and Analysis
A. Design techniques
B. Classes of algorithms
C. Analysis techniques

II. Dynamic Programming

III. Probabalistic Analysis and Randomized Algorithms

IV. Advanced Graph Algorithms
A. All pairs Shortest paths
B. Connectivity
C. Network flow

V. Advanced Data structures and Amortized Analysis

VI. String Matching and Suffix Trees

VII. Lower bounds

VIII. The Classes P and NP
A. NP-hard and NP-complete problems
B. Use of reductions
C. Dealing with NP-complete problems

IX. Approximation algorithms

X. Selected Advanced Topics
A. Number theoretic algorithms
B. Computational geometry
C. Parallel algorithms

Illustrative Reading
T. Cormen, C. Leiserson, R. Rivest, An Introduction to Algorithms, McGraw Hill, 2001
(second edition)

Potential Course Overlap
This course does not have a significant overlap with any other course. It covers some of
the same general topics as ECS 122A and B (the undergraduate algorithms courses) but
does so at a more advanced and formal level. Topic VIII (P and NP) is also covered in
ECS 220 but the focus is quite different in the two classes (ECS 220 takes a much more
formal approach, while ECS 222A stresses the algorithmic implications).