SYLLABUS
CMPT 320 Theory of Computation
Fall 2008
Classes: Fisher 112, TR 2:30-3:55
Instructor: Paul Shields, Fisher 111, (413) 243-0651
Email: pshields@simons-rock.edu
Office Hrs: M 3:30-4:30, T 5:00-5:30, R 1:00-2:00, or by appt.
Web Site: http://cs.simons-rock.edu/cmpt320/
Text
Michael Sipser, Introduction to the Theory of Computation, Thompson, Second Edition, 2006
Description
This course examines the theoretical underpinnings of computer science, including formal models of computation and their corresponding formal grammars, major limitation results concerning computability, and selected topics in complexity theory. Prerequisite CMPT 243 or equivalent.
Objectives
1) to gain a sense of the scope and limits of computer science as a discipline
2) to prepare for more advanced work in computability and complexity theory.
3) to begin to understand the theoretical origins of various technologies
Requirements
There will be regular assignments and 2 prepared class presentations, each of about 30 minutes in length. There will be no final exam.
Attendance
The normal college policy on attendance will be followed.
Grading
Assignments and presentations 100%