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