CSE 355 Fall 2014
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabusf14.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.
The primary course objectives follow:
Students who complete this course can
 formulate correct finite state machines to solve algorithmic problems.
 formulate precise specifications of formal languages.
 reason about the ability of machines to recognize formal languages.
 reason about the relative computational power of machine models.
 understand the concept of a universal computing device (the ChurchTuring Thesis)
 formally prove precise statements about properties of machines and languages.
 understand (some) uses of finite state machine models in areas such as network protocols, mutual exclusion, logic programming, and circuit optimization and design.
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 (only some material on DCFLs covered)
 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  five at 4% each  20%
Always due at the start of class.
Late submissions may not be accepted; and if accepted, may be penalized for lateness.
Written documentation detailing medical treatment or a family emergency is required in order to make alternate arrangements for homework submission.
Homework 1
out 03 September, due 22 September, return 01 October.
Solutions are here.
Grades out of 50 in sorted order are:
9 11 13 15 16 17 17 17 18 18 19 19 20 20
20 20 21 21 22 23 23 24 24 25 25 25 25 27 27 27 27 28 28 28
28 28 28 29 29 29 29 29 29 29 29 29 29 30 30 30 30 31 32 32
32 33 33 33 33 33 33 33 33 33 34 34 34 34 34 35 35 36 36 36
36 36 37 37 37 37 38 38 38 38 38 39 40 40 40 40 40 41 41 41
42 42 43 43 43 44 44 44 44 44 44 44 47 48 48 48 48 49 49
(average 32).
Homework 2
out 22 September, due 06 October, return 15 October.
Solutions are here.
Grades out of 40 are:
5 13 14 19 20 21 21 21 22 23 23 23 23
24 24 24 25 25 26 26 27 27 27 27 28 28 28 28 29 29 29 29 29 29 29 30 30 30
30 30 30 31 31 31 31 31 31 32 32 32 32 32 32 33 33 33 33 33 33 33 33 33 34
34 34 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 36 36 36 36 37 37 37 37
37 37 38 38 38 38 38 38 39 39 39 39 39 39 39 39 40 40 40
Homework 3
out 06 October, due 27 October, return 05 November.
Solutions are here.
Grades out of 40 are:
2 5 7 9 9 10 10 11 11 12 13 14 14 14 14 15 15 16 16 16
17 17 17 17 17 17 17 18 18 18 19 19 19 19 19 19 20 20 20 20
21 21 22 22 22 23 23 23 24 24 24 24 24 24 24 24 25 25 25 25
25 25 25 25 25 26 26 26 27 27 27 27 27 27 28 28 28 29 29 29
29 30 31 31 31 31 31 32 33 34 34 35 36 36 36 37
Homework 4
out 20 October, due 10 November, return 24 November.
Solutions are here.
Grades out of 40 are:
5 6 6 7 7 7 10 11 11 12 13 13 13 14 14 15 15 16 17 17 17 18 18 18
19 19 20 20 21 21 21 22 22 22 23 23 23 24 24 25 26 26 26 26 26
26 26 27 27 28 28 28 28 28 29 29 30 30 31 33 33 33 34 34 34 34
35 35 35 35 35 37 37 37 37 37 38 38 38 39 39 39 40 40 40
Homework 5
out 10 November, due 26 November, return 03 December.
Solutions are here.
Grades out of 40 are:
0 3 5 5 6 6 6 7 7 9 10 10 10 11 11 12 13 13 14 14 14 15 15 17 17 18
18 19 19 20 20 20 21 21 21 21 23 24 24 24 25 25 25 27 27 28 28
29 30 31 31 32 32 32 32 33 33 34 34 35 35 35 36 36 37
Homework 6 (just for practice, not to be handed in  this is from a previous semester, and has questions from Sipser's second edition).
Solutions are here.
 Midterm Exam (Closed Book)  30%  29 October in class
A sample solution is here.
Raw scores out of 50 are:
4 7 7 8 8 9 9 9 9 10 10 11 12
12 13 13 13 14 14 14 15 15 15 16 17 17 17 17 18 18 18 18 18
18 19 19 19 19 20 20 20 20 20 20 21 21 21 21 21 21 22 22 22
23 23 24 24 24 24 24 24 24 25 26 26 26 26 26 26 27 27 27 27
28 28 28 28 29 29 29 30 30 30 30 30 30 30 30 30 31 32 32 33
34 34 35 35 35 36 37 39 39 40 40 44 44 44 45 46 48
Because the average is too low to be informative, I adjusted the grades as follows.
Add 9 to a grade in the range [0,6],
8 in the range [7,14],
7 in the range [15,22],
6 in the range [23,30],
5 in the range [31,38],
4 in the range [39,46], and
3 in the range [47,50].
Adjusted scores out of 50 are:
13 15 15 16 16 17 17 17 17 18 18 19 20
20 21 21 21 22 22 22 22 22 22 23 24 24 24 24 25 25 25 25 25
25 26 26 26 26 27 27 27 27 27 27 28 28 28 28 28 28 29 29 29
29 29 30 30 30 30 30 30 30 31 32 32 32 32 32 32 33 33 33 33
34 34 34 34 35 35 35 36 36 36 36 36 36 36 36 36 36 37 37 38
39 39 40 40 40 41 42 43 43 44 44 48 48 48 49 50 51
 Final Exam (TWO SHEETS OF NOTES)  50%  10 December, 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
the midterm, the final exam grade
replaces the midterm exam grade in calculations of the final course grade.
You must write the midterm exam in order for the grade to be eligible for replacement.
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.
More information is on the primary course web page.
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.