CS 381
Introduction to Theory of Computing

Computer Science Department
Cornell University
Summer 2002

Course Information

Time and place

Lectures are M-F from 8:30 to 9:45 in Upson 215. Class begins on May 22 and ends on July 3.  

Office hours

Newsgroup

There is a newsgroup for the class at cornell.class.cs381. At the moment we do not plan to moderate it, but you can use it to discuss problems and ideas in the class.  For questions outside of class or office hours, you can send mail directly to Greg or Tiberiu, but if you send an email after 4pm, then you should not expect a reply before the next workday.  

Prerequisites

CS280 - Discrete Structures or an equivalent course.

Text

The textbook for this course is

Dexter Kozen: Automata and Computability. Springer-Verlag, New York. 1997, ISBN 0-387-94907-0.

There may be occasional course handouts, which will be available on the web server. These, together with the material presented in class will cover all the topics that will be required in the course.

For further readings and extensions, see one of the following:

Hopcroft, J. E., and Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

Harrison, Michael A., Introduction to Formal Language Theory, Addison-Wesley, 1978.

Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, Prentice-Hall, 1998.

Copies of these books are on reserve in the Engineering Library.

Course requirements

Students should be familiar will all the material covered in the lectures and in the lecture notes posted on the course web site. There will be a 5-10 minute quiz at the beginning of most classes covering the material of the previous lecture. There will be six homework sets, two preliminary exams, and a final exam. Prelims will be cumulative, but they will concentrate on new material. The final will be comprehensive.

Grades will be based on a combination of the quiz, homework and exam scores (10% quizzes, 30% homework, 30% preliminary exams, 30% final exam).

Quizzes

Unannounced quizzes will be given at the beginning of randomly selected lectures. Typically they will involve a few simple questions that are designed to test the understanding of the material discussed in the preceding lecture or two. Each question will be graded out of 1 point, no fractional scores will be given.

The quizzes are intended to provide you with feedback about the style of thinking, the proof methods, and the notations that are required in the course and to encourage you to come to class on time and to keep up with the reading and lectures.  

Homework

Homework will be due approximately once per week. No late assignments will be accepted, but the lowest score will be dropped when computing the final grade. We will do our best to grade and return homework no later than three days after the due date.

Even though late homework will not be accepted for credit, we will be willing to correct them and give you feedback.

Please take special care to hand in clearly written solutions both for homework and exams. The course staff reserves the right to ignore any illegible answers.

In writing up your homework you are allowed to use any book, paper, or published material. If you do so, you are required to cite the complete bibliographical data of your source(s). Simply copying a proof is not sufficient, you are expected to write it up in your own words, and you should also be able to explain it if you are required to do so.

Your proofs can only refer to course material or previous homework. Except for this, all your homework must be self-contained, i.e. any other results that are used must be explicitly proven.

It is very important that you stay caught up since the course is cumulative. If you don't understand the material at the beginning it will be difficult to catch up later. If you have problems, you are encouraged to talk to the course staff as soon as possible.

Exams

There will be two prelims and a final.  The precise exam schedule will be announced later, but the first prelim will be held between June 5 and June 7, the second prelim will be between June 20 and 21, and the final will be held on July 3.  

Regrades

If you believe there is an error in the grading on homework, an exam or quiz, you must submit a written regrade request along with your original work.  There are forms for regrade requests available in the hallway outside 303 Upson.  Your request must indicate what you want regraded and why, and must be submitted within one week of the return of the work in question.  

Academic Integrity

We expect you to maintain the utmost level of academic integrity. This means that all work you submit in CS381 must be the result of your own individual effort. You may discuss the text of the homework problems (i.e. what is required in the problem), general proof strategies, and algorithms with other students in the course, but you may not cooperate in the development or actual writing of solutions.

This implies that one student should never have in his or her possession a copy of all or part of another students' homework. It is your own responsibility to protect your work from unauthorized access at all times. When in doubt, ask beforehand!

You are not permitted to receive more help from persons not enrolled in this class than you would be allowed to receive from your enrolled colleagues.

During the administration of exams and quizzes any form of cooperation or help is forbidden.

Academic dishonesty has no place in a university; it wastes our time and yours, and is unethical. Any violation of this code will be referred to the proper authorities and may lead to failure in the course. For more details see the Code of Academic Integrity. 

CS381 home page
Last Modified: 05/22/2002 by GB.