image University of Washington Computer Science & Engineering
  CSE 417Wi '07:  Algorithms & Computational Complexity
  CSE Home   About Us    Search    Contact Info 

 Schedule & Reading
 Final Review (1-up4-up)
 Class List Archive
 HW #1
 HW #2
 HW #3
 HW #4
 HW #5
 HW #6
Lecture Notes
 1: Overview & Example (1-up4-up)
 2: Analysis (1-up4-up)
 3-5: Graphs, B/DFS (1-up4-up)
  6-10: Greedy
      Scheduling (1-up4-up)
      Huffman (1-up4-up)
  11-15: Dyn. Prog.
      Basics (1-up4-up)
      RNA Structure (1-up4-up)
      Scheduling (1-up4-up)
 16-19: Divide & Conquer (1-up4-up)
 20-26: P & NP (1-up4-up)

Lecture:  Low 101 (schematic) MWF 2:30- 3:20 
Office Hours Phone
Instructor:  Larry Ruzzo, ruzzo at cs  MF 12:00- 1:00  CSE 554  206-543-6298
TA:  Zizhen Yao, yzizhen at cs  Tu 12:00- 2:00  CSE 218 

Course Email: Use this list to ask and/or answer questions about homework, lectures, etc. The instructor and TA are subscribed to this list. All messages are automatically archived.  Questions not of general interest may be directed to the instructor and/or TA. You can (and perhaps should) change your subscription options.

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.


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, I recommend:

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-2007, Department of Computer Science and Engineering, University of Washington.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX