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, context-free grammars, and context-free languages; Turing machines, Turing-recognizable (recursively enumerable) languages, and Turing-decidable (recursive) languages; the Church-Turing thesis; and undecidability. With this background, CSE 555 covers reducibility for computable problems; the recursion theorem; time complexity (including P, NP, NP-complete, PSPACE, PSPACE-complete, EXPTIME); and space complexity.

Students are expected to have formal (mathematical) background in the introduction to the theory of computation (CSE 355 at ASU).

CSE 555:  Theory of Computation  
Class Meeting Time T Th 7:30-8:45 a.m. 
BYAC 150

Office Hours

Charlie Colbourn
Office:  Brickyard 444 
Tuesdays 10:30-11:30, Thursdays 1:00-2:00
Prerequisites Introduction to the Theory of Computation (CSE355 at ASU or equivalent)

Frequently Asked Questions:

  1. 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.
  2. 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.
  3. 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.
  4. I am planning to use 555 to meet a deficiency requirement for 355. Is that allowed? No, never.
  5. 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.
  6. 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.
  7. 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.
  8. My grade is low, so is there extra work I can do to raise my grade? No.
  9. 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.