Theory of Computation
Saint Augustine's College
Instructor: Albert L. Crawford
Office: Cheshire 118
Phone: (919) 516-4048
Office Hours: MWF 9:00 - 11:00
Web page: www.CrawfordEnterprise.com/StAug/index.html
Class Time and Place: TT 2:30 - 3:45 in Cheshire 102
Class Information and Assignments
Sample Examination I over the first
Topic outline -- Examination II
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.
Chapter 0, Introduction -- 1 week
Chapter 1, Regular Languages -- 2 weeks
Chapter 2, Contest-Free Languages -- 2 weeks
Test Review and 1st examination -- 1 week
Chapter 3, The Church-Turing Thesis -- 2 weeks
Chapter 4, Decidability -- 2 weeks
Test Review and 2nd examination -- 1 week
Chapter 5, Reducibility -- 2 weeks
Chapter 7 -- 2 weeks
Projects: The major emphasis on the course will be the theory.
There may be, however, one or two programming projects that will apply
Quizzes: There will be 0 to 10 in class quizzes given throughout
the semester. These will be weighted from 0 to 20 points each. These may
be either announced or unannounced. No makeups will be given for quizzes.
Exams: There will be two regular hour exams during the semester.
These exams will be weighted at 100 points each.
Final: The final examination will be weighted at 150 points and
will cover the material from the entire course with the material from the
last third of the course being given the most weight.
Grades: All grades will be based on a 90, 80, 70, 60 percentage
of all points for grades of A, B, C, and D. Any "curves" that will be placed
on the grades will be made on the individual tests and not at the end of
the semester. Such curves are not likely.
Makeup of work: Should an absence be known ahead of time the student
should so inform the instructor and get his approval. Work that is due
during such an absence should be turned in prior to the absence or sent
to class with a classmate. If an exam is scheduled during such an absence
the student may be required to take the exam early.
Makeups for missed regular exams will not be given unless the reason
for the absence is determined by the instructor to be valid and necessary.
It is the students responsibility to make the reason for the absence known
to the instructor as soon as is reasonably possible.
Course Requirements: It is expected that all assignments be complete
and turned in on time. Late or incomplete assignments will be given a score
of -100% until they are completed. At that time they will be given a score
Cheating: I do not expect this paragraph to apply to anyone. However,
in the very unlikely event that a student is caught cheating please see
the student handbook for the penalties that the instructor has the authority
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