CSE 431,  Sp '10:  Introduction to Theory of Computation

CSE Home

About Us

Search

Contact Info

Administrative  Schedule & Reading  Midterm Review  Final Review Course Email  Class List Archive Assignments  HW #1  HW #2  HW #3  HW #4  HW #5  HW #6  HW #7  HW #8 Lecture Notes  Lecture 1, 3/29  Lecture 2, 3/31  Lecture 3, 4/2  Lecture 4, 4/5  Lecture 5, 4/7  Lecture 6, 4/9  Lecture 7, 4/12  Lecture 8, 4/14  Lecture 9, 4/16  Lecture 10, 4/19  Lecture 11, 4/21  Lecture 12, 4/23  Lecture 13, 4/26  Lectures 1-13 (1-up, 4-up)  Lecture 14, 4/28  Lecture 15, 4/30  Lecture 16, 5/3  Lecture 19, 5/10  Lecture 20, 5/12  Lecture 21, 5/14  Lecture 22, 5/17  Lecture 23, 5/19  Lecture 24, 5/21  Lecture 25, 5/24  Lecture 26, 5/26  Lecture 27, 5/28  Lecture 28, 5/31  Lecture 29, 6/2  Lectures 14-30 (1-up, 4-up) Resources  A real TM

Lecture:  MGH 251 (schematic) MWF 1:30- 2:20PM    Office Hours Location Phone Instructor:  Larry Ruzzo, ruzzocs  M 2:30- 3:20PM  CSE 554  543-6298 TAs:  Aeron Bryce, paradoxacs  W 12:30- 1:20PM  CSE 218      Th 5:00- 6:00PM  CSE 218  Course Email: cse431a_sp10@u.washington.edu. Use this list to ask and/or answer questions about homework, lectures, etc. The instructor is subscribed to this list. All messages are automatically archived.  Questions not of general interest may be directed to the instructor and/or TA collectively (via the "course staff" link at left) or separately (via email addresses above). You can (probably should) change your subscription options. Catalog Description: Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 322. Credits: 3 Learning Objectives: The course explores formal approaches to addressing some of the most fundamental questions in computer science. What is "computation"? How do you define it? What problems are/are not computable? What is/is not "efficiently" computable? Grading: Homework, Midterm, Final. Overall weights 55%, 15%, 30%, roughly. Late Policy: Assignments are due at the start of class on the due date. 50% off if turned in by the start of the next class; no credit thereafter. Barring major emergencies, these deadlines are strict. (You may turn in work electronically, including scanned versions of handwritten papers, via the Catalyst drop box link at left.) Extra Credit: Assignments may include "extra credit" sections. These will enrich your understanding of the material, but at a low points per hour ratio. Do them for the glory, not the points, and don't start extra credit until the basics are complete. Collaboration: Homeworks are all individual, not group, exercises. Discussing them with others is fine, even encouraged, but you must produce your own homework solutions. Follow the "Gilligan's Island Rule": if you discuss the assignment with someone else, don't keep any notes (paper or electronic) from the discussion, then go watch 30+ minutes of TV (Gilligan's Island reruns especially recommended) before you continue work on the homework by yourself. You may not look at other people's written solutions to these problems, not in your friends' notes, not in the dorm files, not on the internet, ever. If in any doubt about whether your activities cross allowable boundaries, tell us before, not after, you turn in your assignment. See also the UW CSE Academic Misconduct Policy, and the links there. Textbook: Michael Sipser, Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005. Errata. (Available from U Book Store, Amazon, etc.) Portions of the CSE 431 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 431 Web: © 1993-2010, Department of Computer Science and Engineering, University of Washington.

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