The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 417: Algorithms & Computational Complexity, 2002
  CSE Home  About Us    Search    Contact Info 

Prerequisites
 CSE 373
Email
 Archive (Last Msg: )
Assignments
 HW #1
 HW #2
 HW #3
 HW #4
 HW #5
 HW #6
Lecture Notes
 0: Admin
 1: Overview & Example
 2: Complexity, I
 3: Complexity, II
  4-8: Dynamic Programming
      Fibonacci
      List Partition
      Longest Increasing Subsequence
      String Edit Distance
 9-13: Divide & Conquer
 14: Midterm Review
  15-20: Graph Algorithms
      B/DFS, Articulation
      Strongly Connected Components
  21-23: Computability Theory
      Decidability and Reductions
  24-26: Complexity Theory
      P, NP, and Reductions, I
      P, NP, and Reductions, II
   

Larry Ruzzo

MWF 1130-1220 MEB 246

Catalog Description: 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.

Office Hours Phone
Instructor: Larry Ruzzo   ruzzo@cs   MTh   12:30- 1:20   Sieg 415   543-6298
TAs: Justin Campbell   jmc@cs   Tu   11:30- 12:20   Sieg 226  
Bill Pentney   bill@cs   W   12:30- 1:20   Sieg 226  

Grading: Homework, Midterm, Final, possible programming project. Overall weights very roughly: HW 30-45%, midterm 15-25%, final 35-50%, project 10-25%, give or take.

Textbooks:

These texts cover quite different components of the material, the Skiena book covers algorithms and NP-completeness and the Sipser book covers computability and complexity. Both cover NP-completeness.

Short biographies of David Hilbert, Kurt Gödel, Alonzo Church and Alan Turing.

Mailing List: There is a class mailing list. Send an email to majordomo@cs.washington.edu with no Subject and with a body that consists of subscribe cse417 on a single line.

Midterm Exam: Will be Monday, February 11, 2002. Here is a sample midterm from a previous quarter. Obviously they covered slightly different material that year, so don't take it too literally, but it will give you some idea of the kinds of questions I might ask. All the following are are certainly fair game:

  • Complexity analysis, Big-O, Θ, Ω
  • Recurrences
  • Divide and conquer
  • Dynamic programming, and
  • All the specific algorithms we've studied this quarter.

Final Exam: Will be Wednesday, March 20, 2:30-4:20. Here is a sample final from a previous quarter. As above, they covered slightly different material that year, so don't take it too literally. The exam is comprehensive. In particular, you may have a second chance at some of the kinds of problems that you missed on the midterm, so don't neglect reviewing earlier material. However, there may be a slight bias towards newer stuff:

  • Graph algorithms including breadth- and depth first search;
  • Applications thereof, including shortest paths, articulation points, connected-, biconnected-, and strongly connected components;
  • Computability theory, the halting problem, and reducibility;
  • Complexity theory, P, NP, NP-completeness, and polynomial time reducibility.

Portions of the CSE 417 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 417 Web: © 1993-2002, Department of Computer Science and Engineering, University of Washington.