CSE 431: Introduction to Theory of Computation, Spring 2004

University of Washington Department of Computer Science & Engineering

CSE Home

About Us

Contact Info

Instructor:

Richard E. Ladner (ladner@cs.washington.edu)
Office: CSE 632, 543-9347
Office Hours: Thursday 11:00 - 12:00

Teaching Assistant:

Ian Simon ( iansimon@cs.washington.edu)
Office hours: Tuesday 3:00 - 4:00 and Wednesday 3:00 - 4:00 in CSE 216

Meeting Times:

Monday, Wednesday, and Friday 10:30 - 11:20 , EE1 045

CSE 431 E-mail Group

To subscribe to or read CSE 431 e-mail list at CSE 431 e-mail. The main purpose of the e-mail group is to post announcements from the instructors.

Assignments are due on Friday (late assignments not accepted without prior approval).

Assignment 1 due April 9th. .pdf
Assignment 2 due April 16th. .pdf
Assignment 3 due April 23rd. .pdf
Assignment 4 due April 30th. .pdf
Assignment 5 due May 14th. .pdf
Assignment 6 due May 21st. .pdf
Assignment 7 due May 28th. .pdf

Project

Project Description
Proposal due Monday, May 10, by 5:00 pm
Paper due Friday, June 4, by 5:00 pm

Reading

3/29/04 - 4/4/04: Sipser: 3.1, 3.2; Davis: Chapters 1, 2
4/5/04 - 4/11/04: Sipser: 3.3, 4.1, 4.2; Davis Chapters 3, 4
4/12/04 - 4/18/04: Sipser: 5.1,5.2; Davis Chapters 5, 6
4/19/04 - 4/25/04: Sipser: 5.3; Davis Chapters 7, 8
4/26/04 - 5/2/04: Sipser: 6.2,6.3
5/3/04 - 5/9/04: Sipser: 7.1, 7.2, 7.3, 7.4; Davis Chapter 9
5/4/04 - 5/16/04: Sipser: 7.5; Davis Chapter 9
5/17/04 - 5/23/04: Sipser: 8.1, 8.2, 8.3, 8.4
5/24/04 - 5/30/04: Sipser: 8.5, 8.6, 9.1, 10.1, 10.2, 10.3

Text Books

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.
There is a list of errors in the first printing and errors in the second printing of the textbook available.
Martin Davis, The Universal Computer, W.W. Norton and Company, 2000

General Theory Resources

These resources may be helpful in your studies.

Midterm Exam

Friday, April 30, 2004
Midterm study guide

Final Exam

8:30-10:20 a.m. Monday, Jun. 7, 2004
Final Exam study guide

Grading

Weekly assignments (25%)
Midterm exam (20%)
Project (15%)
Final exam (40%)

Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to ladner]