**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: **ECS 020; (ECS 060 or ECS 032B or ECS 036C)

**Credit restrictions, cross listings**: None

**Summary of course contents**

- Complexity of algorithms, bounds on complexity, analysis methods.
- Searching, sorting, pattern matching, graph algorithms.
- Algorithm design techniques: divide-conquer, greedy, dynamic programming.
- 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.

**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: **Reviewed 2018.9.7 (CSUGA): prerequisites updated to include new lower division ECS series courses. 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: **Updated 2018.9.7 (CSUGA): prerequisites updated to include new lower division ECS series courses. 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.