CSE 555 Spring 2020 
Theory of Computation

IMPORTANT CHANGES!
Because of concern about the coronavirus pandemic, ASU is suspending in-class meetings wherever possible from 16 MARCH 2020 until the end of semester. Therefore, CSE555 will NOT meet in the usual classroom.
I will continue to post updated information here as it becomes available. This information may change on short notice!

  1. Lectures: We are transitioning the in-class meetings to Zoom. We will NOT be meeting in CDS 234 for these dates.
    Zoom lectures will be at the usual time, 10:30-11:45 a.m., each Tuesday and Thursday. Recordings of the lectures are being placed under the Pages tab on the Canvas site.
    A Canvas site has also been set up for the course, so that you can access Zoom via Canvas.
    There are detailed instructions on how to use Zoom on this site.
  2. Office Hours:
  3. The Midterm Test and Homework will continue to be posted on the class web page. Fortunately the midterm is a take-home test, so no changes arise there.
    I will send grades and comments on homework and tests by email to each individual student.
Thanks for understanding the difficulties that we will all face in continuing the course, and watch for updates. If you have to deal with any interruption in your course participation due to coronavirus, or any health matter, please advise the instructor early so that accommodations can be made.

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).

Course
Information		 CSE 555:  Theory of Computation  
http://www.public.asu.edu/~ccolbou/src/cse555s20.html
Class Meeting Time T Th 10:30-11:45 
CDS 234
Instructor 
 

Office Hours

 Charlie Colbourn
Office:  Brickyard 444 
Charles.Colbourn@asu.edu
Tuesday 1:30-2:30 p.m., Thursday 7:30-8:30 a.m.
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. I strongly advise you not to attempt this.
  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.