CS 381 - Introduction to Theory of Computing, Summer 2005

About the course:

CS 381 is an introduction to the modern theory of computing. The course has three natural sections:

CS 381 is offered in the summer and fall semesters; in terms of material covered and workload, both offerings are equivalent.

In the fall semester, the department also offers CS 481, a somewhat deeper and faster-paced course covering the same topics as CS 381.


Lucja Kot
4104 Upson Hall
Office phone: (607) 255-9537
User id: lucja

My email address is my user id followed by @cs.cornell.edu.

Lecture time and place:

Monday to Friday, 8:30am - 9:45am, Hollister 362.

Office hours:

I will be available most days after class, until 11 or so. If you would like to meet at another time, please don't be shy about emailing for an appointment or just dropping by my office.


There will be a class newsgroup cornell.class.cs381 , which you are welcome to use for questions, discussions, announcements, complaints, suggestions, etc. If you are new to newsgroups, instructions can be found here. Be careful not to post homework solutions, even partial ones.


Your final grade in the course is based on regular homework assignments (40%), two prelims (15% each), a final exam (25%), and in-class quizzes - announced and unannounced - (5%).

Required textbook:

D. C. Kozen, Automata and Computability. Springer-Verlag, 1997.


CS 280 or equivalent. It is essential that you be familiar with the basics of discrete mathematics, as covered (for example) in CS 280. We will make extensive use of trees, sets, functions, relations, and other key concepts. You should also have a solid understanding of basic mathematical proof techniques, including a good grasp of mathematical induction.

If you have not taken CS 280 or an equivalent course, and/or if you are unsure about your background, please talk to me.