Site Map | College of Engineering | UC Davis | MyUCDavis

ECS 222A DESIGN AND ANALYSIS OF ALGORITHMS (4) I

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Course ECS 122A; Statistics 131A recommended

Grading: Letter; problem sets and projects (40%), midterm (25%), final (35%)

Catalog Description:

Techniques for designing efficient algorithms, analyzing their complexity and applying these algorithms to a broad range of application settings. Methods for recognizing and dealing with hard problems are studied.

Goals:

Students learn advanced techniques for the design and analysis of algorithms. They learn to apply these to efficiently solve real problems, and to determine which problems are intractable.

Expanded Course Description:

  1. Overview of Algorithm Design and Analysis
    1. Design techniques
    2. Classes of algorithms
    3. Analysis techniques
  2. Dynamic Programming
  3. Probabalistic Analysis and Randomized Algorithms
  4. Advanced Graph Algorithms
    1. All pairs Shortest paths
    2. Connectivity
    3. Network flow
  5. Advanced Data structures and Amortized Analysis
  6. String Matching and Suffix Trees
  7. Lower bounds
  8. The Classes P and NP
    1. NP-hard and NP-complete problems
    2. Use of reductions
    3. Dealing with NP-complete problems
  9. Approximation algorithms
  10. Selected Advanced Topics
    1. Number theoretic algorithms
    2. Computational geometry
    3. Parallel algorithms

Textbook:

T. Cormen, C. Leiserson, R. Rivest, An Introduction to Algorithms, McGraw Hill, 2001 (second edition)

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

Prepared by: C. Martel (October 2001)

10/01

Back to Course Descriptions