
CSE Home  About Us  Search  Contact Info 
Paul BeameMWF 1230120 at MGH 231Catalog 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. NPcomplete problems and undecidable problems.
Grading: Homework, both pencil and paper and programming, Midterm, Final. Overall weights very roughly: homework 3550%, midterm 1525%, final 3040%, 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 NPcompleteness and the Sipser book covers computability and complexity. Both cover NPcompleteness. 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 email to keep uptodate 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:
Final Exam: Will be Wednesday, December 18, 8:3010: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:305: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: © 19932002, Department of Computer Science and Engineering, University of Washington. 