Computer Science

ECS 122A Algorithm Design and Analysis

ECS 122A ALGORITHM DESIGN AND ANALYSIS (4 units)

Format
Lecture: 3 hours
Discussion: 1 hour

Catalog Description:
Complexity of algorithms, bounds on complexity, algorithms for searching, sorting, pattern matching, graph manipulation, combinatorial problems, randomized algorithms, introduction to NP-complete problems.

Prerequisites: Courses 20, 60

Credit restrictions, cross listings: None

Summary of course contents

  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.

Goals: Students will: (1) learn methods for designing efficient algorithms, evaluating their performance, and ways of establishing precise limits on the possible effectiveness of classes of algorithms; and (2) learn standard algorithms for fundamental problems.

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

Computer Usage:
None

Engineering Design Statement:

ECS 122A ALGORITHM DESIGN AND ANALYSIS (4 units)

Format
Lecture: 3 hours
Discussion: 1 hour

Catalog Description:
Complexity of algorithms, bounds on complexity, algorithms for searching, sorting, pattern matching, graph manipulation, combinatorial problems, randomized algorithms, introduction to NP-complete problems.

Prerequisites: Courses 20, 60

Credit restrictions, cross listings: None

Summary of course contents

  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.

Goals: Students will: (1) learn methods for designing efficient algorithms, evaluating their performance, and ways of establishing precise limits on the possible effectiveness of classes of algorithms; and (2) learn standard algorithms for fundamental problems.

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

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

Student Outcomes:

  • An ability to apply knowledge of mathematics, science, and engineering
  • 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

GE3
Science & Engineering

Overlap: NP-completeness is also covered in course 120, but at a deeper level.

Instructors: N. Amenta, D. Gusfield, V. Filkov, M. Franklin, C. Martel, and P. Rogaway

History: 2012.09.28 (C. Martel): small updates to summary of course contents.   Changed short form of title. Prior version from C. Martel and P. Rogaway, October 2006.

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

Student Outcomes:

  • An ability to apply knowledge of mathematics, science, and engineering
  • 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

GE3
Science & Engineering

Overlap: NP-completeness is also covered in course 120, but at a deeper level.

Instructors: N. Amenta, D. Gusfield, V. Filkov, M. Franklin, C. Martel, and P. Rogaway

History: 2012.09.28 (C. Martel): small updates to summary of course contents.   Changed short form of title. Prior version from C. Martel and P. Rogaway, October 2006.

border