CSE 417 : Algorithms and Computational Complexity
Dick Karp, Winter 1999
MWF 11:30 - 12:20, EE1 045
| Staff | Name | Email | Office Hours |
|---|
| Instructor: |
Dick Karp |
karp@cs | Mon 1:30-2:30, Tues 3:00 - 4:00, Sieg 219 |
| TA: |
Frank McSherry |
mcsherry@cs | [Th, Fri] 2:30 - 3:30, Sieg 226[a, b] |
As well, there is a course mailing list. To suscribe to the list, send email to majordomo@cs.washington.edu, and as the only line in the body put
subscribe cse417
To unsubscribe form the list, replace the "subscribe" with "unsubscribe". Important messages may be sent out on the mailing list, particularly time critical messages. As well, it is also a good forum for general questions (not "how do you do question 3"). To send email to the list, put cse417@cs.washington.edu in the to: field of your message. It is highly recommended that you subscribe to the mailing list.
Assignments
Written assignments will be distributed on Wednesdays and then due the following Wednesday. About six such assignments are expected. Electronic versions of the homework will be made available here, as will solutions to the homeworks. Items that do not have links are not currently available.
Assignment 1 and the Solutions
Assignment 2 and the Solutions
Assignment 3 and the Solutions
Assignment 4 and the Solutions
Assignment 5 and the Solutions
Solutions to the study questions
for the final
As well, there will be a midterm and a final exam constituting 20% and 40% of the final grade, respectively.
Syllabus
The Church-Turing Thesis: Sipser, Chapter 3.
Decidability: Sipser, Chapter 4, Section 5.2.
Time Complexity: Sipser, Sections 7.1, 7.2.
Efficient algorithms operating on strings, integers and graphs.
NP-completeness. Sipser, Sections 7.3, 7.4, 7.5.
Coping with NP-completeness.