Introduction to Analysis of Algorithms (CS4820)

Cornell University, Summer, 2010.

Annoucements

The course evaluation is online. Please fill out the course evaluation by Thursday 4:00pm. (See instructions in email.)
Clarifications about the final exam (August 11, 2010)

You can assume that Undirected Hamiltonian Cycle, Undirected Hamiltonian Path, and Undirected/Symmetric Travelling Salesman Problem are NP-complete, although we did not prove this fact in class (we only mentioned it in class). That is, you can use them as problems to reduce from in your NP-completeness proofs.

In problem 7 (with numbers and operators), assume that the numbers are positive rational numbers. It does not really matter... we just need to work in a model of computation where addition and multiplication of numbers can be done in polynomial time. But assume that numbers are positive rational numbers for simplicity.

Homework 9 is out. Due on Tuesday, August 10, 2010 at 8:30am (before the class).
We have a review session on 8/4 (Wed) from 2:00 to 3:30. Yogi's office hours for 2-3 on 8/4 are cancelled because of review session.
We are going to have a 24 hours take-home final. You will be able to pick up the final some time on Wednesday afternoon, and return at the same time on Thursday afternoon. Take home final is different from homeworks in the sense that you are not allowed to collaborate with your fellow students on it.
Homework 8 is out. Due on Friday, August 06, 2010 at 8:30 (before the class).
Homework 7 is out. Due on Tuesday, August 03, 2010 at 3:00pm.

The problem 2, part (a) has been changed. Please check the new statement.
In problem 3, part (a), we are supposed to compute the derivatives at x_0, not at x. Also, all n computations together should take O(n) time.

Homework 6 is out. Due on Friday, July 30, 2010 at 8:30 (before the class).
We will have a review session for the prelim on Monday 7/26 3-5pm (instead of Yogi's office hours 3-4).
There are a couple example of step-by-step running of Ford-Fulkerson algorithm on example networks. Here is a simple one, and a more complex one.
There is small handout on max-flow available. This mainly reviews the definitions. Please read this handout with Section 7.1 and 7.2 from the textbook.
Homework 5 is out. Due on Friday, July 23, 2010 at 8:30 (before the class). Note that Problem 2 and 3 require some material from Wednesday's lecture.
Homework 4 is out. Due on Tuesday, July 20, 2010 at 8:30 (before the class).
Homework 3 is out. Due on Friday, July 16, 2010 at 8:30 (before the class).
A handout on finding p_j values for the jobs in Weighted Interval Scheduling.
Homework 2 is out. Due on Tuesday, July 13, 2010 at 8:30 (before the class).
For Thursday July 08, Yogi's office hours will be 12-1 and 5-6 (not 2-3 as they are on Thursdays).
Homework 1 is out. Due on Friday, July 09, 2010 at 8:30 (before the class).
The course information handout (pdf), handed out on 2010-07-05.

Schedule

What we have already covered

We will keep an updated schedule for what has been covered in the course on a lecture by lecture basis.

Dates	Monday	Tuesday	Wednesday	Thursday	Friday
Week of 7/5-7/9	Introduction and stable matching. Reading: Section 1.1. Review: Chapter 2 and 3.	Finished up stable matching. Some representative problems. Reading: Section 1.1 and 1.2 Greedy algorithms. Interval scheduling. Reading: Section 4.1. Homework 1 out. Due on Friday 8:30.	Interval scheduling, and scheduling all intervals. Reading: Section 4.1. Started talking about minimizing lateness. Reading: Section 4.2.	Minimizing lateness. Section 4.2. Minimum spanning tree algorithms. Section 4.5 and 4.6.	Minimum spanning tree, Kruskal, Prim, Union-Find data structure, Clustering of maximum spacing. Reading: Section 4.5, 4.6, 4.7. Homework 2 out. Due on Tuesday at 8:30.
Week of 7/12-7/16	Dynamic programming. Weighted Interval Scheduling and Principles of Dynamic Programming. Reading: Sections 6.1 and 6.2, and the handout on finding p_j values for the jobs in Weighted Interval Scheduling.	Dynamic programming. Segmented least square problem. Sequence alignment. Reading: Section 6.3 and 6.6. Homework 3 is out. Due on Friday before class.	Dynamic programming: RNA secondary structure. Knapsack problem (with values as well as weights). Reading: Section 6.5, 6.4.	Dynamic programming: Shortest paths, Bellman-Ford algorithm. Reading: Section 6.8.	Bellman-Ford algorithm, push and pull variants, Distance Vector Protocol. Reading: Section 6.8 and 6.9. Floyd-Warshall algorithm (not in the book). Have a look at this Wikipedia page.
Week of 7/19-7/23	Network flow Definitions, and preliminaries. Reading: Section 7.1, and handout on max-flow.	Augmenting path algorithm (Ford-Fulkerson), max-flow min-cut theorem. Reading: Section 7.2.	Applications of max-flow. Bipartite matching. Project selection as to maximize the benefit from projects minus the cost of resources. Baseball elimination. Reading: Section 7.5, 7.6, 7.11, 7.12. (Note that the project selection problem we did in lecture was different from the one in Section 7.11.) Also have a look at two example of running of Ford-Fulkerson algorithm: a simple one, and a more complex one.	Application of max-flow, min-cut: Image Segmentation. Extension to max-flow: general demands, and lower bounds on flows. Reading: Section 7.10, 7.7.	Wrap up max-flow min-cut. Survey design Airline scheduling... Start divide and conquer algorithms. Reading: Section 7.8, 7.9, and 5.1.
Week of 7/26-7/30	Divide and conquer. Reading: Section 5.1, 5.2. Review session from 3--5.	Prelim (in class).	Divide-and-Conquer. Finding closest pair of points in the plane. Reading: 5.4.	Divide-and-Conquer. Integer multiplication and Fast Fourier Transform. Reading: 5.5, 5.6.	Turing machines. Definitions. Language of a Turing machine. RE (recursively enumerable). R (recursive). This material is not covered in the book. The instructor can refer you to some books about this material if you are interested. Please talk to the instructor.
Week of 8/2-8/6	Turing machines. Multi-tape and non-deterministic. Turing-recognizability. Turing-decidability.	Diagonalization, non-RE languages, non-recursive languages. NP (non-deterministic polynomial time). P (deterministic polynomial time). Reductions.	NP-completeness. Polynomial time reductions. 3SAT is NP-complete. Independent Set (IS) is NP-complete. 3-dimensional matching (3DM) is NP-complete. Reading: Section 8.1, 8.2, 8.3, 8.6.	NP-completeness. Vertex Cover. 3-Coloring of Graphs. Reading: Sections 8.1, 8.7.	NP-completeness. Travling Salesman Problem and Hamiltonian Cycle. Subset Sum Problem. Reading: Sections 8.5, 8.8.
Week of 8/9-8/13	Cook-Levin Theorem.

Future schedule, tentative

Week 1: Stable matching, greedy algorithms, starting dynamic programming.
Week 2: Finish dynamic programming, divide and conquer.
Week 3: Network flows.
Week 4: Finish network flow, prelim 1, Start NP-compleness.
Week 5: Finish NP-compleness, Turing machine, computability, and start approximation algorithms.
Week 6: Approximation algorithms and randomized algorithms. Final exam.

Staff and office hours

For all emails, add cornell.edu after the @ sign.

Instructor: Yogi Sharma. ys246@

Office hours

Mon: 3--4.
Tue: 10--11.
Wed: 2--3.
Thu: 3--4.
Fri: 10--11.

All office hours are in 328 Upson Hall.

By appointment: Send me an email or talk to me after the class, and I will be very happy to schedule more time.

Consultant: Gautam Kamath: gck43@

Office hours: Mon, Thu: 1--2. In Upson 328.

Notes about office hours

Office hours are there to help you understand the material. If something is not clear, please come to the office hours, or schedule time to meet with us, so that we can go over the difficult parts again. The nature of this course is such that if you don't understand previous parts, it is very hard to keep up. The course builds up on previous material extensively. So, if you are having trouble, the time to ask for help is now, not next week. We will be very happy to spend time helping you learn and understand the wonderful world of algorithms.

Mailing lists

We have two mailing lists.

cs4820-l@cs.cornell.edu: All students should subscribe to this mailing list. Broadcast messages to students will be sent using this list.
cs4820-staff-l@cs.cornell.edu: If you want to contact the course staff, this mailing list is preferable to sending email to individual people.

Lectures

Each lecture will be accompanied by readings, that you are encouraged to read after the lecture. There will be no new material in the readings, but they are very helpful for understanding the material and doing well in homeworks and exams.
We encourage that you try to understand everything in the lectures, and ask questions in case something is not clear. The lectures are there to help you understand, not just to ``cover the material''.

Feedback on the course

If you have any comments about the course, feel free to contact the course staff, and please let us know your comments. We will try our best to make the course most useful and fun for you.

Homeworks

There will be two problem sets each week, one to be handed out on Tuesday and due the Friday three days later, and the second handed out on Friday and due on Tuesday. Homeworks will be handed out at the end of the lecture, and will be due at the start of the lecture.
Please note that we won't entertain late homeworks. Homeworks must be handed out at the start of the lecture on the due date (or earlier). The reason for collecting the homeworks at the start of the class is that we don't want students to distracted doing their homeworks during the lecture.

Overall, there are going to be 9 homeworks.
The homeworks can be submitted either in hard copy (hand written) or soft copy (written preferably in LaTeX).
The homeworks will be returned before the next homework is due. Typically, Friday homeworks will be returned on Monday, and Tuesday homeworks will be returned on Thursday.

Late homework: We don't accept late homeworks, unless some genuine emergency arises. Please contact the instructor in such an emergency arises.
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 by a day or two depending on the situation. The definition of valid excuse will be interpreted to include excessive workload in other classes, travel for academic reasons, personal illness, or other reasons at the instructor's discretion.
Homework privacy: Homeworks are returned back during lecture in a pile. So, homework grades are not private. If you want your homeworks to be returned separately, you must write ``HOLD'' on your homework.
Warning: It is unlikely that you will learn the material without doing the homeworks (especially in this course). 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).

Some thoughts on homeworks in CS4820

Here are some thoughts on how to work on homeworks in CS 4820. These are just guidelines, but in our experience, they have been very helpful for good understanding and doing well in the course.

Assignment are fairly challenging. Start early. Don't wait until the night before.
Generally the assignments will be fairly challenging. It is often helpful to look at the problems early; even if you don't spend a lot of time on them right away, it will help to have the problems stewing in your head for some time!

In particular, it is not a good idea to start the assignment the night before it is due. This course requires slightly different way of approaching the problems, and people tend not to do well under time pressure in such situations.
Whenever you give an algorithm, also provide the proof of correctness.
When questions ask you to ``give an algorithm'' for something, you should also provide a proof of correctness and an analysis of its running time. Unless otherwise specified, when a question asks for an ``efficient algorithm'', we are looking for an algorithm that runs in polynomial time.
Get practice formalizing the problems specified in free text.
You'll notice that some of the questions consist mainly of an English description, without much mathematical notation. This is intentional --- part of the point of the problem sets is to practice formalizing algorithmic problems that are initially described in free text. You can see examples of this process in the book for the course --- the problems considered are initially described informally, then formalized using mathematical notation. You should do the same, defining enough notation to be able to express the problem and its solution carefully, and explaining the meaning of all the notation you use.
A clear English description of algorithm is fine for the class. Psedu-code should be accompanied by English explanation.
Typically, the clearest way to explain an algorithm is in English, with the use of some notation. A clear explanation followed by annotated pseudo-code is also fine. On the other hand, solutions that consist of a long piece of pseudo-code with no accompanying explanation tend to be indecipherable by anyone but the author (and usually indecipherable by the author as well, after a few days). Moreover, our experience is that solutions like this usually turn out to have inaccuracies that render them incorrect. We reserve the right to deduct a significant number of points for solutions that consist only of pseudo-code with no explanation, even if they turn out to be correct. Along these lines, it's in your interest to write up solutions neatly --- this makes it easier to understand what's going on in your solution, and to assign partial credit even if it isn't completely correct.
Use problems at the end of chapters (in textbook) for practice. Feel free to discuss them with us.
There are a number of problems at the end of the chapters in the book. These represent a good way to get more practice solving problems related to the material (for example, to help in studying for the prelim and final). If you do work on any of these problems, we will be happy to discuss your solutions with you in office hours. If you want to use a result claimed in one of these end-of-chapter problems as part of the solution to one of the assigned homework problems for the course, you must include a proof of this result with your solutions. (I.e. you can't simply cite the fact that the question was asked in the book and rely implicitly on the answer. This is, of course, in contrast to the rest of the text, which you should feel free to cite as part of homework solutions.)
Work in groups, but write independently. Never submit any work you don't understand completely.
You are encouraged to work with other students in groups of 3-4 students for coming up with ideas for the homework problems. Please keep the group size small (at most 4). You must write up your solutions completely independently. A good rule of thumb when working in groups is that no one should leave the group meeting with anything written down. Also, you must list the names of the students you worked with on your assignment (there is no penalty for working in groups). Also cite any other source you use to solve the homework problems.

You are not allowed to use the web for finding the answers to the homework or exam questions.

Prelim and final

Prelim: Tuesday, July 27. (In class, open notes and open book).
Final exam: 24 hours take-home final. Wednesday 8/11 to Thursday 8/12.

Grading

Your grade will be based on three components. Homework (50\%), Prelim (25\%), and Final (35\%). And yes, that adds up to more than 100. The worst 10\% component of your score will be dropped.

You will be given some extra points for things like participation in class, filling out course evaluations etc.

Grading Criteria: For the most part, you will be asked to design algorithms for various problems. (No programming assignments.) A complete answer consists of a clear description of an algorithm (a clear 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 (the meaning of ``efficiency'' will be given in class).
We will use CS course management system to manage course grades http://cms.csuglab.cornell.edu/.
Regrade policy: Requests for regrade must be submitted within three (3) days of handing out the graded homework. 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 person 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.

Note that during the regrade process, your solution will be evaluate again completely. So, your score can go up or down.

Academic integrity

Any violation of academic integrity will be severely penalized. (Some examples are: copying in homeworks or exams, submitting solutions that you don't understand.) You are allowed (and even encouraged) 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 (and any other sources you used).

As a general rule, you should be able to explain orally to a member of the course staff what you write in your solutions. Please don't submit anything that you don't understand.

Cornell's Code of Academic Integrity: Code of Academic Integrity.

Basic course information

Time and place: Monday through Friday 8:30 to 9:45 in Upson 207.
Course description (from Courses of Study 2009-2010): Develops techniques used in the design and analysis of algorithms, with an emphasis on problems arising in computing applications. Example applications are drawn from systems and networks, artificial intelligence, computer vision, data mining, and computational biology. This course covers four major algorithm design techniques (greedy algorithms, divide-and-conquer, dynamic programming, and network flow), computability theory focusing on undecidability, computational complexity focusing on NP-completeness, and algorithmic techniques for intractable problems (including identification of structured special cases, approximation algorithms, and local search heuristics).

Prerequisites

The official prerequisites for the course are CS 280/2800 and 312/3110.

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

The official text for the course is:

Algorithm Design by Jon Kleinberg and Eva Tardos.

This text is available at the Campus Store. Two copies are also on researve in the Engineering Library.

We will cover some topics that are outside of the book, and we will not cover all the topics in the book.

Other reference books that might be useful for some topics:

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. (On reserve in Engineering Library.)
A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Algorithms.
M. Garey and D. Johnson. Computers and Intractability.
D. Kozen. The Design and Analysis of Algorithms.
M. Sipser. Introduction to the Theory of Computation.