Site Map | College of Engineering | UC Davis | MyUCDavis

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:

  1. Models of Computational Complexity
    1. RAM
    2. Turing machine
    3. Bit and arithmetic complexity
  2. Problem Classification
    1. P and NP
    2. Proving problems NP-complete
    3. P-space and exp.-time completeness
  3. Matching
    1. Algorithms for bipartite graphs
    2. Discussion of non-bipartite matching
  4. Network Flows
    1. Study of advanced flow algorithms
    2. Minimum cost flows
    3. Extensions to the model
    4. Application of flow
  5. Matrix Multiplication
    1. Fast algorithms by Strassen and others
    2. Order of matrix multiplication
  6. Approximation Algorithms
    1. General Techniques
    2. Applications to Knapsack
    3. Bin-packing
    4. Scheduling
    5. Limits of approximation
  7. Advanced Topics (selection from)
    1. Probabilistic algorithms
    2. Parallel algorithms
    3. Encryption techniques
    4. 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

Back to Course Descriptions