Announcements

• Constantine wrote a set of practice problems for the final exam, which have been posted on the Handouts section of the website.
• Lecture notes on Turing machines have been posted on the Handouts section of the website.
• A set of sample solutions for NP-completeness problems was written by Constantine Moraites. It is posted on the Handouts section of the website.
• A study guide for Prelim 2 was written by Constantine Moraites. It contains information about what material the prelim will cover, and guidelines for how to go about solving the types of problems that may be asked on the prelim.
• Because of Tuesday's prelim, we are using the following modified office hour schedule for the week of April 11-15. After this week, office hours will return to their normal schedule.

  Name	Office	Hours
  Bobby Kleinberg	4138 Upson	Mon. 10:15-11:15
  		Thurs. 11-12
  Kyu-Young Kim	328 Upson	Mon. 12-1
  Anthony Chang	328 Upson	Mon. 1-2
  Haden Lee	328 Upson	Mon. 2-3
  Tian Li	328 Upson	Mon. 3-4
  Li Peng	328 Upson	Mon. 4-5
  Greg Zecchina	328 Upson	Mon. 5-6
  Ben Pastel	328 Upson	Tues. 12-1
  Harry Terkelsen	328 Upson	Tues. 5-6
  Constantine Moraites	328 Upson	Tues. 6-7
  Nick Alessi	328 Upson	Thurs. 6:15-7:15
  Gautam Kamath	328 Upson	Thurs. 5:45-6:45

• To view videos of lectures from CS 4820, Spring 2010, visit Videonote, and select Spring 2011 as the semester. (That is not a typo! You must select Spring 2011, even though the lectures were recorded in 2010.) Choose CS 4820 from the drop down list, and select the lecture you want to view. Cornell NetID required. Lectures from January 25 to February 3 were not recorded, unfortunately.
• If you haven't added yourself to the mailing list, please do so by visiting https://lists.cs.cornell.edu/mailman/listinfo/cs4820-l and following the instructions there.

Staff and Office Hours

• Add cornell.edu to any incomplete email addresses below.

CS 4820 STAFF	Name	Email	Phone	Office	Hours
Instructor	Bobby Kleinberg	rdk2	255-9200	4138 Upson	Mon. 10:15-11:15
					Thurs. 11-12
TAs	Anthony Chang	ayc44		328 Upson	Weds. 1-2
	Ben Pastel	brp39		328 Upson	Tues. 12-1
	Constantine Moraites	cdm82		328 Upson	Tues. 6-7
	Gautam “G” Kamath	gck43		328 Upson	Thurs. 5:45-6:45
	Greg Zecchini	gez3		328 Upson	Thurs. 3:30-4:30
	Harry Terkelsen	het32		328 Upson	Weds. 4-5
	Hooyeon “Haden” Lee	hl364		328 Upson	Weds. 5-6
	Kyu-Young Kim	kyk8		328 Upson	Thurs. 1:30-2:30
	Li Peng	lp256		328 Upson	Mon. 4-5
	Nick Alessi	naa34		328 Upson	Thurs. 6:15-7:15
	Tian Li	tl268		328 Upson	Weds. 3-4
Course Administrator	Maria Witlox	mpr13	255-3133	4146 Upson

Mailing lists

• Broadcast messages from the course staff to students will be sent using cs4820-l@lists.cs.cornell.edu. All students should subscribe.
• There will be an additional mailing list, cs4820-staff-l@lists.cs.cornell.edu, for the staff only. Students should use this for addressing questions to the course staff about homework clarifications and procedural questions (e.g. scheduling a make-up prelim). Do not use this list as a substitute for office hours. Questions about the lectures, homeworks, etc., should be asked in office hours.

Homework

• There will be weekly problem sets, due (usually) on Friday. Students will hand in homework using CMS.
• Late Homework Policy: It is expected that homework will be turned in on time. Assignments can be turned in late (via email to cs4820-staff-l@lists.cs.cornell.edu) until 12 noon on the due date, with a penalty of 8 points out of 30 for the assignment. Beyond 12 noon on the due date, late homework will not be be accepted except in emergency situations.  If a genuine emergency situation exists you must inform the course staff as soon as possible.
• Deadline Extensions: Each student is entitled to one extension of the homework deadline during the semester, if the student has a valid excuse and asks for the deadline extension more than twelve hours before the assignment is due. In the event of such a request, the deadline will typically be extended from a Friday morning to the following Monday morning. The definition of valid excuse will be interpreted to include excessive workload in other classes, travel for academic reasons or for a job interview, personal illness, or other reasons at the professor's discretion.
• Submitting Homework: To simplify the process of distributing papers for grading, each homework will consist of 3 problems.  Each problem must be turned in separately.  In other words, each of problems 1, 2, 3 will be placed in separate piles when homework is handed in on Friday. The student's name and netID should appear on each page they turn in.
• Returning Homework: Homework will be returned at the end of class (usually) on Monday. Any homework not picked up in class can be picked up from Upson 360, 10:00-12:00 and 2:00-4:00 Monday through Friday.  You will need your Cornell ID and you will not be able to pick up an assignment for another student.
• Homework Privacy: Normally, graded homework is handed back in a self-service stack.  In other words, your homework grade is not private. If you prefer more privacy, clearly mark HOLD at the top of the first page of each piece of your homework; these papers will be held for pick-up in Upson 360.
• Warning: It is unlikely that you will learn the material in the course unless you do the homework. Those who skip a significant number of them are likely to earn poor grades on the exams (as well as receiving a low homework grade).

Prelims and Final

• There will be two evening prelims and a final exam. The dates and times are as follows.
  • Prelim 1: February 24, 2011, 7:30-9 p.m., Baker Laboratory 200.
  • Prelim 2: April 12, 2011, 7:30-9 p.m., Upson B17 / Kimball B11.
  • Final exam: May 20, 2011, 9:00-11:30 a.m., location TBA.

Grading

• Your course grade will be based on homework, two prelims, and a final exam. Each of these three portions of your grade will be given a maximum weight as follows:
  • 30% homework
  • 40% prelims (20% each)
  • 40% final exam.
  For each student, we will determine which of these three components of their grade has the lowest score relative to the class average. The weight of that component will be reduced by 10%, for that student, so that the weights of all three components add up to 100%.
• 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.
• 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.  It's not fair to the graders to ask them to explain details of their grading scheme for an assignment from several weeks ago.  Also, this rule prevents a pileup of such requests at the end of the semester.
• 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 who graded the question. 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.

Academic Integrity

• 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, and you should acknowledge the names of the students with whom you collaborated.
• Cornell's Code of Academic Integrity: http://www.cuinfo.cornell.edu/Academic/AIC.html

Basic Course Data

• Time and Place: Monday, Wednesday, and Friday, 9:05 to 9:55 in Olin Hall 255.

• Course Description (from the Catalog): Techniques used in the creation and analysis of algorithms. Combinatorial algorithms, computational complexity, NP-completeness, and intractable problems.

Prerequisites

• We will assume that everyone has seen the material in CS 2110, 3110, and 2800, and we will use it as necessary in 4820. This includes elementary data structures, sorting, and basic terminology involving graphs (including the concepts of depth-first search and breadth-first search). Some of these are reviewed in the text.
• The lectures and homework involve the analysis of algorithms at a fairly mathematical level. We expect everyone to be comfortable reading and writing proofs at the level of CS 2800.

Text

• Algorithm Design by Jon Kleinberg and Eva Tardos.  This text is available at the Campus Store.
• Note that, although this book was designed for this course, there will be topics covered in lecture that are not in the text and there will be topics in the text that are not covered in lecture.  You are responsible for topics covered in lecture and for any assigned reading in the text.
• 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.

Schedule

• The Schedule lists topics covered in lecture and the corresponding chapters in the text. It includes some prediction of future lectures. This will be updated periodically during the semester.