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 The ALGORITHM design manual by Steven Skiena, published by Springer-Verlag. (Book Errata.    Author's algorithm web site., Additional Book resource ) 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.