CPSC 390A Theory of Computation, Fall 2005

Anil M. Shende
365B Trexler, x2341
email address: shende@roanoke.edu
Office Hours: MW: 9:30am--10:30am; Th: 9:30am -- 11:30am; and by appointment
Course Website: http://cs.roanoke.edu/CPSC390A/



An Introduction to the Theory of Computer Science, Languages and Machines, 3rd edition by Thomas A. Sudkamp


This course deals with the study of formal models of computation. Topics include formal languages, automata theory, Turing machines, undecidability, and an introduction to computational complexity and recursive function theory.

Prerequisites: CPSC 170

Academic Integrity

Students are expected to adhere to the Academic Integrity policies of Roanoke College. All work submitted for a grade is to be strictly the work of the student unless otherwise specified by the instructor. The policies as outlined in the Academic Integrity handbook will be enforced in the course.

Graded programs are subject to the Roanoke College Academic Integrity policies. Copying a program or a portion of a program (even a single line) or reading another person's program to obtain ideas for solving a problem is plagiarism. Other examples of integrity violation include writing code for someone else, using code written by someone else, telling someone else how to solve a problem or having someone tell you how to solve a problem (and using their method). These cases apply to any work that is handed in for a grade under the instructor's assumption that the work is your own. Unless specified otherwise by the instructor, discussion among students should be limited to general discussion of concepts and language details, not specific aspects of a solution to the assigned problem.

Class Attendance

Regular attendance is highly recommended. Regardless of attendance, students are responsible for all material covered or assigned in class.


There will be two take-home tests (due on Oct. 5, and Nov. 9) and one take-home final exam (due on Dec. 9). There will be no make-ups for any of the tests.

Besides the exams, there will be regular homework assignments, and quizzes in class, and a co-curricular requirement.

Home works: Home works will be assigned on a regular basis and posted at the course website. All home works are due at the beginning of class on the posted due date. Late home works will be penalized 10% per day, and will not be accepted beyond the beginning of class following the due date.

Quizzes: There will be short quizzes in class. These will be announced at least one class period in advance. There will be no make-ups for missed quizzes.

Co-curricular Requirement: Starting this fall, the Mathematics, Computer Science and Physics department will offer a series of discussions that appeal to a broad range of interests related to these fields of study. These co-curricular sessions will engage the community to think about ongoing research, novel applications and other issues that face these disciplines. Each student is required to attend at least one of these sessions, and turn in a short paper describing the coontents of the session, and his/her critical reflections about the topic and content. These papers are due in class within a week of the session.


The final grade will be computed based on the grades in the tests, the final exam, home works, quizzes and projects according to the following weights.

Component Weight
Home works16%
Tests (2)38% (19% each)
Final Exam22%

The grading scale is as follows: