CS-311: Theory of Computation
Fall 2002 Syllabus
Instructor:
Course
Abstract:
As we can see by looking around us, there are many
things a computer can do. They are used
for accounting; they are used in automobiles to improve fuel economy and
control emissions; they are used to forecast weather; and there are even some
indications that computers can exhibit intelligent behavior. Are there any limits to what computers can
do? Does the answer to this question
depend on whether you use a PC or a Sun Workstation? Is "C" more powerful than PASCAL? This seminar explores these questions by
investigating several models of computation, illustrating the power and limitations
of each of these models, and relating these models to computational problems
and applications. Topics include finite
state automata, pushdown automata, grammars, Turing Machines, the Universal
Turing Machine, and Computability.
Course
Hours:
Tuesday and Thursday 11:00-12:15 in Kindade 203.
Prerequisites:
Computer Science 101 and
Math 232
Textbook:
"Introduction to the Theory of Computation" By Michael Sipser.
PWS Publishing, Boston
ISBN 0-534-94729-X
Many of you will find this
text difficult to read, at first. Don’
t let that discourage you. One of the
objectives of this course is for you to learn to read material like this. Be sure to read the relevant parts of the text BEFORE we discuss them in
class … and again afterwards. … and then,
maybe again J
Course
Material:
The course will be presented according to the course outline below. Students will be graded on their understanding of the course as reflected in their class participation, homework assignments, and examinations approximately according to the following weighting:
Class Participation 20%
Homework 20%
Examinations 60%
-------
100%
This is a theoretical
course. Although homework may involve writing
a simple program or two, the course will not be programming intensive. The instructor will pose questions during
class hours for discussion. Homework
will be assigned. There will be at
least one midterm and a final.
Examinations and homework will cover material in the reading assignments
and what is presented in class.
Class Participation
Students are REQUIRED to read about each topic BEFORE it is discussed in class. Although material will be presented in class, a major portion of each class session will involve student discussion. Final grades will reflect attendance and participation in these discussions.
Class time is a time to discuss concepts and ideas inspired by doing the assignments. It is a time to critique ideas and perhaps argue. There are rules
1. Do not monopolize the
discussion. Encourage your colleagues
to participate.
2. Listen actively.
3. Critique constructively.
4. Keep focused on the goals
of the discussion.
We may add to or modify this
list as the class evolves. These
discussions are fun!
Homework
No single homework
assignment will be very time consuming, PROVIDED
you keep up with the class discussions and reading. Homework assignments are an opportunity to explore ideas with
little penalty. They will be critiqued
but they will not be graded severely.
If a program is assigned, however, it must be demonstrated to work
properly or it will receive no credit (see below in section on evaluation)
Exams
Usually, there are two in-class exams (midterms) and one take-home exam (final). In-class exams usually ask you to discuss definitions, prove theorems, and solve problems. Take-home exams often consist of 4 or 5 essay questions that ask you to apply what you have learned to discuss some “big” problem.
Evaluation:
During the semester you will
be given a number of assignments (homework, exams, programming
assignments, presentations, etc.) and students are required to participate in
class discussions. Each assignment will
be worth a certain number of “points”
as will participation in class. A
student’s grade will be determined by the total number of points that he/she
receives (as a percentage of the total possible).
Homework assignments will be critiqued and
graded but will not be graded severely.
They are considered to be your chance to explore what you know. Material in homework assignments will, very
likely, be explored in exams.
Programming assignments, if there are any, are
designed to provide a deeper understanding of the course material. They are
also important in themselves since they provide programming experience. All programs must be demonstrated to the
instructor. At the demonstration, the
student must present the instructor with the final program printout and be prepared
to answer a few questions about the program and the relevant course
material. The score received for the
assignment will be determined as follows:
No points will be given if
the program does not work.
If the program does work,
then its score will be determined by three factors:
1.
The
demonstration (85% of the score):
How well the program
functions
How well the student answers
the questions.
2.
Program
documentation (10% of the score)
3.
Program
style (5% of the score)
Examinations will be based on the material
explored in class, the written assignments, programming projects (if any), and the assigned readings from the
text. Grading will based on the
following:
1. Your understanding of the concepts. You will be penalized considerably if you
use of a concept in a way that indicates you do not understand it. Make sure you understand the concepts and
how to use them in your arguments. This
is particularly important in a take-home exam, where you have ready access to
the original ideas. Use class time and
the homework assignments to test your understanding … ask questions and try to
answer the ones that are “on the floor”.
2. The logical
precision of
your work. Don’t make “sweeping
statements” in you work. Be analytical
in your discussion and make “small”, logical steps. Problems given on in-class exams will usually be “small”. In these problems you will be graded on how
carefully you reason. In a take-home
exam, the questions will sometimes be designed to be too difficult, too
“big”, or to vague to answer completely in the allotted time. You task in this situation will be to
discuss them in terms of what you have learned and form a well-reasoned opinion. These questions are designed to give you an
opportunity to “show off” what you have learned.
Class participation points will based on frequency and quality of student
participation.
Honors Policy:
Occasionally, team projects will be assigned. However, this is NOT
the rule; it is the exception. Unless specifically indicated in writing on the
assignment sheet, homework, exams, and projects you submit must be your own
work. Plagiarized work will not be accepted (will receive a zero), as will the
work it is plagiarized from.
Course Outline (Tentative)
Introduction
Sets
Relations
and Functions
Proof
Techniques
Languages
and Modeling Computers as Language Processors
NOTE: It will be assumed that you are familiar with this
introductory material from MA-232 (a prerequisite). It is covered in the text if you feel a need for a review.
Finite Automata, Regular Languages and Regular Expressions
Definition of Finite State Automata (FSA)
Deterministic FSA (DFSA)
Non Deterministic FSA
(NDFSA)
Equivalence of DFSA and
NDFSA
Properties of Languages
Accepted by FSA
FSA and Regular Expressions
Existence of expressions
which are not regular
Pushdown
Automata and Context Free Languages
Definition of Pushdown
Automata
Context Free Languages
Regular Expressions vs.
Context Free Languages.
Pushdown Automata and
Context Free Grammars
Properties of Context Free
Languages
Existence of Languages which
are not Context Free
Turing
Machines
Definition of a Turing
Machine
Combining Turing Machines
Extensions of the Turing
Machine
Non-Deterministic Turing
Machines
The
Universal Turing Machine
Church's Thesis
Unrestricted Grammars and
the Turing Machine
The Universal Turing Machine
Computability and Decidability
The Halting Problem
Turing Enumerability,
Acceptability and Decidability
Unsolvable Problems about
Turing Machines
Unsolvable Problems about
Grammars
Computational
Complexity
Time Bounded Turing Machines
and Rate of Growth
The Classes P and NP
NP Completeness