Time Schedule:
Steven L Tanimoto
CSE 417
Seattle Campus
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.
