Skip navigation

Site Map | College of Engineering | UC Davis | MyUCDavis

ECS 122B ALGORITHM DESIGN AND ANALYSIS (4) III

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Course ECS 122A

Grading: Letter; projects (25%), homework (10%), midterm (25%), final (40%)

Catalog Description:
Theory and practice of hard problems, and problems with complex algorithmic solutions. NP-completeness, approximation algorithms, randomized algorithms, dynamic programming and branch and bound. Students do theoretical analysis, implementation and practical evaluations. Examples from parallel, string, graph, and geometric algorithms.

Expanded Course Description:

  1. NP-completeness theory in detail based on Turing machines.
  2. Examples of polynomial time reductions.
  3. Approximation algorithms.
  4. NP-completeness of certain near approximation problems.
  5. Randomized algorithms and adversaries.
  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.

Textbook:
T. Cormen and C. Leiserson,Introduction to Algorithms, McGraw-Hill, 1990.

Computer Usage
This class will use workstations as well as home machines. Part of the class will involve extensive computer usage.

Laboratory Projects:
Students will complete two to three large evaluations of competing algorithms or implementations.

Engineering Design Statement:
This course is heavily design oriented, exploiting both formal algorithm design methods and practical implementation.

ABET Category Content:
Engineering Science: 1 unit
Engineering Design: 2 units

Goals:
Students will:

Student Outcomes:

  • An ability to apply knowledge of mathematics, science, and engineering
  • An ability to design and conduct experiments, as well as to analyze and interpret data
  • An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
  • An ability to identify, formulate, and solve engineering problems
  • A recognition of the need for, and an ability to engage in life-long learning
  • An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice

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

    Prepared By: C. Martel (October 1996)

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

    Back to Course Descriptions