Credit Hours: 4
Time and Place of Class: Monday/Wednesday 3:25--4:40, Computer Studies Building 601
Instructor:
Len Schubert
Department of Computer Science
Room 733, Computer Studies Building
University of Rochester
E-mail: schubert AT cs DOT rochester DOT edu
Office Hours (may still be revised): Monday 4:50-5:50 and Thursday 2:00-3:00
TAs:
Piotr Faliszewski
Room 615 Computer Studies Building
E-mail: pfali AT cs DOT rochester DOT edu
Office Hours (subject to revision): Tuesday 12:20-1:20 and Thursday 10-11
David Sloan
E-mail: ds002m AT mail DOT rochester DOT edu
Office Hours (to be revised): Friday 12:00 - 1:00 upper level of CLARC (in Rush Rhees)
Jonathan Weinheimer E-mail: jon DOT weinheimer AT gmail DOT com
Office Hours (to be revised): Monday 2:00 - 3:00 upper level of CLARC (in Rush Rhees)
Prerequisites: CSC173; MTH150
The lectures will be given under the assumption that the students have reasonable knowledge of the material covered in CSC173.Recitations:
See CSC-280 TA Page
Textbook:
Michael J. Sipser, Introduction to the Theory of Computation (2nd edition). Thomson (Course Technology), 2006. Note the list of errata at the website!
Supplementary Texts on Reserve:
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation. 2001.
- Kinber and Smith, Theory of Computation: A Gentle Introduction. Prentice-Hall, 2001.
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation. Prentice-Hall, 1998.
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
- John E. Savage, Models of computation. Addison-Wesley, 1998.
- Michael E. Garey and David S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
- Christos H. Papadimitriou, Computational Complexity. Addison-Wesley, 1994.
Course syllabus:
This course studies fundamental computer models and their computational limitations. Finite-state machines and pumping lemmas, the Chomsky hierarchy, Turing machines and algorithmic universality, noncomputability and undecidability, tradeoffs between power and formal tractability.
Course Material:
Postscript files of slides covering much of the course material will be made available through this web page.
Grading:
The following contribute to the grades:
- two in-class exams (30± 3% each),
- quizzes (10± 3% contribution),
- homework assignments (30± 3% contribution), and
- class participation (no direct contribution as points, but borderline cases are judged based on this).
Quizzes:
There will be weekly 10- or 15-minute quizzes. A quiz is a simple exercise and is based on the previous 2 lectures.Homework:
Homework assignments will be given regularly (approximately weekly). Each assignment consists of a few problems corresponding to the lectures that have been given. Each assignment is due in a week. Problems will be graded by the TAs.Your papers have to be received by the instructor or the TAs before the class meets. If none of them are available, you may give them to one of our secretaries. No late submissions are accepted.
Academic honesty policy:
Students are encouraged to discuss among themselves the principles needed to solve the problems assigned, but must not spell out specifics of solutions to one another. If you collaborated with someone (namely, worked on or shared a solution with someone), then on your paper report who the persons are. The points you earn on that particular problem will be divided by the total number of students involved in the collaboration. Failure to report collaboration, if detected, will result in a penalty---the entire score of the paper will be reduced to zero. Solutions obtained from other sources, such as the web, will also lead to a score of zero for a paper.
| CourseSchedule | Homework Information | Slides from Lectures |
CSC 173 Course Home Page for Fall 2004