CS4123 Theory of Computation. A99
Syllabus
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.
CLASS MEETING:
Mo, Tu, Th, Fr 9:00  9:50 a.m.
Classroom: AK219
PROFESSOR:
Prof. Carolina Ruiz
ruiz@cs.wpi.edu
Office: FL 232
Phone Number: (508) 8315640
Office Hours:
Mo.  11:00    11:50 am

Th.  10:00    10:50 am, or by appointment

TEACHING ASSISTANT:
Peter S. Leveille
psl@wpi.edu
Room: FL A20
Office Hours:
Mo  3:00    4:00 pm

Tu  11:00    12:00 m

Fr  10:00    11:00 am

Messages sent to cs4123_ta@cs.wpi.edu reach both the professor and the
TA.
TEXTBOOK (required):
RECOMMENDED BACKGROUND:
CS 3133 Foundations of Computer Science.
GRADING AND ACADEMIC HONESTY POLICY:
Exam 1
 25%

Exam 2
 25%

Exam 3
 25%

Homework
 25%

Class Participation
 Extra Points

You are encouraged to discuss the homework with your classmates, but
you should develop and write your own solutions. You should explicitly
acknowledge any sources of ideas used that are not your own; this
includes books, web pages, etc. 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 3 exams. Each exam will cover the
material presented in class since the beginning of the term.
In particular, the final exam is cumulative.
The exams are scheduled for Sept. 10, Sept. 24, and Oct. 12.
All exams will be inclass, closedbook, individual exams, unless otherwise
noted.
HOMEWORK
Homework will be due Sept. 7, Sept. 21, Oct. 5, and Oct. 11.
Solutions to the homework will be made available soon after
homework is collected,
so no late homework will be accepted.
You are encouraged to discuss the homework with your classmates,
but you should develop and write your own solutions.
QUIZZES
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
 Messages sent to cs4123@cs.wpi.edu go to the entire class, and
 messages sent to cs4123_ta@cs.wpi.edu go to the lecturer and the TA only.
CLASS WEB PAGES
The web pages for this class are located at:
http://www.cs.wpi.edu/~cs4123/1999a/
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.