CSE 431: Introduction to Theory of Computation, Spring 2008

CSE Home

About Us

Search

Contact Info

Mailing List:

• It is important to subscribe to the class mailing list immediately. Everyone is expected to be reading cse431 e-mail to keep up-to-date on the course.
• To subscribe to the CSE 431 mailing list, visit http://mailman.cs.washington.edu/mailman/listinfo/cse431. 

Problem Sets 

• Assigned weekly, about 7 or 8 of them, generally due on Thursdays  
• Late solutions will NOT be accepted (unless PRIOR approval is obtained)
• IMPORTANT, Please Read:    Homework Policies
  
  
• Problem set 1 (due Apr 10): ps pdf
• Problem set 2 (due Apr 17): ps pdf
• Problem set 3 (due Apr 24): ps pdf
• Problem set 4 (due May 1): ps pdf
• Problem set 5 (due May 15): ps pdf
• Problem set 6 (due May 27): ps pdf
• Problem set 7 (due May 27): ps pdf

Handouts

• Sample finals: no. 1, no. 2

• Alan Turing's 1936 paper On computable numbers, with an application to the Entscheidungsproblem.
• Hilbert's 23 problems (Problems 2 and 10 are of relevance to this course.)
• Survey article by Yuri Matiyasevich: Hilbert's Tenth Problem: What can we do with Diophantine equations.

Text Book

• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.
• We will cover Chapters 3, 4, 5, parts of 6, 7, 8 plus perhaps few other topics depending upon time and interest.
• There is a list of errors in the first printing and errors in the second printing of the textbook available.

Exams

Grading (Rough split)

• Weekly assignments (35-45%)
• Midterm exam (15-20%)
• Final exam (35-40%)

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX