CSE 531: Automata, Computability, Complexity

Paul Beame, Autumn 1999

TTh 10:30-11:50, EE1 003



StaffNameEmailPhoneOffice Hours
Instructor Paul Beame beame@cs543-5114Wed 10:00-10:50, Fri 2:30-3:20Sieg 416
TA Ashish Sabharwal ashish@cs543-7798MW 11:30-12:20Sieg 226b


Class E-mail Archive (Last updated .)
(This is a log of all messages sent to the class e-mail list.)
To send mail to the whole class, mail to: cse531@cs.washington.edu
Instructions on how to subscribe to the cse531 mailing list can be found here.

Textbook
Michael Sipser, Intro. 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.

    We will cover material in Chapters 1,3-8 of the text. The course will emphasize material on computability and NP-completeness. Please read Chapter 1 right away.

    Homework
    Assignment #1 (Due Tuesday, October 12)
    Assignment #2 (Due Thursday, October 28)
    Assignment #3 (Due Tuesday, November 9)
    Assignment #4 (Due Tuesday, November 23)
    Assignment #5 (Due Tuesday, Decemeber 7)

    Handouts
    NFA to Regular Expressions
    Myhill-Nerode Theorem
    Minimizing Finite Automata

    Feedback
    Anonymous (or not) feedback form to tell us how things are going.

    Final Exam
    Friday December 10, 10:30-12:20 in class
    Old final exam in postscript or PDF

    Portions of the CSE 531 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 531 Web: Copyright 1999, Department of Computer Science and Engineering, University of Washington.
    Comments to:
    cse531-webmaster@cs.washington.edu
    (Last Update: )