Home » Courses » Course Descriptions

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:

Program Outcomes:

  • The ability to work independently
  • The ability to apply knowledge of basic science, mathematics and engineering principles to solve computing and information processing problems
  • The ability to write correct and good programs
  • The ability to understand the relationship between hardware and software
  • The ability to understand the tradeoffs in the design of hardware systems, software systems, processes and components
  • The ability to construct appropriate abstractions to manage complexity and to think creatively about new problems
  • The ability to use experimental methods on software systems by gathering data to improve the systems
  • The ability to acquire the foundations to do well in graduate school
  • The ability to acquire the foundations to be a life-long learner

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

    Prepared By: C. Martel (October 1996)

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

    5/06