CSE 555 is an advanced (second) course in the theory of computation. It assumes knowledge of a standard first course covering finite automata, regular expressions, and regular languages; pushdown automata, contextfree grammars, and contextfree languages; Turing machines, Turingrecognizable (recursively enumerable) languages, and Turingdecidable (recursive) languages; the ChurchTuring thesis; and undecidability. With this background, CSE 555 covers reducibility for computable problems; the recursion theorem; time complexity (including P, NP, NPcomplete, PSPACE, PSPACEcomplete, EXPTIME); and space complexity.
Course
Information: 
CSE 555: Theory of Computation
http://www.public.asu.edu/~ccolbou/src/cse555s13.html 

Class Meeting Time: 
BY M109 

Instructor:
Office Hours: 
Office: Brickyard 444 Charles.Colbourn@asu.edu T 1:302:30, Th 10:3011:30 

TA:
Office Hours: 
Office: Brickyard 511 (for office hour) mjbartho@asu.edu W 2:003:00, F 2:003:00 

Prerequisites: 
Introduction to the Theory of Computation. 

Special Needs:  If you are entitled to extra accommodation for any reason (such as a disability), we make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor at the beginning of the course.  
Academic Honesty:  Work in this course, unless explicitly stated in writing to the contrary, is to be an effort by the individual student. It is not acceptable to use work other than your own without full attribution and acknowledgment. While you are welcome to discuss problems with others, it is not acceptable to discuss solutions with them. If in doubt about anything related to academic integrity, see the instructor.  
TextBooks:  
Required Text:  Michael Sipser, Introduction to the Theory of Computation, Third Edition, Thomson, 2012. 