Mathematical Foundations of Computer Science

Spring, 2001


Course web page URL:



Course web page also located at:



Course Description:


·     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.


Required Background:


CPS 100 or 100E and Mathematics 103.



Professor John Reif,

       LSRC D223

phone: 660-6568,

email: reif@cs.duke.edu

Office Hours: Tues & Thurs 3:30-4:30 PM


Teaching Assistant: Apratim Roy

Office: North 01

phone: 660-4001,

email: apratim@cs.duke.edu

Office Hours:

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.


Class Lectures:

Location: LSRC D106


Tuesdays, Thursdays 2:15-3:30 PM


Lecture Notes and Schedule:

download from CPS140 Lecture Notes;

also located at CPS140 Lecture Notes


·     To read postscript files you can download the free ghostview reader at:




Text Book:

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.


Course Announcements

    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)




    Homeworks: 40%

    Class Discussions: 10%

    Tests: 50%

(3 quizzes) Each quiz: 5%

              Midterm: 15%

              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.