CSE 417, Wi '11: Algorithms & Computational Complexity

CSE Home

About Us

Search

Contact Info

Administrative   FAQ   Schedule & Reading Course Email   Subscription Options   Class List Archive Assignments   HW #1   HW #2   HW #3   HW #4   HW #5   HW #6 Lecture Notes  Introduction (4-up)  Analysis (4-up)  Graphs (4-up)  Greedy scheduling (4-up)  Huffman coding (4-up)  Minimum Spanning Trees (4-up)  Dynamic Programming Introduction (4-up)  Dynamic Programming and Scheduling (4-up)  Dynamic Programming: Segmented Squares, etc (4-up)  Dynamic Programming: Stereo correspondences (4-up)  Divide and Conquer (4-up)  Divide and Conquer: FFT (4-up)  Unrolling the FFT (4-up)  Review of stable matching (4-up)  Intractability (4-up)  NP-completeness (4-up)  Reductions (4-up)  PSPACE problems (4-up)  Review diagram (2-up)

Lecture:  EEB 045 (schematic) MWF 2:30-3:20   Office Hours Instructor:  Steve Tanimoto, tanimoto at cs  Mondays and Fridays 10:30-11:20 (CSE 638) TAs:  Jiun-Hung Chen, jhchen at cs  Tuesdays 4:00-5:00 (CSE 216); Fridays 3:30-4:20 (CSE 218)   Chris Raastad, craastad at cs  Mondays 3:30-4:20 (CSE 220); Thursdays 4:30-5:20 (CSE 218) (changed after HW3) Course Discussion Board: GoPost board 19786. Use this board to ask and/or answer questions about homework, lectures, etc. The instructor and TA are subscribed to this board. 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. Prerequisite: CSE 373 Credits: 3 Grading: Homework, Midterm, Final. Homework will be a mix of paper & pencil exercises and programing. Overall weights very roughly: HW 55%, midterm 15%, final 30%. Late Policy: Papers and/or electronic turnins are due at the start of class on the due date. 10% off for up to one day late (business day, e.g., Monday for Friday due dates); additional 20% per day thereafter. Textbook: Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006. (Available from the U Book Store, Amazon, etc.) Based on past experience, we will probably have little if any time to cover the "computability" material outlined in the catalog description. If you want additional material on these topics, as well as an alternative presentation of the computational complexity/NP-completeness topics, we recommend: Michael Sipser, Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005. Errata. (Available from Amazon, etc.) 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-2011, Department of Computer Science and Engineering, University of Washington.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to tanimoto]