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