Theory of Computation
CSC 420
Fall 1999
Saint Augustine's College
Instructor: Albert L. Crawford
Office: Cheshire 118
Phone: (919) 5164048
Office Hours: MWF 9:00  11:00
Email: alcrawford@es.staug.edu
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
two chapters.

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.
Course Schedule:

Chapter 0, Introduction  1 week

Chapter 1, Regular Languages  2 weeks

Chapter 2, ContestFree Languages  2 weeks

Test Review and 1st examination  1 week

Chapter 3, The ChurchTuring Thesis  2 weeks

Chapter 4, Decidability  2 weeks

Test Review and 2nd examination  1 week

Chapter 5, Reducibility  2 weeks

Chapter 7  2 weeks

Final examination
Grading

Projects: The major emphasis on the course will be the theory.
There may be, however, one or two programming projects that will apply
the theory.

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.
Course Policies

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
of zero.

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
to apply.
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.