CSE 417: Algorithms and Computational Complexity

Paul Beame, Winter 2001

MWF 11:30-12:20, Winkenwerder 201

Staff	Name	Email	Phone	Office Hours
Instructor:	Paul Beame	beame@cs	543-5114	M 12:30-1:00,2:30-3:00 W 1:00-2:00	Sieg 416
TA:	Gidon Shavit	gidon@cs	616-1847	W 10:30-11:00 Th 1:30-2:30	Sieg 226a

Class E-mail Archive: (Last update: .)
(This is a log of all messages sent to the class e-mail list.)
To send mail to the whole class, mail to: cse417@cs.washington.edu
Instructions on how to subscribe to the cse417 mailing list can be found here.

Textbooks::

• The main textbook for the course will be "The ALGORITHM design manual" by Steven Skiena, published by Springer-Verlag. The great thing about this text is that it is fun to read and will be a useful reference manual after the course is over. (There is also a list of errors available.)

• In addition, I will borrow a small amount of material from Michael Sipser, Intro. to the Theory of Computation, PWS Publishing, 1997. There is a list of errors in the first printing and errors in the second printing available.

  These texts cover quite different components of the material, the Skiena book covers algorithms and NP-completeness and the Sipser book covers computability and complexity. Both cover NP-completeness.

  Homework:

  Homework is intended to be a major portion of the course. Assignments will be due every week or two, usually on Friday. It is expected that homework solutions represent original work.
  Assignment #1
  Assignment #2
  Assignment #3
  Assignment #4
  Assignment #5

  Slides:

  Jan 3: Powerpoint| Postscript| PDF Jan 5: Powerpoint| Postscript| PDF
  Jan 8: Powerpoint| Postscript| PDF Jan 10: Powerpoint| Postscript| PDF Jan 12: Powerpoint| Postscript| PDF
  Jan 17: Powerpoint| Postscript| PDF Jan 19: Powerpoint| Postscript| PDF
  Jan 22: Powerpoint| Postscript| PDF Jan 26: Powerpoint| Postscript| PDF
  Jan 29: Powerpoint| Postscript| PDF Jan 31: Powerpoint| Postscript| PDF Feb 2: Powerpoint| Postscript| PDF
  Feb 5: Powerpoint| Postscript| PDF Feb 9: Powerpoint| Postscript| PDF
  Feb 12: Powerpoint| Postscript| PDF
  Feb 21: Powerpoint| Postscript| PDF Feb 23: Powerpoint| Postscript| PDF
  Feb 26: Powerpoint| Postscript| PDF Feb 28: Powerpoint| Postscript| PDF March 2: Powerpoint| Postscript| PDF
  March 5: Powerpoint| Postscript| PDF March 7: Powerpoint| Postscript| PDF March 9: Powerpoint| Postscript| PDF

  Feedback:
  Anonymous (or not) feedback form to tell us how things are going.

  Grading:

  The course grade will be based on homework, a midterm, and a final exam. The approximate weighting of the three components is 40-50% Homework, 15-25% midterm and 30-40% final exam.

  Reading Assignments

  Read Chapter 1 of Skiena's book
  Read Chapter 2 of Skiena's book
  Read Chapter 3 of Skiena's book
  Read Chapter 4 of Skiena's book
  Read Chapter 7 of Skiena's book
  Read Chapter 6 of Skiena's book
  Read Chapter 5 of Skiena's book (for fun & future use)
  

  Midterm

  Wednesday February 7th, 11:30-12:20 in class.
  Sample midterm

  Final Exam

  Wednesday March 14, 2:30-4:20 in class
  Sample final
  Review session room & time: EE1-045 March 13th from 100-220

  Syllabus

  • Analysis of Algorithms

  • Basic Algorithm Design Techniques

  • Graph Algorithms

  • Fast Fourier Transform

  • Pattern Matching & Finite Automata

  • Turing machines and Computability

  • Basics of Complexity

  • NP-completeness & Reductions

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

  ---

  Comments to:
  cse417-webmaster@cs.washington.edu
  (Last Update: )