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:

• Sipser Chapter 0 (introduction and review) -- read on your own
• Sipser Chapter 1 -- done.
• Sipser Chapter 2 -- done (not all 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:

• 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 04 September, due 18 September, return 02 October. Solutions are here.
  Grades out of 50 are: 4 11 13 14 15 15 16 18 22 22 22 24 24 24 24 24 25 26 27 27 28 28 28 29 29 29 29 29 29 30 31 32 33 33 33 34 34 34 34 34 34 34 35 36 37 37 37 38 38 38 40 40 40 40 41 41 41 41 42 44 45 45 45 45 45 46 46 46 46 46 47 47 48 48 50.
  Homework 2 out 18 September, due 02 October, return 18 October. Solutions are here.
  Grades out of 40 are: 3 8 9 11 15 15 18 18 20 20 21 22 22 23 23 23 24 24 26 26 26 26 27 27 27 27 27 28 28 28 28 28 29 29 29 29 30 30 30 31 32 32 32 33 33 33 33 34 34 34 34 35 35 35 35 35 36 36 36 37 37 37 37 37 37 37 37 37 38 38 39 39 39 40 40 40 40
  Homework 3 out 09 October, due 23 October, return 04 November Solutions are here.
  Grades out of 40 are: 0 4 5 11 13 14 15 15 16 17 17 18 18 19 20 20 20 21 21 22 23 24 24 24 25 26 27 28 28 28 29 29 29 30 30 31 32 33 33 33 34 35 35 36 37 37 37 37 37 37 38 38 38 38 39 39 39 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
  Homework 4 out 23 October, due 06 November, return 18 November Solutions are here.
  Grades out of 40 are: 9 10 10 11 14 15 16 18 19 20 20 21 21 21 22 23 24 24 24 25 25 26 28 28 28 29 31 31 31 31 32 32 32 33 33 33 33 33 33 34 34 34 35 35 35 35 35 35 36 36 36 37 37 37 37 37 38 38 38 39 39 39 39 39 40 40 40 40 40 40 40
  Homework 5 out 06 November, due 25 November, return 04 December Solutions are here.
  Grades out of 40 are: 3 5 7 9 10 13 13 13 14 15 17 18 19 20 20 20 20 21 21 22 22 22 22 23 23 23 24 25 26 27 27 27 28 28 28 29 29 29 29 30 30 31 31 31 31 31 33 34 34 34 34 36 36 38 38 39 39 39 39 39 40 (but note that 17 students did not submit Homework 5!)
• Midterm Exam 1 (Closed Book) - 20% -- 07 October in class Solutions. Grades out of 50 are: 8 8 10 10 10 10 11 11 12 12 13 14 14 15 15 16 16 17 17 17 18 18 18 18 18 19 19 19 20 20 20 21 21 21 21 22 22 22 22 22 23 24 24 25 25 25 25 25 26 26 27 28 28 28 29 29 29 29 30 31 31 31 32 32 32 32 33 33 33 34 35 35 35 35 36 36 37 39 40 42 47
  Because the grades were quite low, and there was some confusion on a couple of the questions, a short supplementary test was held on 16 October, and the grades obtained added to the midterm scores. Solutions are here. The improved grades out of 50 are now: 8 9 11 11 12 12 12 12 14 14 14 16 17 17 17 17 18 18 19 19 19 19 19 20 21 21 22 22 23 23 24 24 24 25 25 25 25 25 25 26 26 27 28 28 29 29 29 29 30 30 31 31 32 33 34 34 34 36 36 37 37 38 38 39 39 40 40 41 41 41 43 43 43 44 45 45 45 47 49 52 59
• Midterm Exam 2 (ONE SHEET OF NOTES) - 20% -- 20 November in class
Solutions. Grades out of 50 are: 11 11 13 13 14 15 15 15 15 16 16 16 16 16 16 16 16 16 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 19 19 19 20 20 20 21 21 21 21 21 21 21 22 22 22 22 23 23 23 24 24 24 24 24 25 25 26 27 27 28 29 30 34 34 37 38 39 42 42 45 48
Because the average is so low, the following adjustment has been made to the grades. If the original grade was x/50, the new grade is round(x + (50-x)/10 + 5). Adjusted grades out of 50 are: 20 20 22 22 23 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 27 27 27 28 28 28 29 29 29 29 29 29 29 30 30 30 30 31 31 31 32 32 32 32 32 33 33 33 34 34 35 36 37 41 41 43 44 45 48 48 51 53
• Final Exam (TWO SHEETS OF NOTES) - 40% - Wednesday 11 December, 7:30-9: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. 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.