CSE 431: Introduction to Theory of Computation, Spring 2001

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:

Isaac Kunen (zook@cs.washington.edu)
Office hours: Wednesday 2:30 and Thursday 1:30 in Hub Atrium

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 6th. .ps .pdf
Assignment 2 due April 13th. .ps .pdf
Assignment 3 due April 20th. .ps .pdf
Assignment 4 due April 27th. .ps .pdf
Assignment 5 due May 4th. .ps .pdf
Assignment 6 due May 18th. .ps .pdf
Assignment 7 due May 25th. .ps .pdf

Project

Project description .ps .pdf
Proposal due on or before May 11, 2001, 5:00 pm
Final Report due on or before June 1, 2001, 5:00 pm
Student Project Titles

Reading

3/26/01 - 4/1/01: Sipser: 3.1, 3.2; Davis: Chapter 1
4/2/01 - 4/8/01: Sipser: 3.3; Davis: Chapter 2
4/9/01 - 4/15/01: Sipser: 4.1, 4.2; Davis: Chapter 3
4/16/01 - 4/22/01: Sipser: 5.1, 5.2; Davis: Chapter 4
4/23/01 - 4/29/01: Sipser: 5.3; Davis: Chapter 5
4/30/01 - 5/6/01: Sipser: 7.1, 7.2; Davis: Chapter 6
5/7/01 - 5/13/01: Sipser: 7.3, 7.4; Davis: Chapter 7
5/14/01 - 5/20/01: Sipser: 7.5; Davis: Chapters 8 and 9
5/21/01 - 5/27/01: Sipser: 8.1, 8.2, 8.3
5/28/01 - 6/3/01:

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 27, 2001
Midterm study guide

Final Exam

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