CSE 431: Introduction to Theory of Computation, Spring 2017

CSE Home

CSE 431 Home

About Us

Search

Contact Info

Email   Archive  Homework Assignments   Homework 1   Homework 2   Homework 3   Homework 4   Homework 5   Homework 6   Homework 7   Homework 8   Homework 8 solutions Reading Assignments   More NP-complete problems   Read Sections 7.4 and 7.5   Read Section 9.3   Cocke-Kasami-Younger Algorithm   Read Chapter 7   Read Chapter 5   Chomsky Normal Form   Read Chapter 4   Read Chapter 3   Turing and Post Handout   Slides on NFAs   Read Chapter 1   Review Chapter 0 Administrative   Homework Policy Interesting Links   Davis' The Universal Computer   Hilbert's 23 Problems   David Hilbert Bio   Kurt Godel Bio   Alonzo Church Bio   Alan Turing Bio

Location Mondays, Wednesdays, and Fridays 10:30-11:20    Mary Gates Hall 228 Instructor Paul Beame Office: CSE 668 Phone 206-543-5114 Office Hours: MWF 11:20-11:50, and W 2:00-2:50 Teaching Assistant Vincent Liew Office Hours: Wednesdays 3:00-4:00 CSE 220, Thursdays 2:00-3:00 CSE 021 Textbook Michael Sipser, Introduction to the Theory of Computation. Any of the first, international, second or third editions will work. Earlier editions are less than one quarter the cost of the third edition online. Although the numbering of almost everything in the first and international editions are different from the others, the content is mostly unchanged except for some corrections and new and solved problems in each subsequent edition. The third edition has an extra section 2.4 on deterministic context-free languages that we won't cover anyway. See errata links from Sipser's book page for lists of errors and corrections. Mailing List Course annoucements will be made on the class mailing list, cse431a_sp17. Grading Homework 45-55%, midterm 15-20%, final 30-35%, give or take. Extra Credit. See the homework policy Midterm Exam Friday May 5 in class. A sample midterm gives some idea of the content that it will cover. There will be a review session on May 4 at 5:00 in room CSE 305. Final Exam The final exam will be at the time listed in the official exam schedule which is 8:30-10:20 pm, Monday June 5. Here is an old final exam from a prior quarter. There will be a review session on Sunday June 4 at 1:00 p.m. in CSE 403. Catalog Description Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions. Prerequisite: CSE 312. 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-2017, Allen School of Computer Science and Engineering, University of Washington.