CSE 355 Spring 2016
Introduction to the Theory of Computation Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/355syllabuss16.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:


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.
In fall 2014, 21 students were reported for academic integrity violations in my section of CSE 355.
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.