Theory of Computation
CSC 420
Fall 1999
Saint Augustine's College

Instructor: Albert L. Crawford Cover, Introduction to the Theory of Computation by Michael Sipser
Office: Cheshire 118
Phone: (919) 516-4048
Office Hours: MWF 9:00 - 11:00
Web page:

Class Time and Place: TT 2:30 - 3:45 in Cheshire 102

Class Information and Assignments

  1. Sample Examination I over the first two chapters.
  2. Topic outline -- Examination II
  3. Topic outline -- Final Examination

Text: "Introduction to the Theory of Computation" by Michael Sipser.  Published by PWS Publishing Company, 1996.

Course Catalogue Description: This course explores formal models of computation such as finite state automata, pushdown automata and Turing machines will be studied, along with the corresponding elements of formal languages (including regular expressions, context free languages, and recursively innumerable languages).  These models will be used to provide a mathematical basis for the study of computablility, and to provide an introduction to formal theory behind compiler construction.  The study of Church's thesis and universal Turing machines will lead to the study of undecidable problems.  Prerequisite: CSC 404.

Course Schedule:


Course Policies

Attendance: You are expected to attend class. Any unexcused absence is considered excessive. If such absences reaches three or more the student will receive a half of a letter grade reduction for each absence beyond two. Attendance will be taken at the beginning of each class.

Note: The above syllabus is subject to change at the instructor's discretion.