ECS 122B: Algorithm Design & Analysis

Subject
ECS 122B
Title
Algorithm Design & Analysis
Status
Active
Units
4.0
Effective Term
2019 Winter Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
Theory and practice of hard problems, and problems with complex algorithm solutions. NP-completeness, approximation algorithms, randomized algorithms, dynamic programming and branch and bound. Theoretical analysis, implementation and practical evaluations. Examples from parallel, string, graph, and geometric algorithms. GE Prior to Fall 2011: SciEng. GE: SE, QL.
Prerequisites
ECS 122A; (ECS 060 or ECS 034 or ECS 036C)
Enrollment Restrictions
Pass One open to Computer Science, Computer Science Engineering, and Computer Engineering Majors only.

Summary of Course Content

  1. NP-completeness theory and implications for algorithm design.
  2. Examples of polynomial time reductions.
  3. Graph algorithms: network flow, min-cost flow, applications of network flow.
  4. Approximation algorithms.
  5. Randomized algorithms.
  6. Dynamic programming and practical speedups.
  7. Branch and bound methods for hard problems
  8. Computational studies of chosen algorithms and implementations. Emphasis on time versus space versus programming simplicity. What methods really work in practice versus theory. Use of timing and profiling tools.

Illustrative Reading

  • Jon Bentley, Programming Pearls, Addison-Wesley, second edition, 1999.
  • J. Kleinberg and É. Tardos, Algorithm Design, Addison-Wesley, 2005.

Potential Course Overlap

This course does not duplicate any existing course.

Course Category

Upper Division