Introduction to Analysis of Algorithms

Cornell University, Spring 2008

Announcements

- Professor Kleinberg's office hours on Tuesday, May 13, will be held in Upson 315.
- Here is some information about the final exam.
- Solutions for problem sets 9 and 10 have been posted on CMS.
- To accompany the lecture given on Wednesday, April 30, here are some notes on online prediction algorithms.
- From Monday, 4/28 to Friday, 5/2, we
will use a modified office hour schedule to provide
extra help before Problem Set 10 is due. Here is
the schedule.
Day Time TA Location Monday, 4/28 11 a.m. - 12 noon Andrew Chan 328 Upson Monday, 4/28 12:15 - 1:15 p.m. Kareem Amin 328 Upson Monday, 4/28 1:15-2:15 p.m. Nikos Karampatziakis 328 Upson Monday, 4/28 3-4 p.m. Kan Li 328 Upson Tuesday, 4/29 11-12 a.m. Bobby Kleinberg 4138 Upson Tuesday, 4/29 12-1 p.m. Rafael Frongillo 328 Upson Tuesday, 4/29 1-2 p.m. Hyungoo Kang 328 Upson Tuesday, 4/29 2-3 p.m. Bobby Kleinberg 4138 Upson Tuesday, 4/29 3-4 p.m. George Panayotov 328 Upson Wednesday, 4/30 2-3 p.m. Bobby Miller 328 Upson Thursday, 5/1 11:30 a.m. - 12 noon Bobby Kleinberg 4138 Upson Thursday, 5/1 1-2 p.m. Chris Estela 328 Upson - Solutions for Prelim 2 are now on CMS.
- Problem Set 10 is due on Wednesday, April 30.
- To accompany the lecture given on Friday, April 25, here are some notes on the Miller-Rabin randomized primality test.
- Problem Set 9 is due on Friday, April 25.
- If you received a score for Problem Set 5, Question 2, but the score doesn't appear in CMS, bring your paper to someone on the course staff so they can re-enter your grade into CMS.

- Add
*cornell.edu*to any incomplete email addresses below.

CS 482 STAFF Name Phone Office Hours Instructor Bobby Kleinberg

rdk2 255-9200 4138 Upson Tues. 11-12 Thurs. 10-11 TAs Kareem Amin kaa32 328 Upson Mon. 12:15-1:15 Andrew Chan ahc35 328 Upson Wed. 11-12 Chris Estela cde8 328 Upson Thurs. 1-2 Rafael Frongillo rmf25 328 Upson Tues. 12-1 Hyungoo Kang hk297 328 Upson Weds. 12-1 Nikos Karampatziakis nk238 328 Upson Wed. 1-2 Kan Li kl342 328 Upson Thurs. 3-4 Bobby Miller rkm23 328 Upson Wed. 2-3 George Panayotov gvp3 328 Upson Thurs. 12-1 Course Administrator Stacey Shirk sbs27 255-0980 4105 Upson

- Broadcast message from the course staff to students
will be sent using
**cs482-l@lists.cs.cornell.edu**. All students should subscribe. - There will be an additional mailing list,
**cs482-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.

- 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 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.**Returning Homework:**Homework will be returned at the end of class (usually) on Friday. 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).

- 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
- 30% prelims (15% 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*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.

- 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, 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.

- 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.

*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*.

- T. Cormen, C. Leiserson, R. Rivest.

- 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.

- The most recent items are listed first