CS4123 Theory of Computation
Syllabus  B 2002
WARNING:
Small changes to this syllabus may be made during the course of the term.
COURSE DESCRIPTION:
Building on the theoretical foundations from CS 3133, this course
addresses the fundamental question of what it means to be "computable,"
including different characterization of computable sets and functions.
Topics include the halting problem, the ChurchTuring thesis, primitive
recursive functions, recursive sets, recursively enumerable sets,
NPcompleteness, and reducibilities.
COURSE GOALS AND OUTCOMES:
Course Goals:
The goal of CS4123 is to provide the students with knowledge and
techniques that will allow them to determine whether a given problem
is or is not solvable with a computer (decidable vs. undecidable
problems), and if it is solvable with a computer, whether or not it
can be solved within a "reasonable" amount of time (tractable vs.
intractable problems).
Course Outcomes:
During the course of the term the students will learn the necessary
knowledge and will gain the necessary first hand experience to:
 Understand the difference between
decidable and undecidable problems
 Classify a given formal description
of a problem as either decidable or
undecidable
 Design Turing Machines to solve
problems
 Understand ChurchTuring Thesis
 Understand the difference between
tractable and intractable problems
 Classify a given formal description
of a decidable problem as either
tractable or intractable
 Apply Reducibility techniques to
classify problems
 Analyze the time complexity of
a given problem
 Classify a given decidable problem
as belonging to P, NP, NPcomplete,
or exponential time complexity classes
CLASS MEETING:
Mo, Tu, Th, Fr 1:00  1:50 p.m.
Classroom: AK233
PROFESSOR:
Prof. Carolina Ruiz
ruiz@cs.wpi.edu
Office: FL 232
Phone Number: (508) 8315640
Office Hours:
Mo.  2:00    3:00 pm

Th.  3:00    4:00 pm, or by appointment

TEACHING ASSISTANT:
Beth Donovan
bdonovan@cs.wpi.edu
Office Hours: CS Annex (GL05)
Tu.  12:00    1:00 pm

Thu.  11:00    12:00 pm

Fr.  10:00    11:00 am

SENIOR ASSISTANT:
Adam Elliott
aelliott@wpi.edu
Office Hours: CS Annex (GL05)
Wed.  7:00    8:00 pm

Thu.  5:00    6:00 pm

TEXTBOOK (required):
RECOMMENDED BACKGROUND:
CS 3133 Foundations of Computer Science.
GRADING AND ACADEMIC HONESTY POLICY:
Exam 1
 25%

Exam 2
 25%

Quiz 1
 10%

Quiz 2
 10%

Homework
 30%

Class Participation
 Extra Points

You may discuss the homework with your classmates if you wish, but
you must develop and write your own solutions.
Your solutions must be your own original work. However, if for
some reason you use any other sources of ideas,
including for instance books, web pages, etc.,
you must explicitly
acknowledge those sources.
Failure to identify
nonoriginal work is considered academic dishonesty.
Collaboration or
other outside assistance on exams is not allowed.
Your grade will reflect your own work and achievements during the
course. Any type of cheating will be penalized with an NR grade for the
course and will be reported to the WPI Judicial Board. See
http://www.WPI.EDu/Pubs/Policies/sect5.html for the
WPI's Academic Honesty Policy.
EXAMS
There will be a total of 2 exams. Each exam will cover the
material presented in class since the beginning of the term.
In particular, the final exam is cumulative.
Both exams will be inclass, closedbook, individual exams, unless otherwise
noted.
HOMEWORK
A total of four homework assignments will be given during the term.
Solutions to the homework will be made available soon after
homework is collected
so no late homework will be accepted.
Homework in this class is individual.
You may discuss the homework with your classmates if you wish,
but you must develop and write your own solutions.
According to the
WPI Undergraduate Catalog, "Unless otherwise indicated,
WPI courses usually carry credit of 1/3 unit. This level of activity
suggests at least 17 hours of work per week, including class and laboratory
time." Hence,
you are expected to spend at least 13 hours
of work per week on this course outside the classroom.
QUIZZES
Two major quizzes will be given during the term.
One between the beginning of the term and Exam 1, and
one between the Exam 1 and Exam 2.
These quizzes will be based on the homework assignments
and the material covered in class, and will serve as
preparation for the Exams.
Also, other smaller, pop quizzes may be given during the term. Be prepared!
CLASS PARTICIPATION
Students are expected to attend class and to read the material assigned
to each class in advance. Class participation will add extra points to
students' grades.
CLASS MAILING LIST
The mailing list for this class is: cs4123@cs.wpi.edu
BS/MS GRADUATE CREDIT
This course may be taken for graduate credit by students in the BS/MS CS program.
Written permission from the professor is required. In order to receive graduate
credit, students who have signed up for this program need to solve and turn in
solutions to additional, higher level problems included in each of the course's
homework assignments.
CLASS WEB PAGES
The web pages for this class are located at:
http://www.cs.wpi.edu/~cs4123/b02/
Announcements will be posted on the web pages and/or
the class mailing list, and so you are urged to check your email and
the class web pages frequently.
ADDITIONAL SUGGESTED REFERENCES
The following additional references complement and/or supplement
the material contained in the required textbook.

Christos H. Papadimitriou,
``Computational Complexity'',
AddisonWesley Publishing Company, 1994.

H.R. Lewis and C.H. Papadimitriou, ``Elements of the Theory of Computation''.
Second edition. Prentice Hall, 1998.

M.R. Garey and D.S. Johnson, ``Computers and Intractability: A Guide to
the Theory of NPCompleteness''. W.H. Freeman, 1979.

J.E. Hopcroft and J.D. Ullman, ``Introduction to Automata Theory,
Languages, and Computation''. Addison Wesley, 1979.

T.H. Cormen, C.E. Leiserson, R.L. Rivest,
``Introduction to Algorithms''. McGrawHill, 1989.

H. Rogers, ``Theory of Recursive Functions and Effective
Computability''. The MIT Press, 1987.
WARNING:
Small changes to this syllabus may be made during the course
of the term.