CSE 531: Computability and Complexity, Fall 2004
Office: Allen 656; Phone: 685-1959
Office hours: Thursdays 4:30-5:30pm
Atri Rudra (
Office hours: Mon 3:30-4:30pm, Wed 1:30-2:30pm at CSE 220.
Tuesdays and Thursdays 12-1:20 pm, at
Problem Sets and Hadnouts
Problem set #0 (no need to turn in):
Solutions to Problem set #0 :
Problem set #1 (due Oct 19, 2004):
Lecture notes on Kolmogorov complexity (Oct 19, 2004):
Problem set #2 (due Nov 2, 2004):
Problem set #3 (due Nov 16, 2004):
Problem set #4 (due Nov 30, 2004):
Problem set #5 (due Dec 9, 2004):
Sample final exam:
CSE 531 E-mail Group
To subscribe to the CSE 531 E-mail Group, visit
All e-mail to cse531 is posted in the
(last updated[an error occurred while processing this directive] ).
Introduction to the Theory of Computation
PWS Publishing, 1997.
There is a list of
errors in the first printing
errors in the second printing
of the textbook available.
Simple LaTeX & Visio example of 531-relevant stuff
Department of Computer Science & Engineering
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX