Lecture: 3 hours
Project: 1 hour
Prerequisite: Course ECS 222A
Grading: Letter; problem sets (40%), midterm (40%), project (20%)
Advanced topics in complexity theory. Problem classification. The classes P, NP, P-space, co-NP. Matching and network flow algorithms. Matrix multiplication. Approximation algorithms.
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:
T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, McGraw Hill, 2001
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)
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).