CSE 555 Spring 2016
Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/555syllabuss16.html
CSE 555 is an advanced course in the theory of computation.
Topics to be Covered:
(The specific syllabus will be made more explicit as the semester
- Sipser Chapters 0,1,2,3,4 -- review on your own
- Sipser Chapter 5 -- done
- Sipser Chapter 6 -- done
- Sipser Chapter 7 -- done
- Sipser Chapter 8 -- done
- Sipser Chapter 9.1, 9.2 -- done
The grading for the class is as follows:
General Course Information:
If you do not have a clear understanding of the material in CSE 355 (the first four chapters of Sipser's text, roughly) then
you are strongly recommended not to attempt this course.
Students may discuss homework
assignments with their classmates; however all work turned in is expected
to be that of the individual. If you have any questions regarding appropriate
collaboration please see the instructor.
We will follow the text closely, but the emphasis on the tests will be the same as that in the lectures. Hence, although class attendance is not required, it is highly recommended.
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.