Graduate Algorithms

Homework 3 is now online (pdf, latex). Remember that it is due next Monday, Oct 29.

Some comments:

• In the second problem, you are asked to show that heuristics for a poly-time solvable problem yield 2-approximations. It is not only NP-Complete problems that need approximations. Often, a problem can be solved exactly in polynomial time, but an approximation can be found much faster, and depending on the application, this might be acceptable.
• The final problem is a canonical example of how to prove that the planar version of a problem is NP-Complete: You take the problem, lay it out on the plane, and find some gadget that removes crossings while preserving whatever measure you’re trying to compute. Solving this problem will give you a good idea of how to attack any problem of this kind. A warning though: this problem will take some time, so don’t expect to be able to solve it on Sunday night without spending some time before then !

Update:  I’ve extended the assignment deadline to Oct 31, Wednesday, at 5pm.

The midterm can be found here. Due date is Oct 19 (friday) @ 5pm. LaTeX src (minus the figures: you’ll have to comment those parts out) is here.

Additional notes:

• You may NOT consult your fellow classmates or others. The books are your only friends.
• You may post questions about the midterm as comments on this post. I will be monitoring it frequently.

Today, we’ll cover linear programming, which apart from being one of the most important questions in operations research, is also a tool for generating lower bounds for NP-hard problems automatically. We’ll see how LPs can help us get a(nother) 2-approximation for Vertex Cover.

I’ve updated the class syllabus, populating the remaining lectures with a planned course of study in network flows, randomization, and an assortment of other topics. Also note two important date changes:

1. Homework 3 will now be handed out Oct 22 (rather than Oct 15), since you will all be busy with the midterm. However, the due date will remain the same.
2. The midterm will be two days long, rather than one day. Midterms will be due Friday Oct 19 @ 5pm (electronically or on paper)

Today’s lecture will continue our study of approximations. This time we will consider the travelling salesman problem in metric spaces  (Section 7.7 of these notes), and arbitrarily good approximations for KNAPSACK (KT 11).

In this lecture, we covered the simple 2-approximation for computing the vertex cover. In class, we proved the approximation ratio based on a simple local argument: namely that for each pair of vertices the algorithm chooses, OPT must pick at least one of them. We also looked at the problem of minimizing makespan which has the distinction of yielding one of the very first approximation algorithms, a 2-1/m approximation due to Ron Graham in 1966.

In both of the above cases, we emphasized the need for a lower bound on OPT, so as to reason about the approximation ratio guaranteed by our method. We were able to construct such a lower bound directly by inspection of the input or the algorithm. We then moved onto the problem of SET COVER, where such a lower bound is much harder to come by, and is constructed bit by bit from the steps of the algorithm.

The treatment of the SET COVER analysis in class differs slightly from the textbook. These notes are a useful guide to the method of analysis we used in class.

I’ll be using Chapter 11 from the textbook as a guide for our journey through approximation algorithms. However, I’d like to set the foundations with some basic material that I’ll draw from other sources. Since I don’t have comprehensive lecture notes yet, here are some links, with page numbers to look at:

• Rajeev Motwani’s (old) lecture notes on approximation algorithms. The notes are old, but the fundamentals haven’t really changed. I’ll be drawing on material from Chapter 1 (pages 1-33: the definitions, and the impossibility results).
• Sariel Har-Peled’s notes on approximation algorithms. The relevant material is in pages 1-2 (the greedy approximation algorithm for VERTEX COVER)

Homework 2 consists of problems that are entirely from the textbook. Since many of the problems are rather long and wordy, I thought it better to merely mention the problem numbers, rather than reproducing them in their entirety. However, I know that many of you don’t own the textbook, and use library versions. If you foresee *any* problems in accessing the textbook in order to work on the problems, please let me know as soon as possible, and I can make copies of the problems for you.

Note that the due date is earlier than normal: Oct 5 rather than Oct 8. This is because fall break starts on Oct 6.

The problems are:

1. 4.3 (The UPS problem)
2. 4.9 (Bottleneck spanning trees)
3. 6.1 (Independent sets)
4. 6.6 (Typesetting): This problem dates back to Knuth, who mentions this as one of the problems he faced when designing TeX, (LaTeX is a high-level wrapper for TeX)
5. 6.8 (The Matrix, Reloading…)

Here’s the PDF and LaTeX source for the homework.

Hi all,
I have realized that I didn’t give enough information either in class or in the lecture notes to do the interpolation step (the inverse DFT) correctly, and so I won’t require you to do it. Do complete all the other steps though (evaluation and multiplication). I apologize for the confusion caused by this, and I will explain the problem in Monday’s class.

Hi all,

I hope you’re busy cracking homework 1. I have some comments based on questions people have had.

1. In Q1-3, the recurrence involving T(n/log n), you will quickly find that you get messy expressions like log(n/log n) and so on. It might be useful to recall the trick we used for dealing with floors and ceilings in a recurrence. Namely, rather than trying to find an exact bound for the recurrence, we find two bounds, one lower and one upper, and show that their asymptotic value is the same, yielding a tight $latex \Theta$ bound. Specifically, if we consider the expression log(n/log n), this becomes log n - loglog n. Now this is clearly less than log n, and more importantly, it is also more (in the limit) than 0.9999 log n (or any other constant c < 1 you choose to use). Keep that in mind as you analyze the recurrence.

2. Remember that $latex \log^2{n}=(\log{n})^2$, rather than $latex \log\log{n}$ (log applied twice), which is (occasionally, but rarely) written as $latex \log^{(2)}n$.

3. When I say “show”, you should always mentally translate this as “prove”. This does not mean you’ll lose marks for not writing things out in gory detail. It means you’ll lose marks for missing important steps, or “assuming it’s obvious”.

4. In Q5, the FFT trace, it will be helpful to look at the circuit diagram I described in the notes. You might find that it makes tracing the recursive algorithm a bit easier. Further, I went rather quickly over the inverse DFT operation. Notice that on page 9 of the notes, I show that the coefficients in the inverse DFT ($latex \omega^{-kj}_n$) can be rewritten as $latex \omega^{n-kj}_n$ (this is easy to see if you multiply by $latex \omega^n_n=1$). This means, as I mentioned, that the inverse DFT can be computed by running the DFT algorithm with the reverse of the input vector. But DON’T forget the scale factor of 1/n when computing the inverse DFT (see the first equation on page 9).

The best way to check your answer is to actually multiply the two polynomials using the standard procedure and verify that you get the same answer as the FFT-based method.

5. In Q4, there is some confusion over the desired running time. I’m asking for an algorithm that runs in time $latex o(2^n)$. This means that it has to be STRICTLY better than $latex 2^n$. For example, $latex 1.999^n$ would be an acceptable answer.