CSE 431: Introduction to Theory of Computation, Spring 2002

University of Washington Department of Computer Science & Engineering

CSE Home

About Us

Contact Info

Instructor:

Richard E. Ladner (ladner@cs.washington.edu)
Office: Sieg 311, 543-9347
Office Hours: Tuesday and Thursday, 11:00-12:00

Teaching Assistant:

Ashish Sabharwal (ashish@cs.washington.edu)
Office hours: Wednesday 3:30-4:30 and Thursday 2:30-3:30 in Sieg 226a

Meeting Times:

Monday, Wednesday, and Friday 10:30 - 11:20 , MGB 251

CSE 431 E-mail Group

To subscribe to the CSE 431 E-mail Group send an e-mail message to majordomo@cs.washington.edu with subscribe cse431 in the body of the message. Your message should be sent from the e-mail account where you want to your class e-mail to arrive. Other commands for majordomo can be found by sending e-mail to majordomo with a blank message body. All e-mail to cse431 is posted in the E-mail Archive (last updated ).

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

Assignment 1 due April 12th. .pdf
Assignment 2 due April 19th. .pdf
Assignment 3 due April 26th. .pdf
Assignment 4 due May 10th. .pdf
Assignment 5 due May 17th. .pdf
Assignment 6 due May 24th. .pdf
Assignment 7 due May 31st. .pdf

Project

Project Description
Proposal due on or before May 13, 2001, 5:00 pm
Final Report due on or before June 7, 2001, 5:00 pm
Student Projects

Reading

4/1/02 - 4/7/02: Sipser: 3.1, 3.2; Davis: Chapter 1
4/8/02 - 4/14/02: Sipser: 3.3, 4.1, 4.2; Davis Chapters 2 and 3
4/15/02 - 4/21/02: Sipser: 5.1,5.2; Davis Chapters 4 and 5
4/22/02 - 4/28/02: Sipser: 5.3; Davis Chapter 6
4/29/02 - 5/5/02: Sipser: 6.2,6.3; Davis Chapter 7
5/6/02 - 5/12/02: Sipser: 7.1, 7.2, 7.3, 7.4; Davis Chapter 8
5/13/02 - 5/19/02: Sipser: 7.5; Davis Chapter 9
5/20/02 - 5/26/02: Sipser: 8.1, 8.2, 8.3, 8.4 5/27/02 - 6/1/02: 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, May 3, 2002
Midterm study guide

Final Exam

8:30-10:20 a.m. Monday, June 10, 2002
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