### ECS 222B ADVANCED DESIGN AND ANALYSIS OF ALGORITHMS (4) II

**Lecture**: 3 hours

**Project**: 1 hour

**Prerequisite**: Course ECS 222A

**Grading**: Letter; problem sets (40%), midterm (40%), project (20%)

**Catalog 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.

**Goals:**

Students learn about advanced algorithms and techniques for classifying and dealing with hard problems. Students also get experience applying these algorithms to applications through home- work and a class project.

**Expanded Course Description:**

- Models of Computational Complexity
- RAM
- Turing machine
- Bit and arithmetic complexity

- Problem Classification
- P and NP
- Proving problems NP-complete
- P-space and exp.-time completeness

- Matching
- Algorithms for bipartite graphs
- Discussion of non-bipartite matching

- Network Flows
- Study of advanced flow algorithms
- Minimum cost flows
- Extensions to the model
- Application of flow

- Matrix Multiplication
- Fast algorithms by Strassen and others
- Order of matrix multiplication

- Approximation Algorithms
- General Techniques
- Applications to Knapsack
- Bin-packing
- Scheduling
- Limits of approximation

- Advanced Topics (selection from)
- Probabilistic algorithms
- Parallel algorithms
- Encryption techniques
- Scheduling theory

**Textbook:**

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

**Project/Design Statement:**

The course requires an in depth project involving the design, implementation, and experimental evaluation of an advanced algorithm.

**Instructors:** D. Gusfield, M. Franklin, C. Martel, P. Rogaway

**Prepared by:** C. Martel (December 2001)

**Overlap Statement:**

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

12/01