Staff | Name | 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: )