CSE P5 31: Computability and Complexity, Winter 2009

Steam-powered Turing Machine

University of Washington Computer Science & Engineering

CSE 531: Computability and Complexity, Winter 2009

IMPORTANT ANNOUNCEMENTS:

Here is the schedule for project presentations.
Here is the 6th homework.
Here is information about the projects.
Slides are here.
You can send the course's instructor and TA anonymous feedback here
The course's mailing list is set up. Please subscribe here.

Instructor:

Anna R. Karlin (karlin@cs)
Office: Allen 594, Ph: 543-9344
Office Hours: by appointment

Teaching Assistant

Cam Thach Nguyen (ncthach@cs)
Office hours: Tues 5:30 -6:30pm
in class

Meeting Times:

Tuesdays, 6:30 -- 9:20pm.
Location: CSE 403

Text Books

Main text: Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, 2009.
Also highly recommended: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.

We will use this book especially for Chapters 3, 4 and 5.
There is a list of errors in the first printing and errors in the second printing of the textbook available.

Problem Sets

Problem Set 1, due Jan 23. Suggested Solution
Problem Set 2, due Jan 30. Suggested Solution
Problem Set 3, due Feb 6. Suggested Solution
Problem Set 4, due Feb 13. Suggested Solution
Problem Set 5, due Feb 20. Suggested Solution
Problem Set 6, due Mar 14. Suggested Solution

Some interesting links:

Alan Turing's 1936 paper On computable numbers, with an application to the Entscheidungsproblem.
A New Yorker article about Alan Turing.
Hilbert's 23 problems (Problems 2 and 10 are of relevance to this course.)
An interesting popular review of a book about Kurt Godel.
A New Yorker article: "What were Einstein and Godel talking about?"
A wonderful article

Grading (Rough split)

Weekly assignments (70%)
Project (30%)


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