CSE 355 Spring 2013
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabuss13.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)  read on your own
 Sipser Chapter 1  done.
 Sipser Chapter 2  done (we only did some of the material on DCFLs)
 Sipser Chapter 3  done
 Sipser Chapter 4  done
 Sipser Chapter 5, section 5.1  done
The grading for the class is as follows:
(All dates are tentative!)

Homework Assignments  four at 6% each  24%
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 22 January, Due 05 February, Returned 12 February).
Solutions are here.
Grades out of 40 are: 13 13 17 20 20 21 22 24 25 25 25 26 26 26 26 27 27
27 27 27 28 28 28 29 29 29 29 30 30 30 31 31 31 32 32 32 32
32 32 33 33 33 33 33 34 34 34 36 36 36 39 39. Average 28.7.
Homework 2 (Out 12 February, Due 26 February, Returned 07 March).
Solutions are here.
Grades out of 40 are: 5 12 12 14 16 18 18 20 20 21 22 22 22 23 24 25 25 25 26 26 26 26 27 27 27
27 27 27 28 28 29 29 29 31 31 31 33 33 33 33 33 34 35 35 36 36 37.
Homework 3 (Out 05 March, Due 02 April, Returned 11 April).
Solutions are here.
Grades out of 40 are: 15 15 15 19 19 20 20 21 21 21 21.6 22 24 24 24 25 26 27
27 27 27 27 28 28 28 30 30 30 30 31 31 31 32 32 32 32 32 32
33 34 34 34 34 35 36 36 36 36 38 39 39.
Homework 4 (Out 09 April, Due 23 April, Returned 30 April (if possible).)
Solutions are here.
 Midterm Exam 1 (Closed Book)  12%  21 February in class
Solutions are here.
Grades out of 50 are:
12 15 16 16 18 19 19 19 19 22 22 23 25 25 25 25 25 26 26 26 27 27 27 28 28 29 29
29 29 30 30 30 31 31 31 31 31 32 32 32 32 33 33 36 36 37 37 39 40 40 42 43 43
 Midterm Exam 2 (Open Book  Open Notes)  12%  21 March in class
Solutions are here.
Grades out of 50 are:
21 25 25 27 27 27 27 30 31 31 33 34 34 34 34 34 35 36 36 36 36 37 38 38
38 38 38 38 39 39 39 40 40 40 40 40 40 40 41 41 41 42 42 43 44 44 44 46 47
47 48 49
 Midterm Exam 3 (Open Book  Open Notes)  12%  16 April in class
Solutions are here.
Grades out of 50 are:
21 23 24 26 26 26 27 28 28 29 29 29 29 29 29 30 30 30 31
32 32 32 32 32 32 32 33 34 35 35 35 35 35 36 36 36 37 38 38
38 39 39 39 40 40 42 42 43 44 49 49
 Final Exam (One 8.5"x11" sheet of paper)  40%  Thursday 02 May, 7:309:20 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 any of
the midterms, 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.