CSE 355 Spring 2009
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabuss09.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.)
 Sipser Chapter 0 (introduction and review)
 Sipser Chapter 1  completed
 Sipser Chapter 2  completed
 Sipser Chapter 3  completed
 Sipser Chapter 4  completed
 Sipser Chapter 5, sections 5.1,5.2  completed
The grading for the class is as follows:

Homework Assignments  six at 5% 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 (Out 27 January, Due 10 February, Returned 17 February).
Solutions are here.
Grades are out of 50. The average was 39.2. The sorted list of grades is:
50 49 49 49 48.5 47.5 47.5 47 47 46.5
45.5 45.5 45 45 44.5 44.5 44 44 43 43
42.5 42 41.5 41 40.5 40.5 40 39.5 39.5 39
38.5 38 37.5 36.5 36 36 36 35 34.5 33.5
33.5 33 30 29.5 29 29 28 26 25 25
19
Homework 2 (Out 10 February, Due 24 February, Returned 03 March).
Solutions are here.
Grades out of 50: Average 27. Grade Distribution: 49.5 43.5 43.5 42.5 42 42 41.5 41.5 38.5 35.5 35.5
35 34.5 34.5 33 32.5 31 30.5 29.5 29 28.5 28.5
28.5 28.5 28 26.5 26.5 26.5 26.5 24.5 24.5 24 23.5
22 20.5 20.5 19 18.5 18.5 18 16 15 13.5 10.5
10 10 9 9 9
Homework 3 (Out 24 February, Due 17 March, Returned 24 March).
Solutions are here.
Grade out of 50. Average 34.8. Grade Distribution: 50 50 49.5 49 48 47.5 46.5 46.5 46 45 44.5
44 44 44 43 43 41.5 41 40 39.5 39.5 39.5
39 38 37 35 35 34.5 34.5 32 31 29.5 29
29 28 28 28 27 26.5 24.5 24 23 23 22
17 15 15 12 7
Homework 4 (Out 17 March, Due 31 March, Returned 07 April.
Solutions are here.
Average is 40.4/50.
Grade distribution: 50 50 49 49 48 48 48 48 47.5 47.5 47 47
46.5 46.5 45.5 45 45 45 45 45 44 44 44 44
43 43 42 41.5 40.5 40.5 40 40 39.5 38 38 38
37.5 37 35.5 34.5 34.5 33.5 33 33 30 29.5 27.5 24.5 21 4
Homework 5 (Out 31 March, Due 14 April, Returned 28 April).
Solutions are here.
Average is 36.6.
Grade distribution: 15 18 20 21 24 24 25 26 27 28 29 30 32.5 33
34.5 35 36.5 37 37 38 38 38 38 38 38.5 39 40 41 41 42 42 42 43 44
44 44 44 44 44.5 45 46 47 47 47 49 49
Homework 6 (Out 09 April, Due 23 April, Returned 30 April).
Solutions are here.
Average is 44.5.
Grade distribution: 20 35 35 35 37 38 39 39 39 39 40
40 41 41 43 43 44 44 44 44 45 45 47 48 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 50
50 50 50 50
 Midterm Exam 1 (Closed Book)  15%  19 February in class
Solutions are here.
The average was 26.8/60.
Sorted Grades out of 60 are 57 56 53 48 46 44 44 43 42 41 38 37 34 31 30 30 30 29 27 27 27 27 26 26 26 25 25 25 25 24 24 24 22 22 21 21 20 20 20 18 17 17 16 16 16 15 15 14 13 12 11 11 10 9 8.
This midterm is worth 15% of your final grade. These grades will be scaled upwards as follows to determine what you get out of 15. If you received g/60, then compute 5 + (g/5) to get the grade out of 15.
The new average is then 10.36/15 = 69.1%. The grade distribution out of 15 becomes
6.6 6.8 7 7.2 7.2 7.4 7.6 7.8 8 8 8.2 8.2 8.4 8.4 8.6 9 9 9.2 9.2 9.4 9.4 9.8 9.8 9.8 10 10 10 10 10.2 10.2 10.4 10.4 10.4 10.4 10.8 11 11 11 11.2 11.8 12.4 12.6 13.2 13.4 13.6 13.8 13.8 14.2 14.6 15.6 16.2 16.4
 Midterm Exam 2 (Closed Book)  15%  02 April in class
Solutions are here.
The average was 33.3/60.
Grades out of 60 are: 12 13 15 16 16 16 16 18 19 20 21 22 23 23 23 24 25 26 27 27 30 31 31 32 34 35 35 36 39 39 41 41 41 42 43 43 45 45 45 46 46 48 50 50 51 51 52 53 56.
This midterm is worth 15% of your final grade. These grades will be scaled upwards as follows to determine what you get out of 15.
If you received g/60, then compute 4 + (g/5) to get the grade out of 15. The new average is then 10.67/15 = 71.1%.
The grade distribution out of 15 becomes 6.4 6.6 7 7.2 7.2 7.2 7.2 7.6 7.8 8 8.2 8.4 8.6 8.6 8.6 8.8 9 9.2 9.4 9.4 10 10.2 10.2 10.4 10.8 11 11
11.2 11.8 11.8 12.2 12.2 12.2 12.4 12.6 12.6 13 13 13 13.2 13.2 13.6 14 14 14.2 14.2 14.4 14.6 15.2
 Final Exam (Open Book and Notes)  40%  9:5011:40 Tuesday 12 May
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.