CSE 355 Spring 2012
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabuss12.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.)
 Linz Chapter 1 (introduction and review)  read on your own
 Linz Chapter 2  done (skipped 2.4)
 Linz Chapter 3  done
 Linz Chapter 4  done
 Linz Chapter 5  done (skipped 5.3)
 Linz Chapter 6  done (skipped 6.3)
 Linz Chapter 7  done (skipped 7.4)
 Linz Chapter 8  done (omitted "some decidable properties" in 8.2)
 Linz Chapter 9  done
 Linz Chapter 10  done (skipped 10.5)
 Linz Chapter 11 (done, 11.1 only)
 Linz Chapter 12  12.1, 12.2 only
The grading for the class is as follows:

Homework Assignments  five at 2% each  10%
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.
Each homework will have five questions, of which only two will be graded (and you will be told which two in advance.) Solutions will be posted for all five questions.
Homework 1 (Out 17 January, Due 31 January, Returned 09 February).
Solutions are posted.
Grades out of 20 are:
0 2 2 3 3 3 3 4 4 5 5 5 5 5 6
6 7 7 7 8 8 8 8 9 9 9 9 9 9 9 10 10 10 10 10
10 10 10 10 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12
12 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 15
15 15 15 15 16 16 17 18 18 18 18 18 19 19 19 19 20 20 20 20
Homework 2 (Out 31 January, Due 14 February, Returned 23 February).
Solutions are posted.
Grades out of 20 are: 0 2 3 5 6 6 7 7 8 8 9 9 9 10 10
10 11 11 11 11 11 12 12 12 12 12 12 12 13 13 13 13 13 13 14 14 14 14 15 15
15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17
17 17 17 17 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 20 20 20 20
Homework 3 (Out 21 February, Due 06 March, Returned 27 March).
Solutions are posted.
Grades out of 20 are:
2 4 4 4 6 7 7 8 9 9 9 10 10 10 10 10 11 11 11 11 11 11 11 12 12 12 12
12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 15
15 15 16 16 16 16 17 17 17 17 17 18 18 18 18 18 18 18 18 19 19 19 19 19 19 20 20
Homework 4 (Out 06 March, Due 29 March, Returned 10 April.)
Solutions are posted.
Grades out of 20 are:
2 3 4 5 5 6 6 8 8 8 8 9 9 9 10 10 10 10 11 11 11
11 11 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13
13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15
15 15 16 16 16 16 16 16 17 17 17 17 17 18 19 19 20 20 20
Homework 5 (Out 03 April, Due 17 April, Returned 24 April).
Solutions are posted.
Grades out of 20 are:
0 1 2 2 3 3 4 4 4 4 5 5 6 7 7 8 9 9 9 9 10 10 11 11 11
12 12 12 12 12 13 13 13 14 14 14 14 15 15 15 15 15 15 15 15 16 16 16 16 16
16 17 17 17 17 17 17 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 20 20
 Midterm Exam 1 (Closed Book)  20%  16 February in class
Solutions are posted.
Grades out of 50 in sorted order:
4 5 5 6 6 6 9 11 11 12 12 12 13 14 15 15 15 15 15 16
17 19 19 20 20 21 21 21 21 22 22 23 24 25 25 25 25 25 25 26
26 26 26 26 26 26 26 26 27 27 27 27 27 28 28 28 28 29 29 29
29 29 29 29 29 29 30 30 30 30 31 32 32 33 33 33 34 34 34 34
34 35 35 36 36 36 36 37 39 43 43 43 47 47 47 49.
Average is 25.7.
 Midterm Exam 2 (Open Book, Open Notes)  20%  27 March in class
Solutions are posted.
Grades out of 50 in sorted order:
1 3 7 8 9 9 9 9 10 11 11 11 11 11 12 12 13 13 13 14 14 14 15
15 15 16 16 16 16 16 16 16 17 17 17 18 18 18 18 18 18 18 19 19 19 19
19 20 20 20 20 21 21 21 21 21 22 22 22 24 24 24 25 25 25 26 26 26 26
27 27 27 27 27 27 28 28 29 30 31 31 31 32 33 34 35 36 37 46 50.
See the news page for discussion of how to interpret these.
 Final Exam (Open Books and Notes)  50%  7:309:20 Thursday 26 April
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.
In order to replace a midterm grade, you must have written the midterm.
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.