CSE 355 Fall 2006
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabus.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 has been made more explicit as the semester
progressed.)
See the course myasu site for the PDFs of the lecture notes used in class.
 S Chapter 1 (mostly review)  done
 S Chapter 2  done
 S Chapter 3  done
 S Chapter 5  done
 S Chapter 6  done, but MyhillNerode only discussed briefly
 S Chapter 7  done
 S Chapter 4  quick overview only done on October 24
 S Chapter 8  done, proofs only sketched
 S Chapter 11  done, high level overview without proofs
 S Chapter 12  done, outline only
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 (Handed Out 29 August, Due September 12).
Solutions are here.
Average grade was 77.2. Here is the grade distribution:
35 37 38 50 55 56 56 57 58 64 68 69 69 69
71 71 72 72 73 73 73 74 74 77 82 83 84 84
86 86 86 87 88 88 88 88 89 91 92 94 94 95
95 98 99 99 100 100 100
Homework 2 (Handed Out 1 September, Due September 26).
Solutions are here.
Average grade was 80.3. Here is the grade distribution:
27 42 61 61 62 62 64 64 64 68 70 71 73 75
76 76 77 77 78 78 79 79 80 82 84 85 85 86
86 87 88 88 89 90 90 90 90 90 91 91 91 92
93 93 93 94 96 96 96 97 97
Homework 3 (Handed Out 25 September, Due October 10).
Solutions are here.
Average grade was 72.6. Here is the grade distribution:
26 27 36 37 44 48 48 52 53 54 59 63 63 63
63 64 65 68 71 71 71 71 71 72 72 73 73 74
77 77 80 82 84 85 85 86 86 87 87 88 89 90
92 93 94 95 96 96 100 100
Homework 4 (Handed Out 10 October, Due October 26).
Solutions are here.
Average grade was 69.6. Here is the grade distribution:
16 23 25 33 40 42 44 45 45 48 50 52 54 54
55 56 57 58 60 62 67 69 71 74 76 77 77 78
78 78 82 82 84 84 86 87 87 88 89 90 91 92
92 93 93 94 95 95 95
Homework 5 (Handed Out 26 October, Due 16 November).
Solutions are here.
Average grade was 64.0. Here is the grade distribution:
20 22 25 31 32 34 37 43 47 48 48 49 49
50 51 52 52 52 55 58 59 59 60 61 62 66
66 67 67 68 69 70 72 72 74 74 75 78 78
80 84 87 90 93 94 95 96 97 97 97
Homework 6 (Handed Out 16 November, Due 30 November, but see the news page).
Solutions are here.
 Midterm Exam 1 (Closed Book)  15%  3 October in class
Covers Chapters 1, 2, 3, and 5.
Average grade was 33.8/60.
Grades out of 60 are:
14 15 16 16 18 20 20 22 22 23 24 24 24 24 25 26 29 29 29 30 31 31 32 32 32 33
34 34 36 36 36 36 37 37 38 38 39 39 39 45 45 46 47 48 49 49 49 49 50 50 54 57
 Midterm Exam 2 (Closed Book)  15%  2 November in class
Covers Chapters 6 and 7 (and uses basic overview of Chapter 4), but note that questions concerning earlier material may be parts of questions on later material!
Average was 27/60. Grades out of 60 are:
0 6 7 12 13 13 13 14 15 15 16 16 19
19 20 20 21 21 21 22 22 22 22 23 24 24 24
24 25 26 26 26 27 29 30 31 32 35 36 39
40 42 42 45 46 46 47 48 49 52 52 57
 Bonus Midterm Exam (Closed Book)  (see below)%  14 November in class
Covers Chapters 1,2,3,5,6,7.
This is an optional opportunity to earn some of the grades that you have lost. Here is what will happen. Suppose that you have A/60 on midterm 1, B/60 on midterm 2, and earn M/60 on the bonus midterm. Your new grade on midterm 1 will become A +
M*(.7.01*A), and your grade on midterm 2 will become B+M*(.7.01*B). In both cases, the new midterm grades will be rounded up to the next integer.
Earlier announcements about allowing a better final exam grade to replace one or both midterm grades still stand!
A sample solution for the bonus midterm is here.
The average on the bonus midterm was 30.9 out of 60. Here is the grade distribution: 5 15 16 19 20 21 21 22 22 23 23 23 23
24 24 24 25 26 27 27 27 28 28 30 30 31
32 32 32 33 35 35 37 37 38 38 38 38 38
38 40 40 40 41 41 41 46 46 51 55
Using the formula given this changes the average on midterm 1 to 44.4 out of 60. Here is the distribution: 16 18 27 27 31 31 32 32 33 36 37 38 39
39 39 40 41 41 42 42 42 42 42 42 45 45
45 45 45 45 46 46 47 47 48 49 50 51 51
51 55 55 55 57 57 58 58 60 60 60 61 65
Using the formula given this changes the average on midterm 2 to
39.5 out of 60. Here is the distribution: 10 13 21 22 25 26 27 28 28 29 29 29 29
31 32 33 34 34 34 34 34 35 36 36 39 39
39 39 39 40 41 41 42 42 44 45 46 47 47
52 52 53 55 55 55 56 57 57 58 60 62 65
Hopefully these are a better reflection of the grades in the class than before.
 Final Exam (Closed Book)  40%  10:0011:50 on 8 December
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.