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

Administrative
 FAQ
 Schedule
 Final Review (1-up, 4-up)
Email
 Mail archive
Assignments
 HW #1
 HW #2
 HW #3
 HW #4
 HW #5
 HW #6
Lecture Notes
 1: Overview & Example (1-up, 4-up)
 2-3: Analysis (1-up, 4-up)
 4-6: Graphs, B/DFS (1-up, 4-up)
  7-11: Greedy
      Scheduling (1-up, 4-up)
      Huffman (1-up, 4-up)
  12-15: Dynamic Programming
      Fibonacci (1-up, 4-up)
      Stamps (1-up, 4-up)
      RNA Structure (1-up, 4-up)
      Scheduling (1-up, 4-up)
 16-19: Divide & Conquer (1-up, 4-up)
 20-26: P & NP (1-up, 4-up)
   

Time: MWF 2:30-3:20
Place: Low 101 (schematic)
E-mail Office Hours Phone
Instructor: Larry Ruzzo ruzzo@cs,  MF 12:00- 1:00,  CSE 554,  543-6298
TA: Paul Pham ppham@cs,  Th 2:00- 3:00,  CSE 216,  685-3871

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

Class email lists: cse417a_wi06@u.washington.edu. Use this list to ask and/or answer questions about homework, lectures, etc. The instructor and TA are subscribed to this list, and will answer questions, but I almost always find that the questions and answers are of general interest, and that your fellow students often will answer more quickly (and more clearly) than the staff can. Students should be automatically subscribed within 24 hours of registration. You can modify your subscription options. All messages are automatically archived. General information about the email system is here. Questions not of general interest should be directed to the instructor and/or TA.

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 one day late (business day, e.g., Monday for Friday due dates); additional 20% per day thereafter.

Textbook:

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-2006, 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
[comments to cse417-webmaster@cs.washington.edu]