CSE 555 Spring 2017
Theory of Computation
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.
Students are expected to have
formal (mathematical) background in
the introduction to the theory of computation (CSE 355 at ASU).
Course
Information 
CSE 555: Theory of Computation
http://www.public.asu.edu/~ccolbou/src/cse555s17.html 
Class Meeting Time 
T Th 7:308:45 a.m.
BYAC 150

Instructor
Office Hours 
Charlie Colbourn
Office: Brickyard 444
Charles.Colbourn@asu.edu
Tuesdays 10:3011:30, Thursdays 1:002:00

Prerequisites 
Introduction to the Theory of Computation (CSE355 at ASU or equivalent)

Frequently Asked Questions:
 I have not taken 355 or equivalent but I am sure I can catch up.
Is that ok?
Based on past experience, students encounter great difficulty doing this, often resulting in a huge investment of time,
and sometimes also a poor or failing grade. I strongly advise you not to do it.
 I have taken 355 or equivalent but we did not do any proofs. Is that a problem?
In 555, knowing the statements of theorems is definitely not enough. It is crucial to know why they are true.
 My friends tell me that this is a hard class. Is it? It depends. It requires a lot of thinking, and a consistent effort to keep up. But if you have the background for the course, and make a reasonable investment in it, personally I do not think it is hard.
 I am planning to use 555 to meet a deficiency requirement for 355. Is that allowed? No, never.
 Can we use material that we find on the internet or in books other than the text? The goal is to learn the material, not just to get a grade on a homework assignment. If you find things online or wherever, you must cite them properly; it is dishonest not to do so.
Please note that if you use such materials without understanding them, you are quite likely
going to repeat any errors in the online source, and use results and terms that are not part of our course.
Moreover, it is poor preparation for the midterm and final, which are weighted much more heavily.
 I will be absent for a class. What do I do? If it is for medical reasons or family emergency, email me to let me know, and get documentation to provide to me.
If for any other reason, do not miss the midterm or final. If you miss a different class, make sure that any homework that is due is sent by email by the due time.
 I am running late and won't get to class in time to turn in the assignment. What should I do?
Send a scan of your homework to me by email before the time that it is due. Then bring a paper copy to me (or my mailbox) as soon as possible thereafter.
 My grade is low, so is there extra work I can do to raise my grade? No.
 I didn't finish my homework in time, so can I please, just once, turn it in late? Turn in whatever you have by the due time. Anything that is late may receive no credit.