ECS 222A: Design & Analysis of Algorithms

ECS 222A
Design & Analysis of Algorithms
Effective Term
2016 Spring Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Techniques for designing efficient algorithms, analyzing their complexity and applying these algorithms to a broad range of applications. Methods for recognizing and dealing with difficult problems.
ECS 122A; STA 031A recommended.
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.

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).

Course Category