Instructor: Albert L. Crawford 
Office: Cheshire 118
Phone: (919) 516-4048
Office Hours: MWF 9:00 - 11:00
E-mail: alcrawford@es.st-aug.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

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:

• 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
• 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.

• 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.