Skip navigation

Site Map | College of Engineering | UC Davis | MyUCDavis

ECS 122A ALGORITHM DESIGN AND ANALYSIS (4) I, II, III

Lecture: 3 hours

Discussion: 1 hour

Prerequisites: Courses 20, 60

Grading: Letter; written assignments (30%), examinations (70%)

Catalog Description:
Complexity of algorithms, bounds on complexity, algorithms for searching, sorting, pattern matching, graph manipulation, combinatorial problems, introduction to NP-complete problems. Not open to students who have taken ECS 122.

Expanded Course Description:

  1. Complexity of algorithms, bounds on complexity.
  2. Searching, sorting, pattern matching, graph algorithms.
  3. Solving large combinatorial problems by exhaustive search.
  4. Back-tracking, branch-and-bound technique.
  5. Approximate methods. NP-complete problems.
Textbook:
T. Cormen and C. Leiserso, Introduction to Algorithms, McGraw-Hill, 2001

Computer Usage:
None

Engineering Design Statement:
Written assignments often (25-50% of time) contain problems involving the design and analysis of algorithms for a particular type of computer system. The students are given a general description of the problem to be solved and the general parameters of the computer system which is to be used to solve the problem. The students are then expected to design a detailed solution consisting of both standard routines and new routines which they design. They are also expected to justify the correctness of their solution and to analyze its expected performance. Examination questions also test the design and analysis techniques learned through the homework assignments.

ABET Category Content:

Engineering Science: 2 units
Engineering Design: 1 unit

Goals:
Students will:

Student Outcomes:

Instructors: C. Martel, D. Gusfield, P. Rogaway

Prepared by: P. Rogaway, C. Martel (October 2006)

Overlap Statement:
This course does not duplicate any existing course.

Back to Course Descriptions