CSE 417: Algorithms and Computational Complexity
Paul Beame, Winter 2000
MWF 11:30-12:20, Loew 106
| Staff | Name | Email | Phone | Office Hours |
|---|
| Instructor: |
Paul Beame |
beame@cs | 543-5114 | W 4:00-5:00 and after class | Sieg 416 |
| TA: |
Ashish Sabharwal |
ashish@cs |
543-7798 | TTh 11:00-11:50 | Sieg 226
(1st 1/2 hour Th in hall) |
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::
There will be two textbooks for the course.
- The main one will be
Introduction to Algorithms: A creative approach by Udi Manber,
Addison-Wesley.
- The secondary one is
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 Manber
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 weekly, usually on Friday. It is expected that
homework solutions represent original work.
Assignment #1 (Due Wednesday, January 19)
Assignment #2 (Due Friday, January 28)
Assignment #3 (Due Friday, February 11)
Assignment #4 (Due Monday, February 28)
Assignment #5 (Due Friday, March 10)
Slides:
Knapsack Problem
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 the induction review in Manber's text
Read chapter 3 in Manber's text
Read sections 6.2, 6.4.1-6.4.4 in Manber's text
Read chapter 5 in Manber's text
Read section 6.8 in Manber's text
Read chapter 7, sections 7.1, 7.3-7.8 in Manber's text
Midterm
Wednesday February 9th, 11:30-12:20 in class.
Sample algorithms exam questions
Postscript
or PDF (Acrobat Reader)
Midterm Solutions
Postscript or
PDF (Acrobat Reader)
Final Exam
Wednesday March 15, 2:30-4:20 in class
Review sheet
Syllabus
- Review of Induction
- 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 1999,
Department of Computer Science and Engineering, University of
Washington.
Comments to:
cse417-webmaster@cs.washington.edu
(Last Update:
)