Introduction to Analysis of Algorithms

Computer Science 482
Spring 2007

Announcements

• Solutions for the Review Problems for the Final Exam are available on CMS under the Final Exam "assignment"
• Final Exam Review Session: Tuesday, May 15, 4:30-5:30 in Upson B17
• There are some changes to Office Hours during finals week
• Final Exam:
  • The CS482 Final Exam takes place 9:00 - 11:30 am on Thursday, May 17, in Hollister B14
  • Review Problems for the Final Exam are now available
  • There will be a Review Session for the Final Exam on Tuesday, May 15; the room and time will be posted as soon as this information is known
  • Office hours will continue until the Final Exam; necessary changes (due to a TA having a final exam, for instance) will be posted here as soon as the information is available
• The Schedule has been updated to show all the lecture topics and the corresponding sections in the text for the entire semester
• Link to old announcements...

Staff and Office Hours

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

CS 482 STAFF	Name	Email	Phone	Office
Instructor	Paul Chew	chew@cs.	255-9217	494 Rhodes
TAs	Kareem Amin	kaa32@
	Gregor Carrigan	gcc26@
	Liwei Chen	lc276@
	Rodney Eng	rpe7@
	Huijia (Rachel) Lin	huijia@cs.
	Zach Scherr	zls2@
	Andrew Tibbits	aht9@
	Ymir Vigfusson	ymir@cs.		4143 Uposn
	Benjamin Weber	bhw7@
Course Administrator	Kelly Patwell	patwell@cs.	255-7790	5147 Upson

• Office hours are listed below. You can also use any of the communication methods suggested below.

Office/Consulting Hours	Where	Who
Monday, 12:20 - 1:20 cancelled 5/14 Finals week: Wednesday, 3:00-4:00	328D Upson	Gregor Carrigan
Monday, 1:30-2:30	328C Upson	Andrew Tibbits
Monday, 3:30-4:30 cancelled 5/14 Finals week: Wednesday, 1:00-2:00	328D Upson	Liwei Chen
Monday, 4:00-5:00	328B Upson	Benjamin Weber
Tuesday, 3:00-4:00	328D Upson	Rodney Eng
Tuesday 5:30-6:30	328 Upson	Zach Scherr
Wednesday 6:00-7:00	328D Upson	Kareem Amin
Thursday, 11:00 - 12:00 Finals week: Wednesday, 10:00-11:00	328D Upson	Ymir Vigfusson
Monday, 2:00 - 3:00 cancelled 5/14 Tuesday, 2:00 - 3:00	494 Rhodes	Paul Chew
Friday, 4:00-5:00	328D Upson	Huijia (Rachel) Lin

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.
• Course Newsgroup: cornell.class.cs482
  This group is monitored by the course staff and is intended for both questions and discussion.  This is likely to be the quickest way to get a question answered.  Please do not post homework solutions or partial solutions.
• Office Hours: Hours will be announced in class and posted on the course web site as soon as they are determined.
• Email: Questions about the course can be emailed to any of the course staff.
• Appointments: You can make an appointment with any member of the course staff. The best way to set up an appointment is via email.

Homework

• There will be weekly problem sets, due in class (usually) on Friday.
• 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 course staff as soon as possible.
• Submitting Homework: To simplify the process of distributing papers for grading, each homework will consist of 3 parts (A, B, and C).  Each part must be turned in separately.  In other words, each of parts A, B, and C will be placed in separate piles when homework is handed in on Friday.
• Returning Homework: Homework will be returned at the end of class (usually) on Wednesday. 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 (A, B, and C) of your homework; I will hold these papers for pick-up during my office hours.
• 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).

Homework	Topic	Due Date	Solution Status
HW01	Stable Matching + Review	Friday, Feb 2	available on CMS
HW02	Divide & Conquer; Dynamic Programming	Wednesday, Feb 14	available on CMS
HW03	Dynamic Programming; Greedy Algorithms	Wednesday, Feb 21	available on CMS
HW04	Network Flow	Wednesday, Mar 7	available on CMS
HW05	More Network Flow	Wednesday, Mar 14	available on CMS
HW06	NP-Completeness	Wednesday, Mar 28	available on CMS
HW07	More NP-Completeness	Wednesday, Apr 4	available on CMS
HW08	Solving/Approximating NP-Complete Problems	Wednesday, Apr 18	available on CMS
HW09	Approximating NP-Complete Problems	Wednesday, Apr 25	available on CMS
HW10	Randomized Algorithms	Wednesday, May 2	available on CMS

Grading

• Your course grade will be based on homework (due each Friday), two prelims, and a final exam. Weighting will be roughly as follows:
  • 40% homework
  • 36% prelims (18% each)
  • 24% 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 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.
• 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 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 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 at a fairly mathematical level. 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.

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.

Items Placed on the Web

• Review Problems for the Final Exam
• HW10
• HW09
• HW08
• Review Problems for Prelim Two
• HW07
• Guidelines for Proving NP-Completeness
• HW06
• HW05
• HW04
• Guidelines for using Dynamic Programming
• Guidelines for Proving Correctness of Greedy Algorithms via Greedy Stays Ahead
• Guidelines for Proving Correctness of Greedy Algorithms via an Exchange Argument
• Review Problems for Prelim One
• HW03
• HW02
• HW01
• The most recent items are listed first