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.