Catalog Description: Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 322.

			Office Hours	Location	Phone
Instructor:	Paul Beame	beame@cs	Mondays & Wednesdays 11:20-11:50 Thursdays 11:00-12:00 & by appointment	Sieg 416	543-5114
TA:	Erik Vee	env@cs	Tuesdays 12:30-1:20 & Thursdays 12-1	Sieg 4th floor cubicles

Grading: Homework 45-55%, Midterm 15-20%, Final 30-35%, give or take. Extra Credit.

Textbook:

Michael Sipser, Intro. to the Theory of Computation, PWS Publishing, 1997. A copy is on reserve in the Engineering Library. (Book Errata: first printing , second printing .

http://www.cs.washington.edu/431

Mailing List: There is a class mailing list, cse431@cs.washington.edu. Follow the link in the left column on this page to sign up. Everyone is expected to be reading cse431 e-mail to keep up-to-date on the course.

Midterm Exam: In class either May 7 or May 9.

Final Exam: The final exam will be at the time listed in the official exam schedule which is 8:30-10:20 am, Monday June 9.

Homework There will be weekly homework sets, generally due on Fridays. Homework should be handed in at the beginning of lecture on the day it is due. Late homeworks will not receive credit. (If a genuine emergency situation prevents you from handing in an assignment on time, come talk to one of us and we can work something out. Similarly, if you can anticipate an extraordinary or unusual circumstance that will necessitate an extension, please talk to us ahead of time.)

Disability Accommodations If you would like to request academic accommodations due to a disability, please contact Disabled Student Service, 448 Schmitz, 543-8924 (V/TDD). If you already have a letter from Disabled Student Services indicating that you have a disability that requires academic accommodations, please let the instructor know so we can discuss the appropriate accommodations.