CS60: Theory of Computation
Earlham College
Department of Computer Science
Ray Ontko, Instructor
Spring Semester 1998-99
Dennis Hall, Room 214
2:30-3:50 MTh
Syllabus
Why this course?
Theory of Computation provides a rigorous introduction to the
theoretical foundations of computer science. It addresses a
number of inter-related topics and attempts to answer the questions,
"What is a computer?", "What is an algorithm?", and "What is
computable?" Students taking the course will engage in a close
reading of important theorems and proofs, will prove a number of
unobvious and interesting assertions in order to practice and elucidate
the techniques used in this area of the discipline, and will develop
a number of programs to help connect the theory to practice.
Although this is not a "math" course, it does make significant use of
mathematical symbols, abstractions, definitions, theorems, proofs,
lemmas, corollaries, logical reasoning, inductive proofs, and the like.
If such concepts are difficult for you, you will find this course to be
difficult but rewarding; I invite you to accept the challenge.
Pre-requisite Course
There is one pre-requisite course listed for Theory of Computation.
CS38: Advanced Programming assures a level of mastery
of programming and the development of a basic mental structure
for the inner workings of an electronic computer. As a result of
CS38 (or other programming experiences) I will assume that you
have mastered C, C++, or Java, and could design, code, and debug
reasonably complex programs of moderate length (a few thousand lines).
I consider CS38 (or equivalent) to be an absolute requirement
for taking this course.
This course will use a
text
and its
exercise problems to help you build a
foundation for understanding the theory of computation.
There will be seven sections to the course, with
examinations
at the conclusion of each of the first three sections, and a final
examination at the end of the course.
Several of the sections will include a
programming project to help you apply
what you have learned, and several sections may include additional
reading in the research literature to allow you to see how
the leading edge is advanced in this area of the discipline.
Your full participation and engagement
in the course is a critical part of learning the habits and methods
appropriate to this area of study.
Your grade
for the course should reflect the degree to which you have mastered
the material and techniques of the subject area, and the degree to
which you have taken advantage of what the course has to offer.
These topics and the course schedule,
how to reach me, and a possible
motto are
discussed below.
This syllabus and other handouts will be available,
where practical, on the course homepage.
There is also a listserv available to
facilitate e-mail correspondence between members of the class.
The required text for the course is
Lewis, Harry R., and
Christos H. Papadimitriou,
Elements of the Theory of Computation, Second Edition
(Prentice-Hall, 1997).
It includes wonderful explanation
of the material and excellent exercise problems to probe and
develop your understanding. It is a "classic" in the field
and is used in