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: )
  Sign-up Instructions
Assignments
  HW #1
  HW #2
  HW #3
  HW #4
Lecture Notes
  Intro
  TM's and Halting Problem
  Intro to Complexity
  Complexity & Sorting
  Dynamic Programming I
  Dynamic Programming II
  Dynamic Programming III
  Divide and Conquer I
  Divide and Conquer II
  Divide and Conquer III
  Graphs and Graph Traversal
  Graph Traversal Applications
  More Graph Algorithms
  Greedy Graph Algorithms
  Pattern Matching
  P, NP, & NP-completeness
  More NP-completeness
  Dealing with NP-completeness
Reading Assignments
  Chapter 6 of Skiena
  Chapter 4 of Skiena
  Chapter 3 of Skiena
  Chapter 2 of Skiena
  Chapter 1 of Skiena
  Sipser Sampler
  Turing & Post Handout
Cool Links
  Craig's Halting Problem Page
  David Hilbert Bio
  Kurt Godel Bio
  Alonzo Church Bio
  Alan Turing Bio
   

Paul Beame

MWF 1230-120  at  MGH 231

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 Location Phone
Instructor: Paul Beame   beame@cs   MW 1:20-2:00, F 2:00-3:00 Sieg 416 543-5114
TAs: Deepak Verma   deepak@cs   Tu 12:00-1:00  Sieg 226A
Michael Nelson   nelsonmj@cs   Th   3:30-4:30 Sieg 226B

Grading: Homework, both pencil and paper and programming, Midterm, Final. Overall weights very roughly: homework 35-50%, midterm 15-25%, final 30-40%, give or take.

Textbooks

In addition, I will borrow a small amount of material from Michael Sipser, Intro. to the Theory of Computation, PWS Publishing, 1997. A copy is on reserve in the Engineering Library. (Book Errata: first printing , second printing .)

These texts cover 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.

Mailing List: There is a class mailing list, cse417@cs.washington.edu. Follow the link in the left column on this page to sign up. Everyone is expected to be reading cse417 e-mail to keep up-to-date on the course.

Midterm Exam: Will be Friday, November 8 in class. Here is a sample midterm from a previous quarter. Obviously the course 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 certainly fair game:

  • Church-Turing Thesis
  • The fact that the Halting Problem is undecidable and how to use this fact to show that other problems are undecidable
  • Complexity analysis, T, Big-O, Omega, Theta
  • Recurrences
  • Divide and conquer
  • Dynamic programming
  • All the specific algorithms we've studied so far this quarter, with the exception of the exact details of Strassen's algorithm and the Fast Fourier Transform.

Final Exam: Will be Wednesday, December 18, 8:30-10:20 a.m. That will mean lots of time to study after the end of classes. Here is a sample final from a previous quarter. Review session: Will be Monday, December 16, 3:30-5:00 p.m. in Sieg 134. Here is a List of Topics for the Final.


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.