# Instructor Class Description

Time Schedule:

**Steven L Tanimoto**

CSE 417

Seattle Campus

### Algorithms and Computational Complexity

Design and analysis of algorithms and data structures. Efficient algorithms for manipulating graphs and strings. Fast Fourier Transform. Models of computation, including Turing machines. Time and space complexity. NP-complete problems and undecidable problems. Intended for non-majors. Prerequisite: CSE 373.

**Class description**

Algorithm design, including design methods, important types of problems, analysis of algorithm efficiency, and proofs of correctness. Computational complexity, NP-completeness of problem classes, intractability of problem classes. Many algorithms for operating on graphs and sequences.

**Student learning goals**

Be able to analyze the running time of an algorithm in terms of the most relevant quantities.

Be able to design an efficient algorithm for a new class of problems.

Be able to prove that an algorithm correctly computes what it is supposed to.

Understand the workings of many important algorithms.

Understand NP-completeness in both theoretical and practical terms.

Understand intractability.

**General method of instruction**

Lectures and problem sets plus some computer programming.

**Recommended preparation**

CSE 373 is the official prerequisite. However, it will be helpful to review "big O", "big Omega" and "big Theta" definitions and usage. Also, review proof by induction, and review graph definitions and algorithms.

**Class assignments and grading**

Most assignments involve the analysis or creation of algorithms. Some assignments will involve programming. Recommended languages are Java and/or Python.

Grades will be based on a total score obtained as a weighted sum of several course component scores, including homework, midterm exam, and final exam.

*The information above is intended to be helpful in choosing courses. Because the instructor may further develop his/her plans for this course, its characteristics are subject to change without notice. In most cases, the official course syllabus will be distributed on the first day of class.*

*Additional Information*

Last Update by Steven L Tanimoto

Date: 11/01/2012