CSE 555 Spring 2017
Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/555syllabuss17.html
CSE 555 is an advanced course in the theory of computation.
Topics to be Covered:
(The specific syllabus will be made more explicit as the semester
- Sipser Chapters 0,1,2,3,4 -- review on your own
- Sipser Chapter 5
- Sipser Chapter 6
- Sipser Chapter 7
- Sipser Chapter 8
- Sipser Chapter 9.1, 9.2
The grading for the class is as follows:
Homework Assignments - five at 6% 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 (Out 19 January Due 02 February).
Homework 2 (Out 02 February Due 16 February).
Homework 3 (Out 16 February Due 02 March).
Homework 4 (Out 23 March Due 06 April).
Homework 5 (Out 06 April Due 20 April).
- Midterm Exam - 25% - 02 March in class
Sketches of solutions are here.
- Final Exam - 45% - Take Home. Out 27 April at noon. Due electronically 02 May at 09:20 a.m. by email to the instructor.
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 to have it considered for replacement by the final.
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.
The final exam is here and the tex source file as well.
This is an individual effort, and material other than text or course notes is not to be used.
Introduction to the Theory of Computation (CSE355 at ASU or equivalent)
||If you are entitled to extra accommodation for any reason (such
as a disability), we make every reasonable attempt to accommodate you.
However, it is your responsibility to discuss this with the instructor
at the beginning of the course.
Work in this course, unless explicitly stated in writing to the contrary, is to be an effort by the individual student. It is not acceptable to use work other than your own without full attribution and acknowledgment. While you are welcome to discuss
problems with others, it is not acceptable to discuss solutions with them.
Ask the instructor if you are unsure about how much collaboration is permitted.
Depending on the severity of the infraction, penalties may include a grade of zero on the offending item, a grade of zero on the offending item and a reduction of the final grade by one full letter grade, a failing grade in the course with an indication of academic dishonesty. Such penalties might result in a requirement to withdraw from the university.
If in doubt about anything related to academic integrity, see the instructor.
|| Michael Sipser, Introduction to the Theory of Computation, Third Edition, Thomson, 2012.
If you do not have a clear understanding of the material in CSE 355 (the first four chapters of Sipser's text, except for DCFLs) then
you are strongly recommended not to attempt this course.
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.