Introduction to Analysis of Algorithms

CS 4820, Cornell University, Summer 2008

Time, location: MTWRF, 8:30-9:45AM , Upson 207
Instructor & TA: Thành Nguyen .
Email: thanh at cs.cornell.edu
Office hour: 657 Rhodes Hall.
15:30-16:30 on Monday, Wednesday, Thursday.
10:00-11:00 on Tuesday and Friday.
There will be extra office hours before prelims, exam.
Check CMS http://cscms.cit.cornell.edu for HW solutions and grades.
Check www.cam.cornell.edu/~thanh/4820 for:

Announcements HWs, handouts More information

Announcements

Aug 11: Typo in the extra problems. Problem B4, the length of the walk should be at least n-1 instead of n.
Aug 10: The list of extra problems updated!
Aug 7: Please fill out an on-line course evaluation. Thanks!
Aug 7: For the final, there will be questions about approximation algorithms. Some review questions on this topic will be available next week.
Aug 6: A list of extra problems is available. This is also the list of review problems for the final. But you can hand in the solutions for rewards.
Aug 1: Typo in the last problem of review problems. Please download the new file.
Jul 31: List of review problems for Prelims 2 is available.
Jul 30: Find the Longest Path by Daniel Barrett. Lyrics .
Jul 26: HW4 and Prelim 1 graded. Grades and solutions are on CMS.
Jul 23: HW5 is released.
Jul-21: Solutions of Preview Problems are on CMS. Dynamic programming is important. Please read the note online, and read chapter 6.8 for the prelim.
Jul-18: See the list of review problems.
You can get slides of the lectures from CMS.
A link to slides of a similar course.
Jul-11: HW1 is graded, solution and grade is on CMS.
Jul-8: Office hour has been changed.
Jul-7: HW1 is released. See the link in the chedule below. Please read the "note on HW".
Welcome to CS4820 !!!

Schedule, Homeworks and Handouts

See the "Note on Homework" for homework's policy and related information.
The schedule is roughly as below, and will be updated periodically throughout the term.

Monday	Tuesday	Wednesday	Thursday	Friday
Jul 07 Stable matching Read 1.1; Ch2(optional) Information Note on Homework HW1	Jul 08 Some representative Problems Read 1.2; Ch3(optional) A picture	Jul 09 Greedy Algorithm Read 4.1; 4.2 Note: stays ahead Note: exchange argument	Jul 10 Greedy Algorithm Read 4.5 Note: Two proofs for MST HW1 due HW2	Jul 11 Greedy Algorithm Read 4.9
Jul 14 Union-Find data structure (Read 4.6) Divide & Conquer (Read 5.1) HW2 due HW3	Jul 15 Divide & Conquer Read Ch.5	Jul 16 Dynamic Programming Read 6.1. 6.2 Note on dynamic programming Slides Dynamic Programming	Jul 17 Dynamic Programming Read 6.3, 6.4, 6.5 HW3 due HW4	Jul 18 Dynamic Programming Read 6.8 List of review problems Slides on Shortest path
Jul 21 Problem Solving Note on the structure of dynamic programming algorithms HW4 due	Jul 22 PRELIM 1 Matching, Greedy, D&C, Dynamic Prog.	Jul 23 Network Flow Ford-Fulkerson algorithm Read 7.1, 7.2 Slides on Intro to network flows	Jul 24 Network Flow Applications Read 7.5, 7.12 HW5 Slides on Applications of network flows	Jul 25 Network Flow Extensions Note: Maximum weighted perfect matching Read 7.7, 7.13 Slides on extension of network flow
Jul 28 Network flow Applications Read 7.9, 7.11 HW5 due HW6 Slides on more applications of network flows	Jul 29 Polynomial time Reduction, definition of NP 8.1, 8.2, 8.3 Slides on NP-complete	Jul 30 NP-complete problems Guidelines for proving NP completeness 8.4, 8.5, 8.6	Jul 31 NP-complete 8.7, 8.8 HW6 due HW7 Slides on NP-complete	Aug 1 Algorithms on tree, cycle, and other simple structures List of review problems Slides on Special cases
Aug 4 Problem Solving HW7 due	Aug 5 PRELIM 2 Earlier topics + Network flow, NP	Aug 6 Introduction to Approximation algorithms, greedy approach. Read 11.1, 11.2 Slides on intro to approximation algorithms	Aug 7 Approximation algorithm using local search Read 12.1, 12.3,12.4 HW8 Extra problems Slides on local serach	Aug 8 Local search and game theory Read 12.7 Slides on local serach and game theory
Aug 11 Introduction to Randomized Algorithms ThreeBallot Voting System Read 13.1,13.2 HW8 due HW9	Aug 12 Randomized Algorithms Read 13.3, 13.4 Slides on Randomized algorithms	Aug 13 Algorithms, Random, Information, Games	Aug 14 Review Section HW9 due	Aug 15 FINAL EXAM From entire course

Information about the course

Goals

To translate and understand various real world problems in algorithmic languages.
To learn some basic techniques to solve these problems.
To understand what makes a problem hard, but first to learn what it means to be hard with time constraints.
To apply some of the techniques learned before to find approximate solutions when the problems are hard.
To see other types of constraints in real world problems such as lack of a central control, lack of information, and redundancy of information.

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.

Prerequisites

The official prerequisites for the course are CS 280, 312, and 381/481.
We will assume that everyone has seen the material in CS 211, 312, and 280, and we will use it as necessary in 4820. This includes elementary data structures, sorting, big-O notation, and basic terminology involving graphs (including the concepts of depth-first search, breadth-first search, connectivity, and topological sorting). These topics are covered in chapters 2 and 3 of the textbook.
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 280 and 381/481.

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.

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://cscms.cit.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

You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely.
You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you must write up the solutions to each problem set completely on your own. You must also list the names of everyone that you discussed the problem set with.