ECS 222B: Advanced Design & Analysis of Algorithms

ECS 222B
Advanced Design & Analysis of Algorithms
Effective Term
2016 Spring Quarter
Learning Activities
Lecture - 3.0 hours
Project (Term Project) - 1.0 hours
Advanced topics in complexity theory. Problem classification. The classes P, NP, P-space, co-NP. Matching and network flow algorithms. Matrix multiplication. Approximation algorithms.
ECS 222A
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.

Summary of Course Content
I. Models of Computational Complexity
B. Turing machine
C. Bit and arithmetic complexity

II. Problem Classification
A. P and NP
B. Proving problems NP-complete
C. P-space and exp.-time completeness

III. Matching
A. Algorithms for bipartite graphs
B. Discussion of non-bipartite matching

IV. Network Flows
A. Study of advanced flow algorithms
B. Minimum cost flows
C. Extensions to the model
D. Application of flow

V. Matrix Multiplication
A. Fast algorithms by Strassen and others
B. Order of matrix multiplication

VI. Approximation Algorithms
A. General Techniques
B. Applications to Knapsack
C. Bin-packing
D. Scheduling
E. Limits of approximation

VII. Advanced Topics (selection from)
A. Probabilistic algorithms
B. Parallel algorithms
C. Encryption techniques
D. Scheduling theory

Project/Design Statement:
The course requires an in depth project involving the design, implementation, and experimental evaluation of an advanced algorithm.

Illustrative Reading
T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, McGraw Hill, 2001

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 222A but does so at a more advanced and formal level. Topic II (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 222B stresses the algorithmic implications).

Course Category