** **

**Course web page URL:**

**http://www.cs.duke.edu/~reif/courses/cps140**

** **

**Course web page also located
at:**

**http://www.cs.duke.edu/education/courses/spring01/cps140/**

** **

**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

** **

**Reading **

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**

**Times:
**

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

http://www.cs.wisc.edu/~ghost/

** **

** **

**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

Tools:

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

** **

** **

**Grading **

Homeworks: 40%

Class Discussions: 10%

(3 quizzes) Each quiz: 5%

Midterm:
15%

Final Exam 20%

** **

**Collaboration**

** **

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.

** **

** **

** **