CS381
Introduction to Theory of Computing

Computer Science Department
Cornell University
Summer 2000

Course Information

Time and place

Lectures are M-F from 8:30 to 9:45 in Upson 215. Lectures start on May 23 and end on June 30.

Office hours

Online help

A newsgroup cornell.class.cs381 has been set up as a way for students to pose questions to the staff. You can use Netscape or Internet Explorer to access this newsgroup by clicking on the link, or you may use any newsreader that you are familiar with. We prefer that you post your questions to this newsgroup, but if you would like to send a personal message, you can send mail directly to Tibor or Wei.

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 will 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 homeworks, 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

Quizzes will be given on most days at the beginning of the lecture. Typically they will involve five simple questions that are designed to test the understanding of the material discussed in the preceding lecture. 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.

Homeworks

Homework will be due each Monday, at the end of class. Solutions will be handed out at the end of class on due dates. The solutions will not be made available on the web. 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 homeworks no later than three days after they have been turned in.

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

Please take special care to hand in clearly written solutions both for homeworks 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 homeworks. 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.

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: 06/21/2000 by KH.