Introduction to Analysis of Algorithms

Computer Science 482
Summer 2007

Announcements

• The final exams have been graded and final course grades have been determined.  Final exam scores and course grades are available on CMS.
• The final exam was apparently a difficult exam (the highest score was 70).  In determining final grades, the final exam scores were modified.  In effect, 20 points were added to each exam score.
• The final exam takes place on the last day of class, Friday, Aug 17.  The exam takes place in our regular classroom.  The exam begins at our regular class time (8:30AM) and ends at 11:00. 
• Review Problems for the Final Exam are now available
• HW09 (the last one!) is due Wednesday, Aug 15
• HW08 due date has been changed to Monday, Aug 13.  The last problem was mistyped as Problem 9, Chapter 11, but the correct problem is Problem 10, Chapter 11.
• HW08 is due Friday, Aug 10
• Prelim Two has been graded and will be returned during Wednesday's class.  The solution key for Prelim Two has been posted to CMS; it appears as part of the Prelim Two "assignment".
• As announced in Thursday's class, Paul Chew's office hour for Friday, Aug 3, has been cancelled
• Another guide from a previous course incarnation: Guidelines for Proving NP-Completeness
• HW07 was due Thursday, Aug 2, but this has been changed to Friday, Aug 3
• HW06 is due Tuesday, Jul 31
• The solution key for Prelim One has been posted to CMS; it appears as part of the Prelim One "assignment"
• HW05 is due Friday, Jul 27
• Our first prelim takes place on Tuesday, July 24; you may find it useful to look at Review Problems for Prelim One
• HW04 is due Friday, Jul 20
• This is another guide produced for a previous incarnation of the course: Guidelines for using Dynamic Programming
• HW03 is due Wednesday, Jul 18
• This is another guide produced for a previous incarnation of the course: Guidelines for Proving Correctness of Greedy Algorithms via an Exchange Argument
• The solution for HW01 has been placed on CMS (as a file under the HW01 assignment)
• HW01 has been graded and the grades are available on CMS
• This is a guide produced for a previous incarnation of the course: Guidelines for Proving Correctness of Greedy Algorithms via Greedy Stays Ahead
• HW02 is due Monday, Jul 16
• Office hours have been moved so that they're more accessible (hours are now 10:45 - 11:45)
• HW01 is due Thursday, Jul 12
• Schedule for exams (this information is also in the Schedule)
  • Prelim I: in class on Tuesday, Jul 24
  • Prelim II: in class on Tuesday, Aug 7
  • Final Exam: Friday, Aug 17 (last day of class)
• Announcements are posted on the website; it's a good idea to check the Announcements often

Basic Course Data

• Time and Place: Monday through Friday, 8:30 - 9:45 AM, Hollister Hall 312 (Jul 9 through Aug 17).

• 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 211, 312, and 280, and we will use it as necessary in 482. 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 using mathematical proofs. We expect everyone to be comfortable reading and writing proofs at the level of CS 280.

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.

Staff and Office Hours

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

CS 482 STAFF	Name	Email	Phone	Office	Office Hours
Instructor	Paul Chew	chew@cs.	255-9217	494 Rhodes	M-F 10:45 - 11:45
Course Administrator	Kelly Patwell	patwell@cs.	255-7790	5147 Upson

Communication

• Course Web Site: http://www.cs.cornell.edu/Courses/cs482/
  Check the website often.  This is the central repository for all the information available about the course including the latest homework assignment, scheduling changes, and important announcements.
• Office Hours: See above table.
• Email: Questions about the course can be emailed to the instructor or the Course Administrator.  Questions about the homework can be emailed to the instructor.
• Appointments: The best way to set up an appointment is via email.

Homework

• Problem sets are due approximately every other lecture.  The summer session moves fast --- it's a good idea to start on your homework as soon as you can.
• Late Homework Policy: It is expected that homework will be turned in in class and on time. Late homework will not be be accepted except in emergency situations.  If a genuine emergency situation exists you must inform the Instructor or the Course Administrator as soon as possible.
• Returning Homework: Homework will be returned in class. The current plan is to return it on the day after it was turned in.
• 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.  Note that homework makes up a significant portion of your final course grade.

Homework	Topic	Due Date	Solution Status
HW01	Stable Matching	Thursday, Jul 12	solution available on CMS
HW02	Graph Algorithms Greedy Algorithms	Monday, Jul 16	solution available on CMS
HW03	Divide & Conquer Dynamic Programming	Wednesday, Jul 18	solution available on CMS
HW04	Dynamic Programming	Friday, Jul 20	solution available on CMS
HW05	Network Flow	Friday, Jul 27	solution available on CMS
HW06	More Network Flow	Tuesday, Jul 31	solution available on CMS
HW07	NP-Completeness	Friday, Aug 3	solution available on CMS
HW08	NP-Completeness: Special Cases & Approximations	Monday, Aug 13	solution available on CMS
HW09	Randomized Algorithms	Wednesday, Aug 15	solution available on CMS

Grading

• Your course grade will be based on homework, two prelims, and a final exam. Weighting will be roughly as follows:
  • 30% homework
  • 40% prelims (20% each)
  • 30% final exam
• 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 three lectures of the time that homework or exams are returned to the class.  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 instructor. Note that we're talking here about correct work that was 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. 
• For this course, we encourage students to discuss the course content, including homework. Generally, discussing an algorithm or approach is acceptable. As a rule of thumb for such cooperation, try not to write anything down. Cooperation should never involve a student possessing a copy of all, or a portion of, someone else's work, regardless of format. You are expected to write up (and understand) the homework on your own.
• Computer Science Department Policy on Academic Integrity: http://www.cs.cornell.edu/degreeprogs/ugrad/CSMajor/index.htm
• Cornell's Code of Academic Integrity: http://www.cuinfo.cornell.edu/Academic/AIC.html
• If you are unsure about any questions of academic integrity, please ask.

Schedule

• The Schedule lists topics covered in lecture and the corresponding reading in the text. It also includes rough predictions of future lectures. This will be updated periodically during the semester.

Items Placed on the Web

• Review Problems for the Final Exam
• HW09
• HW08
• Review Problems for Prelim Two
• Guidelines for Proving NP-Completeness
• HW07
• HW06
• HW05
• Review Problems for Prelim One
• HW04
• Guidelines for using Dynamic Programming
• HW03
• Guidelines for Proving Correctness of Greedy Algorithms via an Exchange Argument
• Guidelines for Proving Correctness of Greedy Algorithms via Greedy Stays Ahead
• HW02
• HW01
• This list is updated during the semester; the most recently added items are listed first