CSE 531: Automata, Computability, and Complexity, Fall 2000

CSE Home

About Us

Search

Contact Info

Instructor:

• Richard E. Ladner (ladner@cs.washington.edu)
• Office: Sieg 311, 543-9347
• Office Hours : Drop in any time or e-mail to make appointment

Teaching Assistant:

• Zasha Weinberg (zasha@cs.washington.edu)
  Office hours: Mon, 4:30-5:30, Sieg 226a; Fri, 3:30-4:30, Sieg 226b.

Meeting Times:

• Tuesday and Thursday 10:30 pm - 11:50 pm, EE1 025

CSE 531 E-mail Group

• To subscribe to the CSE 531 E-mail Group send an e-mail message to majordomo@cs.washington.edu with subscribe cse531 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 cse531 is posted in the E-mail Archive (last updated [an error occurred while processing this directive]).

Assignments

• Assignment 1: .ps .pdf
• Assignment 2: .ps .pdf
• Assignment 3: .ps .pdf
• Assignment 4: .ps .pdf
• Assignment 5: .ps .pdf
• Assignment 6: .ps .pdf
• Assignment 7: .ps .pdf due Tuesday, November 21.
• Assignment 8: .ps .pdf due Thursday, November 30.

Notetaking and Other Activities

Class Notes

• A context-free grammar for the language u#v where there is something wrong to cause u to not yield v. .ps .pdf
• A pedagogical proof of the Immerman-Szelepscenyi theorem. .ps .pdf
• Zasha's long notes on assignment 3 in html.
• Zasha's less-long notes on assignment 4 in html.
• Midterm Solutions .ps .pdf
• Zasha's much less long notes on assignments 6 and 7 in html.
• Zasha's long and LaTeX'd notes on assignment 8 .ps, .pdf.
• The stuff between P and NP-complete, if any. .ps
• The exponential complexity of the circularity problem for attribute grammars. .pdf
• Reduction of PCP to not-everything problem for context-free grammars. .ps

Text Book

• 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.

Simple LaTeX & Visio example of 531-relevant stuff

General theory resources

Midterm Exam

• Thursday, November 9, 2000
• Midterm study guide

Final Exam

• 10:30 - 12:20, Friday, December 8, 2000
• Final Exam study guide

	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]