Course web page URL:
Course web page also located at:
· An introduction to theoretical computer science including:
1. abstract machines such as finite state automata, pushdown automata and Turing machines,
2. formal languages from regular languages to recursively enumerable languages, and also
3. complexity theory including problems and puzzles that are NP complete, and and games that are PSPACE complete.
CPS 100 or 100E and Mathematics 103.
Professor John Reif,
Office Hours: Tues & Thurs 3:30-4:30 PM
Teaching Assistant: Apratim Roy
Office: North 01
Monday, Wednesday 1:00-3:00 PM
Recitation # 01R (5557):
LSRC A158 Wends 2:20-3:20 PM
Recitation # 02R (5558):
Moved to LSRC D106 Wends 5:30-6:30 PM
If you've looked at material before it's discussed in class you'll get much more out of the class discussion. You need to be prepared to ask and answer questions in class, since this will represent 15% of your class grade. Prior to each lecture, you should read:
· that day’s Lecture (see below)
· the assigned chapter from Sipser.
Location: LSRC D106
· To read postscript files you can download the free ghostview reader at:
Introduction to the Theory of Computation,
by Michael Sipser,
PWS Publishing Company, 1997.
Secondary (Optional) Text Book:
Elements of the Theory of Computation,
by Lewis and Papadimitriou,
Prentice Hall, 1998.
Anonymous Course Feedback
Read the CPS 140 Newsgroup
· We use the tools JFLAP, JeLLRap and others in this course Click here for information on these tools.
You should regularly read the newsgroup duke.cs.cps140 as it may contain announcements, hints, and information relevant to this class.
Homework: Delivered to TA
Due at start of class on Due date
Late Homework 20% less per day late
(after start of class on due date)
Class Discussions: 10%
(3 quizzes) Each quiz: 5%
Final Exam 20%
Tests must be your own work.
Homework assignments should be primarily your own work. You may consult with one or two other students (and as many times as you want with TA) on these assignments. For each assignment you are expected to include a list of the people with whom you have consulted (including students, TA's, tutors, professors). You may not consult with the same CPS 140 students on two consecutive assignments.