• Professor Kleinberg will be out of town next week starting immediately after Wednesday's class (Sept. 2), until the end of the week. Consequently:
  • Prof. Kleinberg's office hours next week will take place on Tuesday, August 31, 3-4pm or by appointment.
  • Class is canceled on Friday, September 3.
• The schedule section of the course website now contains a list of lecture topics for the first two weeks of class, along with assigned readings. In particular, there is a handout associated with the lectures for August 27-30.
• The first homework assignment will be assigned on Friday, Sept. 3, and it will be due on Friday, Sept. 17.

Instructor:	Bobby Kleinberg rdk@cs. 4138 Upson Office hours: Wed. 3:45-4:45, Thurs. 1-2 Phone: 255-9200
TA:	Yue Gao ygao@cs. Office hours: Tuesday, 1:30-2:30, Upson 328B.

• The Design and Analysis of Algorithms by Dexter Kozen. (Required)
• Algorithm Design by Jon Kleinberg and Eva Tardos. (Recommended)
• The following are also useful references.
  • T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. 
  • A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Computer Algorithms. 
  • M. Garey and D. Johnson. Computers and Intractability . 
  • D. Kozen. The Design and Analysis of Algorithms.

The official prerequisites for the course are CS 4820 or graduate standing. We will assume knowledge of:

• discrete mathematical structures, including graphs, trees, DAGs
• basic data structures such as lists, trees, heaps, sorting and searching
• asymptotic complexity, O( ) and o( ) notation, solving recurrences
• machine models and general computability
• algebra: matrices and polynomials over the integers, the real and complex numbers, and the integers mod p.
• probability: sample spaces, random variables, expectation and variance, independence, conditional probability and expectation.

• There will be problem sets roughly every two weeks. The problem sets will generally be handed out on a Friday and will be due the following Friday. Students will turn in the homework using CMS.
• Students may work on homework in groups of up to 3 people. Each group may turn in a single solution set that applies to all members of the group. However, students are asked to understand each of their group's solutions well enough to give an impromptu white-board presentation of the solution.
• There will be an in-class midterm and a take-home final.
• The date of the in-class midterm is TBA. The take-home final will be due on the last day of class.

• Your course grade will be based on the homework and exams. Weighting will be roughly as follows:
  • 20% homework
  • 40% midterm
  • 50% final exam
  The weight of either the midterm or the final exam will be reduced by ten percentage points. For each student, the reduced weight will be applied to the exam on which that student received the lower grade.
• Grading Criteria: For the most part, you will be asked to design algorithms for various problems. (There will not be any programming assignments.) A complete answer consists of a clear description of an algorithm (an English description is fine), followed by an analysis of its running time and a proof that it works correctly. You should try to make your algorithms as efficient as possible. Compared to CS 482, the grading in CS 6820 places greater emphasis on writing correct and complete proofs.
• CMS: We are using the CS course management system at http://cms.csuglab.cornell.edu/ to manage course grades. Please check your grades regularly to make sure we are recording things properly. The system also provides some grading statistics.
• Regrade Policy: Regrade requests must be made within one week of the time that homework or exams are returned to the class.
• Regrade Process: If you believe your solution to a question was correct and it was marked incorrect then you should write up an explanation of the grading error, attach it to your homework, and bring it to the TA. Alternately, you can leave the homework and written explanation with the instructor. Note that we're talking here about correct algorithms that were treated as incorrect; in general, we will not look at regrade requests that are simply arguing about the amount of partial credit assigned. Regrade requests will be handled periodically in batch mode rather than on-the-spot.

• The mailing list is cs6820-l@cs.cornell.edu. If you have not received a message welcoming you to the mailing list, please subscribe by visiting https://lists.cs.cornell.edu/mailman/listinfo/cs6820-l.

• Any violation of academic integrity will be severely penalized. You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you are expected to write up (and understand) the homework on your own.
• Cornell's Code of Academic Integrity: http://www.cuinfo.cornell.edu/Academic/AIC.html

• Time and Place: Monday, Wednesday, and Friday, 2:30 to 3:20 in Olin 165.

• Course Description (from the Catalog): Methodology for developing and analyzing efficient algorithms. Understanding the inherent complexity of natural problems via polynomial-time algorithms, advanced data structures, randomized algorithms, approximation algorithms, and NP-completeness. Additional topics may include algebraic and number theoretic algorithms, circuit lower bounds, online algorithms, or algorithmic game theory.