#
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:
)