ECS 122A: Algorithm Design and Analysis

Subject
ECS 122A
Title
Algorithm Design and Analysis
Status
Active
Units
4.0
Effective Term
2019 Winter Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
Complexity of algorithms, bounds on complexity, analysis methods. Searching, sorting, pattern matching, graph algorithms. Algorithm design techniques: divide-conquer, greedy, dynamic programming. Approximation methods. NP-complete problems. GE Prior to Fall 2011: SciEng. GE: SE.
Prerequisites
ECS 020; (ECS 060 or ECS 032B or ECS 036C)
Enrollment Restrictions
Pass One open to Computer Science, Computer Science Engineering, Computer Engineering, and Applied Physics Majors only.

Summary of Course Content

  1. Complexity of algorithms, bounds on complexity, analysis methods.
  2. Searching, sorting, pattern matching, graph algorithms.
  3. Algorithm design techniques: divide-conquer, greedy, dynamic programming.
  4. Approximation methods. NP-complete problems. 

Illustrative Reading

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 3rd edition. The MIT Press, 2009.

Potential Course Overlap

There is no significant overlap with other courses.

Course Category

Upper Division