Title
Advanced Design & Analysis of Algorithms
Effective Term
2016 Spring Quarter
Learning Activities
Lecture - 3.0 hours
Project (Term Project) - 1.0 hours
Description
Advanced topics in complexity theory. Problem classification. The classes P, NP, P-space, co-NP. Matching and network flow algorithms. Matrix multiplication. Approximation algorithms.
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.
Summary of Course Content
I. Models of Computational Complexity
A. RAM
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
