Instructor
Dexter Kozen |
Teaching AssistantZoya Svitkina |
AdministratorKelly Patwell |
MWF 9:05-9:55, Thurston 205
Dexter: MW 10-11am, Upson 5143
Zoya: TTh 1:30-2:30pm, Upson 4106
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.
All handouts and homework sets will be available on the web in pdf or html format.
It is
your responsibility to check often for new postings. For viewing pdf files, we recommend Adobe Reader, available free of charge.
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 Kelly 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. You may not take the final before the scheduled 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%, quizzes and class attendance 5%.
| Prelim 1 | Wednesday, 22 October | 9:05-9:55am | Thurston 205 |
| Prelim 2 | Wednesday, 12 November | 9:05-9:55am | Thurston 205 |
| Final | Friday, 12 December | 9-11:30am | Phillips 203 |
Homework and exams will be returned in class as soon as they are graded, usually the class period following the homework due date or exam. Uncollected homework and exams can be obtained from Kelly in Upson 4147.
To submit a regrade, please fill out a regrade form (available from Kelly in Upson 5147) with an explanation of our error, attach it to your homework or exam, and submit it to Kelly in Upson 5147 within one week of the date the homework or exam was returned in class.
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.