Dexter Kozen

kozen@cs.cornell.edu

Upson 5143

255-9209 office

257-4579 home

Alexa Sharp

asharp@cs.cornell.edu

Upson 5157

255-9834 office

Gabor Foldes

gf27@cornell.edu

Upson 326

255-4330 office

Kamal Aboul-Hosn

kamal@cs.cornell.edu

Upson 4161

255-1149

Beth Howard

bhoward@cs.cornell.edu

Upson 5147

255-4188

MWF 9:05-9:55, Hollister 110

Dexter: MF 10-11, Upson 5143

Alexa: W 12:15-1:15, Th 2:30-3:30, Upson 5157

Gabor: Tu 3-4, Upson 328

Kamal: Th 6-8pm, Upson 328

The following text is required:

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

We will follow the text fairly closely; check the table of contents for the syllabus. Supplementary topics will be covered as time permits.

Other useful sources:

- J. E. Hopcroft, R. Motwani, and J. D. Ullman,
*Introduction to Automata Theory, Languages, and Computation*. 2nd edition. Addison-Wesley, 2001. - H. Lewis and C. Papadimitriou,
*Elements of the Theory of Computation*. Prentice-Hall, 1981. - M. A. Harrison,
*Introduction to Formal Language Theory*. Addison-Wesley, 1978. - N. J. Cutland,
*Computability*. Cambridge Univ. Press, 1980. - H. Garey and D. Johnson,
*Computers and Intractibility: A Guide to the Theory of NP-Completeness*. W. H. Freeman, 1979.

These titles are on reserve in the Engineering Library, Carpenter Hall.

Homework sets, handouts, and announcements will be posted periodically. It is your responsibility to check for new postings.

There will be weekly homework assignments consisting of 4-6 problems. Assignments and solutions will be available online. Solutions may be handwritten or typeset; no email please. Solutions are due by 4pm on the due date. You may submit them in class or to Beth in Upson 5147.

Late homework will in general not be accepted. Extensions will be granted only in advance of the due date and only with a good excuse, such as illness. No homework will be accepted for any reason after the solutions have been posted.

There will be two in-class prelim exams and a final. Exams will be open book and notes. The final exam is scheduled for Thursday, Dec. 19, 12:00-2:30pm. You may not take the final before this date. If you miss the final you will receive a grade of incomplete in the course.

There will also be periodic unannounced quizzes.

The homework will be worth 35% of the course grade, the prelims 15% each, the final 30%, and the quizzes 5%.

The final exam will be **Thursday, ****December 19,
12-2:30pm, Phillips 101**.

You may discuss with your colleagues general strategies for solving the homework problems, but you must formulate the solutions and write them up alone. In particular, you may not work from notes taken during collaborative sessions. Acknowledge all sources, including others in the class from whom you obtained ideas. Failure to respect this policy will be considered a violation of the Code of Academic Integrity. If you are unsure about anything, please ask.

A public newsgroup cornell.class.cs481 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. Free-ranging technical discussions are often quite enlightening and are especially encouraged.

Announcements will be posted to the newsgroup, so it will be in your interest to check there daily.

There is also a course email address cs481@cs.cornell.edu. Email to this address will be forwarded to the entire course staff. Use this medium for any question unsuitable for general distribution, such as a detailed question concerning your solution to a homework problem. Please prefer the course email address over the personal email of a particular member of the course staff if a response by anyone on the staff would suffice; but direct followups to the member of the course staff who responds.

We will make every attempt to answer questions posted to the newsgroup or sent to the course email address in a timely fashion.

CS381 and CS481 follow roughly the same syllabus, but 481 is somewhat faster paced and goes into more depth. It is meant for more theoretically inclined students, grad students, and undergrads bound for grad school. Corrective shifting is encouraged in the first few weeks.

The homework due dates of the two courses are coordinated for the first few weeks. If you shift after the due dates, we will accept your homework scores from the other course.

Familiarity with discrete mathematics at the level of CS280 is assumed. We will make extensive use of graphs, trees, dags, sets, functions, relations, equivalence relations, and partial orders. Familiarity with propositional and first-order predicate logic and the basic techniques of mathematical proof, including a thorough understanding of mathematical induction, is also essential. In addition, familiarity with the content of CS312 and a course in elementary logic or algebra such as Math 432 or Math 481 will be helpful. Of course, the most important prerequisite is mathematical maturity.