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

Administrative
 FAQ
 Schedule
 Midterm Review (1-up, 4-up)
 Final Review (1-up, 4-up)
Email
 Mail archive
Assignments
 HW #1
 HW #2
 HW #3
 HW #4
 HW #5
      GraphGen
      Test Case
      C++ Turnin
      Java Turnin
 HW #6
      Test Case
      C++ Turnin
      Java Turnin
Lecture Notes
 1: Admin (1-up, 4-up)
 2: Overview & Example (1-up, 4-up)
 3: Complexity (1-up, 4-up)
  4-12: Dynamic Programming
      Fibonacci (1-up, 4-up)
      List Partition (1-up, 4-up)
      Longest Incr. Subseq. (1-up, 4-up)
      String Edit Distance (1-up, 4-up)
 13-17: Divide & Conquer (1-up, 4-up)
 18-24: Graphs, B/DFS, Artic. (1-up, 4-up)
 25-29: P & NP (1-up, 4-up)
   

Time: MWF 2:30-3:20
Place: Smi 205
Office Hours Phone
Instructor: Larry Ruzzo, ruzzo@cs, Tu 12:00- 1:00, CSE 554, 543-6298
Larry Ruzzo, ruzzo@cs, F 1:30- 2:20, CSE 554, 543-6298
TA: Yuhan Cai, yuhancai@cs, M 12:30- 2:20, CSE 216,

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

Mail archive of all mail sent to cse417@cs. Read it regularly or subscribe.
Please feel free to use this list to ask and/or answer questions about homework, lectures, etc.

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 due at the start of class on the due date. 10% off for one day late (Monday, for Friday due dates). See instructor if you slip even more.

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-2005, 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]