CSE 417 : Algorithms and Computational Complexity
Dick Karp, Winter 1999
MWF 11:30 - 12:20, EE1 045
||karp@cs ||Mon 1:30-2:30, Tues 3:00 - 4:00, Sieg 219
||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 firstname.lastname@example.org, and as the only line in the body put
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 email@example.com in the to: field of your message. It is highly recommended that you subscribe to the mailing list.
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.
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.