CSE 355 Spring 2017
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabuss17.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
  1. formulate correct finite state machines to solve algorithmic problems.
  2. formulate precise specifications of formal languages.
  3. reason about the ability of machines to recognize formal languages.
  4. reason about the relative computational power of machine models.
  5. understand the concept of a universal computing device (the Church-Turing Thesis)
  6. formally prove precise statements about properties of machines and languages.
  7. 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.)

The grading for the class is as follows:

Contacts Direct questions as follows:
  • concerning help for homework assignments and quizzes to either recitation leader, copying the instructor.
  • concerning comments on homework assignments to your recitation leader.
  • concerning recitation sections to your recitation leader.

    If you want to attend a recitation section other than the one in which you are registered, this will be allowed if, and only if, space permits. If the room becomes overfull, all students who are not registered in the recitation section must leave.

  • concerning extra help sessions to the undergraduate TA, copying the recitation leaders.
  • concerning the midterm test, the final exam, and general course organization to the instructor.
Prerequisites Students are expected to have background in Advanced data structures and algorithms (CSE 310), Mathematical foundations (MAT 243).
Special Needs 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. 
Academic Honesty 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.

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.

Attendance 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.
Protocol for Lecture Lectures start promptly at 9:00. Announcements will be made, then questions answered, and then the lecture material presented. Therefore late arrival will mean that you may miss important announcements about homeworks, recitations, readings, and the like, and you will certainly disrupt the class and make it more difficult for your fellow students to listen and learn. Please think about your fellow students, and ensure that they have the opportunity to profit from the lecture, whether or not you wish to. If you must arrive late, enter quietly and do not disrupt the lecture. If you must leave early, leave quietly and do not disrupt the lecture.
Required Text Michael Sipser, Introduction to the Theory of Computation, Third Edition, Cengage Learning, 2012, (ISBN-13: 978-1133187790).