CS 381 - Introduction to Theory of Computing, Summer 2004

Course staff:

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

Teaching Assistant:
Peter Sirokman
4143 Upson Hall
Office phone: (607) 255-7573
User id: pfs

Our email addresses are the appropriate user id followed by @cs.cornell.edu.

Lecture time and place:

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

Office hours:

Lucja: Mon, Wed 9:45-11 am (after class), Tue, Thu 12-1pm

Peter: Mon, Wed, Thu, Fri 3-4 pm

If you need to meet with us outside of office hours, please do not hesitate to email us for an appointment (but please do email if you can; we appreciate knowing in advance that you will be coming to see us).


A public newsgroup cornell.class.cs381 has been created as a public forum for questions, technical 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. Please keep posts relevant, but do not hesitate to post if you have a legitimate comment or question! "Relevant" is a much broader notion than the topics covered in class this week; any theory-related discussion is likely to be of some relevance.


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

Required textbook:

D. C. Kozen, Automata and Computability. Springer-Verlag, 1997. This textbook is available at the Cornell Store.


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 Lucja.