CSE 431: Introduction to Theory of Computation, Spring 2005

Steam-powered Turing Machine

University of Washington Computer Science & Engineering

CSE 431: Introduction to Theory of Computation, Spring 2005

Instructor:

Venkatesan Guruswami (venkat@cs)
Office: Allen 656, Ph: 685-1959
Office Hours: Wed 11:30-12:30

Teaching Assistant

Ioannis Giotis (giotis@cs)
Office hours: Thursday 2:00-3:00pm
CSE 220

Meeting Times:

Monday, Wednesday, and Friday, 10:30-11:20am.
Location: MGH 241.

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 Fridays
Your lowest homework score will be dropped.
Late solutions will NOT be accepted (unless PRIOR approval is obtained)
IMPORTANT, Please Read: Homework Policies
Problem set 1 (due Apr 8): ps pdf
Problem set 2 (due Apr 15): ps pdf
Problem set 3 (due Apr 22): ps pdf
Problem set 4 (due Apr 29): ps pdf
Problem set 5 (due May 13): ps pdf
Problem set 6 (due May 20): ps pdf
Problem set 7 (due May 27): ps pdf
Problem set 8 (due June 3): ps pdf

Handouts

Sample final: ps pdf
Sample midterm: ps pdf

Some historical links:

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

Midterm exam: In class, Wednesday, May 4, 2005.
Final exam: 8:30-10:20 a.m. Monday, Jun. 6, 2005.

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