CSE 555 Spring 2014
Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/555syllabuss14.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
progresses.)
 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:

Homework Assignments  five at 8% each  40%
Always due at the start of class.
Written documentation detailing medical treatment or a family emergency is required in order to make alternate arrangements for homework submission.
Homework 1 (Out 23 January, Due 06 February).
Solutions are here.
Grades out of 50 are:
18 22 26 26 26 29 30 32 33 33 36 41 42 42 42 42 45 46 47 47 48 48 48 49
Homework 2 (Out 06 February, Due 20 February).
Solutions are here.
Grades out of 50 are:
12 17 18 19 21 21 26 28 34 36 37 38 40 40 42 44 44 44 45 46 49 50
Homework 3 (Out 20 February, Due 06 March electronically, copied to me and the TA).
Solutions are here.
Grades out of 50 are:
12 18 21 23 24 24 27 30 31 33 33 35 37 39 39 40 42 43 44 46 48 49
Homework 4 (Out 25 March, Due 08 April).
Solutions are here.
Grades out of 50 are:
14 18 20 27 32 33 34 34 35 36 37 40 41 42 46 47 50
Homework 5 (Out 08 April, Due 24 April).
Solutions are here.
 Midterm Exam (TakeHome)  20%  Out 22 March at noon, Due 26 March at 11:59 p.m. electronically to colbourn@asu.edu
Here is the midterm in PDF, and the tex source is here.
Solutions are here.
Grades out of 50 are:
0 15 19 20 23 23 23 25 28 29 30 31 33 38 39 43 44 45 46 48 48 49
 Final Exam (TakeHome)  40%  Out 03 May at noon, Due 08 May at 2:00 p.m. electronically to colbourn@asu.edu
Here is the final in PDF, and the tex source is here.
The goal is to learn the material, and grades are meant to be reflective of how well you learned it. For this reason, the final exam is more heavily weighted, and is cumulative. If your percentage grade on the final exam exceeds that on
the midterm, the final exam grade
replaces the midterm exam grade in calculations of the final course grade.
It does not replace homework grades.
It is imperative that you make a legitimate attempt to answer all of the
homework questions. Any scaling of grades at the end of the course takes into
account the effort invested.
General Course Information:
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.