Graduate Algorithms

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.

Wednesday’s lecture will be on the dreaded topic of NP-hardness. Although the concept was first established as recently as 1971, when the Cook-Levin theorem showed the existence of an NP-complete problem, there are innumerable NP-Complete problems lurking out there in the wild, no matter what field of research you go into (let alone in computer science). According to Christos Papadimitrious, 6000 new NP-Completeness results are proved each year. Here are some examples, taken from Kevin Wayne, of NP-Complete problems in the wild. Where possible, I’ve linked to actual documentation of this fact.

• Aerospace engineering: optimal mesh partitioning for finite elements.
• Biology: protein folding.
• Chemical engineering: heat exchanger network synthesis.
• Civil engineering: equilibrium of urban traffic flow.
• Economics: computation of arbitrage in financial markets with friction.
• Electrical engineering: VLSI layout.
• Environmental engineering: optimal placement of contaminant sensors.
• Financial engineering: find minimum risk portfolio of given return.
• Game theory: find Nash equilibrium that maximizes social welfare.
• Genomics: phylogeny reconstruction.
• Mechanical engineering: structure of turbulence in sheared flows.
• Medicine: reconstructing 3-D shape from biplane angiocardiogram.
• Operations research: optimal resource allocation.
• Physics: partition function of 3-D Ising model in statistical mechanics.
• Politics: Shapley-Shubik voting power.
• Pop culture: Minesweeper consistency, and Tetris.
• Statistics: optimal experimental design.

All of which goes to say, it’s important to understand NP-hardness, because the odds are high that you’ll bump into an NP-hard problem sooner rather than later.

Update: Scott’s question in class was: how do we express the operation of sorting as a decision problem in the form described ?

Answer: One way of doing this is to define the language SORT as the set of all pairs ($latex \sigma,\mu$), where $latex \sigma=(x_1,x_2,\ldots{x_n})$, $latex \mu=(y_1,y_2,\ldots{y_n})$, and $latex (\sigma,\mu)$ is in SORT if $latex \mu$ equals $latex \sigma$ in sorted order. Notice that you can check membership in $latex O(n\log{n})$ by sorting $latex \sigma$ in $latex O(n\log{n})$ time and verifying that it equals $latex \mu$ in linear time, but it’s not clear that you can do anything any faster. You can check that $latex \mu$ is sorted in linear time, but how do you check that it contains exactly the same multi-set of elements as $latex \sigma$ ?

On Monday, we’ll cover the various algorithms for computing a minimum spanning tree of a graph. A very nice applet that demonstrates both Prim’s and Kruskal’s algorithm for the MST can be found here.

Note: Monday’s lecture will be in MEB 3147, instead of MEB 3105. This is a one-time shift, only for this Monday’s lecture.

Some useful links:

• A proof of Cayley’s theorem by Edsger Dijkstra.
• Priority queue applet (as implemented via a heap or array)
• The Union Find data structure (two applets)

Slides for today’s lecture are a lightly modified version of Kevin Wayne’s slides (pdf) accompanying the textbook.

Homework 1 is here.The LaTeX source is here.

The due date is Sep 24, 2007.

Homework 0 will be handed out in class. Here are some statistics:

Min: 16

Max: 50

Median: 44

Mean: 41.9

Stddev: 8.75

Overall, people did quite well: marks were lost mainly for small imprecisions, or for carelessness (especially in Q1). I’ll spend a little time talking about the homework during the lecture.

Today’s lecture covered the basics of dynamic programming, from Ch. 6 of KT. We looked at weighted interval scheduling, curve fitting, and SUBSET-SUM, and examined how to obtain solutions via dynamic programming for each of these problems.

The Wikipedia reference article on dynamic programming describes some of the history of the method, as well as providing examples of where it occurs out in the wild. Some of the more well known examples include

• BLAST, the genomic sequence analyzer
• The Viterbi algorithm for calculating likely paths in Markov chains
• The Duckworth/Lewis method for prorating required targets in one-day cricket games when rain intervenes.

The subtlety of why the SUBSET-SUM dynamic program does not run in polynomial time will be addressed in more detail when we cover NP-hardness. Remember though that “n”, the size of the input, is most precisely modelled (at least for complexity-theoretic purposes) as the number of bits needed to write down the input in a “reasonably compact” encoding. I could obviously pad any input string with 0s and 1s to make it seem longer, hence the “reasonably compact” requirement.

For example, consider a graph on n vertices and m edges. Since there are n vertices, we need $latex \log{n}$ bits to describe each vertex, and $latex 2log{n}$ bits to describe each edge. Summing this up, we need a total of $latex n\log{n}+2m\log{n}$ bits, which is $latex O((n+m)\log{n}$. This is what we expect, except for the extra $latex \log{n}$ factor.

It turns out that in “normal” graph algorithms, we cheat a little by assuming that we can perform operations on vertices (like comparing two vertices) in constant time, which would contradict the fact that a vertex representation takes $latex \log{n}$ bits. This is one aspect of the RAM (Random Access Machine) model of computation, where we assume that operations on single cells of memory can be performed in constant time, regardless of the size of the values. What this means is that instead of viewing the space needed by a vertex to be $latex \log{n}$ bits, we can pretend that it uses a constant number of bits, in which case the total number of bits needed to write down a graph reduces to $latex O(n+m)$. For almost all algorithms that we analyze, we implicitly use the RAM model of computation. This has its own problems: we can solve NP-hard problems in polynomial time in a RAM model (!) augmented with bitwise operators, but as long as you aren’t doing bizarre things with bits and encodings of numbers, you’re safe.

Numbers however are trickier. As I explained in class, the space needed to store a value W is $latex \log{W}$, and so any algorithm that takes W as input and runs in time super polynomial in $latex \log{W}$ does not run in polynomial time in the size of the input.