CSE 355 Fall 2010
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabusf10.html
CSE 355 is introductory course to
the theory of computation.
The focus is on the capabilities of "simple" machines, and the problems that they can compute.
Topics to be Covered:
(The specific syllabus will be made more explicit as the semester
progresses.)
 S Chapter 1 (mostly review)  done
 S Chapter 2  done
 S Chapter 5, Sections 16  done
 S Chapter 6, Sections 1, 2, 4, 5,6  done
 S Chapter 5, Section 7  done
 S Chapter 6, Section 7  quick overview  done
 S Chapter 6, Section 3  done
 S Chapter 3  done
 S Chapter 4, sections 4.14.5.  done
 S Chapter 4, 4.7 and 4.8 covered very briefly.  done
 S Chapter 7  done.
 S Chapter 8
 S Chapter 11  high level overview without proofs
 S Chapter 12  outline only
The grading for the class is as follows:

Homework Assignments  five at 6% each  30%
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 (Handed Out 26 August, Due 14 September (was 09 September)).
Sample Solutions are here; note that there are many correct ways to solve each problem, these are just examples.
The grades out of 50 were: 50 50 50 50 50 49.5 49 49 48.5 48 48 47.5 47.5 46.5 46.5
44.5 44 43 42 42 42 41.5 41 40.5 38.5 38.5 38 37 35.5 35
33.5 33 33 29.5 29 26 24.5 21 15.5 12
Homework 2 (Handed Out 09 September, Due 23 September).
Sample Solutions are here.
The grades out of 50 were: 13 26 28 28.5 32.5 34.5 34.5
35 36 36 36.5 38 41.5 41.5 41.5 42 42
42.5 43.5 43.5 43.5 43.5 44 44 46 46.5 46.5
48 48 49 49.5 49.5 49.5 49.5 50 50 50
50 50 50
Homework 3 (Handed Out 23 September, Due 14 October).
Sample Solutions are here.
Grades out of 50 are: 4 11 14 19 21 21 25 29 30 30 31 31 33 36
38 38 40 40 40 42 42 43 43 43 45 45 46 46 47
47 48 48 48 48 48 50 50
Homework 4 (Handed Out 15 October, Due 04 November).
Sample Solutions are here.
Grades out of 50 are: 27 35 35 35 36 39 40 41 43 43 43 44
44 44 44 45 45 45 46 46 46 46 47 48 48 48 48
49 50 50 50 50 50 50.
Homework 5 (Handed Out 04 November, Due 23 November).
Sample Solutions are here.
Homework 6 (SAMPLE ONLY  NOT TO BE HANDED IN).
Sample Solutions are here.
 Midterm Exam 1 (Closed Book)  15%  30 September in class
Covers Chapters 1, 2, 5, and 6.
Sample solutions are here.
 Midterm Exam 2 (Closed Book)  15%  28 October in class
Covers Chapters 3 and 4 and the first part of 7 primarily, but assumes knowledge of earlier material as well.
Sample solutions are here.
 Final Exam (Closed Book)  40%  14 December, 9:5011:40 a.m.
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 either
or both midterms, the final exam grade
replaces the midterm exam grade in calculations of the final course grade.
It does not replace homework grades.
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.