Course Information CS481 Fall 04
Staff
InstructorEva Tardos |
Teaching AssistantsThanh Nguyen Joel Ossher
|
AdministratorBill Hogan |
Homework & Exams
Problem Set 1 was due on Wednesday, September 8th at the beginning of class. Typo in statement of Problem 3 fixed on Sept 2. Solutions with some grading comments are available on the racks in from of 303 Upson Hall.
Solution for the Quiz from Monday, September 6th.
Graded PS1 was distributed in class Wednesday, Sept 15. If you did not pick up your problem set, or your quiz 1 from a while back, they can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Problem Set 2 is due on Wednesday, September 15th at the beginning of class.
Graded PS2 was distributed in class Friday, Sept 24.Solutions with some grading comments are available on the racks in from of 303 Upson Hall. If you did not pick up your problem set, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Problem Set 3 was due on Wednesday, September 22nd.
Graded PS3 was distributed in class Friday, October 1st. Solutions with some grading comments are available on the racks in from of 303 Upson Hall. If you did not pick up your problem set, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Solution for the Quiz from Monday, September 27th.
Problem Set 4 was due on Friday, October 1st at the beginning of class.
Graded PS4 can be picked up in Upson 363C, Monday through Friday between 2 and 4:30. Solutions with some grading comments are available on the racks in from of 303 Upson Hall.
Problem Set 5 was due on Friday, October 8th at the beginning of class.
Graded PS5 was distributed in class Friday, October 15th. Solutions with some grading comments are available on the racks in from of 303 Upson Hall. If you did not pick up your problem set, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Problem Set 6 was due on Friday, October 15th at the beginning of class.. Solutions are available on the racks in from of 303 Upson Hall. The problem set was distributed in class on Oct 22nd. If you do not pick up your problem set, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Midterm 1: was in class Wednesday, October 20th. For information about the prelim, and practice questions see this handout. The midterm is graded, and will be distributed in class on the 22nd. Solutions are available on the racks in from of 303 Upson Hall. If you did not pick up your prelim, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Problem 1 was graded by Joel, Problems 2-3 by Thanh, and Problem 4 by Eva. If you have trouble with the grading, please complain first to the person who graded it.
Problem Set 7 was due on Friday, October 29th at the beginning of class. (Problem 1/f fixed 10/25 at 10:20pm). Solutions are available on the racks in from of 303 Upson Hall. The problem set was distributed in class on Nov 5th. If you do not pick up your problem set, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Solutions for Quiz 3 are available on the racks in from of 303 Upson Hall. The graded quiz was distributed in class on Nov 5th. If you do not pick up your quiz, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Problem Set 8 was due on Friday, November 5th at the beginning of class. Typo in statement of stronger pumping lemma (in problem 4): it is all about context free grammars, not regular sets. Solutions are available in Upson 303. The graded problem set was distributed in class on Nov 10th. If you do not pick up your problem set, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Midterm 2: was in class Friday, November 12th.
Solutions for Quiz 4 The graded quiz was distributed in class on Dec 3rd. If you do not pick up your quiz, it can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Problem Set 9 was due on Monday,
November 22nd at the beginning of class.
Problem Set 10 was due Friday, December 3rd. Solutions will be available on the racks in from of 303 Upson Hall starting Monday, December 6th. The problem set will be graded by Wednesday December 8th, and will be available in Upson 363C, Monday through Friday between 2 and 4:30.
The final is Wednesday December 15th, 9-11:30 in Phillips 219. The final is cumulative. Here is a handout with practice questions. Solutions will be available on the Web on Sunday (Dec 12th), and on the racks in from of 303 Upson Hall starting Monday.
Handouts & Links
CS481 Fall 02
CS481 Fall 03
CS381 Fall 04
A note about proofs
Textbooks
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. In addition to this book, we cover applications to finite automata such as Hidden Markov Models, and protocols. We will also cover supplementary topics on hardness of computations, crypto systems based on hard problems, and zero knowledge proofs, 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 (course text for CS381 F03).
- 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.
- 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.
Handouts
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.
Graded homeworks not claimed in class can be picked up in Upson 363C, Monday through Friday between 2 and 4:30.
Homework solutions with some grading comments will be available on the racks in from of 303 Upson Hall.
A tutorial on Hidden Markov Models by Lawrence Rabiner.
Homework & Exams
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 9am on the due date. You may submit them in class or to Bill Hogan in Upson 4119.
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 closed book and notes. You may not take the final before the scheduled date.
There will also be occasional unannounced quizzes.
The homework will be worth 35% of the course grade, the prelims 15% each, the final 30%, quizzes and class attendance 5%.
Grades.
We are using the CS course management system at https://cms2.csuglab.cornell.edu/ to manage course grades. Please check your grades regularly, to make sure we are recording things properly. The system also has general course statistics.
Exam Schedule
|
Prelim 1 |
Wednesday, October 20 |
9:05-9:55am |
Hollister 110 |
|
Prelim 2 |
Friday, November 12 |
9:05-9:55am |
Hollister 110 |
|
Final |
Wednesday, December 15 |
9-11:30am |
Phillips 219 |
Returns
Homework and exams will be returned in class as soon as they are graded, usually within a week following the homework due date or exam.
Regrades
To submit a regrade, please fill out a regrade form (available from Bill in Upson 4119) with an explanation of our error, attach it to your homework or exam. You can submit a regrade directly to Thanh during his office hours, or submit it to Bill in Upson 4119 within two week of the date the homework or exam was returned in class.
Policy Regarding Collaboration on Homework
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 books, 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.
Newsgroup & Email
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 and to this Web page, 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 vs CS481
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.
Prerequisite: CS280
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.