HW5 posted

We know Homework 4 is not due until Monday, but we thought we could give you a bit more time to enjoy Homework 5 (link here). Most problems have a (relatively) short and simple solution, which means that you should talk to us if your solutions appear to be ungodly long and difficult.

The Mysteries of Algorithms

If you want to take a break from homework, research, etc, or want to hear a talk about algorithms intended for the general audience, today CMU is presenting the 2008 Dickson Prize in Science to Professor Richard M. Karp, one of the world's most renowned computer science theorists. Professor Karp will give a lecture titled "The Mysteries of Algorithms" after the award presentation.

Details follow....

---

Dickson Prize in Science
Honoring Dr. Richard M. Karp
Wednesday, March 25, 2009
4:30 p.m.
Following the award presentation, Dr. Karp will present his lecture titled ?The Mysteries of Algorithms.?

McConomy Auditorium, first floor, University Center

A reception will immediately follow in Rangos 1 and 2, second floor, University Center.
These events are free and open to the public.

For more information, please visit www.cmu.edu/dickson-prize.

If you have any questions, please contact the Office of University Events at 412-268-5052 or events@andrew.cmu.edu.

Office hours this week

Hi everyone,

I will be out of town from Thursday to Sunday this week, so I need to cancel my Friday office hours. If anyone has any questions feel free to email me, or come to my Wednesday office hours.

Corrections and Mega Hints

Thanks Andrea, Stephanie, and Tony for pointing out typos -- sorry for the confusion.

Problem 1:
In part b, the previous hint doesn't quite lead you to the goal. Sorry about that. Here's an updated version. Play with Farkas's lemma using the following matrix/vector: Let $A'$ be obtained by appending $-b^T$ to the rows of the matrix $A^T$, where $A$ and $b$ come from the primal program, and let $b'$ be obtained by appending $-z$ to the original vector $c$. Here $z$ is the value of the optimal primal program. That is,

$A' = \left(\begin{array}{c} A^T \\ -b^T \end{array}\right)$ and $b' = \left(\begin{array}{c} c \\ -z \end{array}\right)$.

Then argue along this line. If the first clause of Farkars holds, then we are set. So suppose for a contradiction that it does not, then it must be the case that the second clause holds. Derive a contradiction. The following template might be useful: by clause (2) of Farkas, we know that $Ax - \lambda b = 0$, $c^Tx - \lambda z < 0$, and $x \geq 0$, where
$y = \left(\begin{array}{c} x \\ \lambda \end{array}\right).$ Case 1: if $\lambda = 0$, derive a contradiction. Case 2: if $\lambda > 0$, what happens then?

Problem 2:
See the previous hint for part a). For part b), it suffices to look at the following primal:

Minimize 0
Subject to $\piP = \pi$, $\sum_i \pi_i = 1$, and $\pi_i \geq 0$.

There is a trivial solution for the dual. You will also want to show that the dual program is bounded. This is trickier, but we won't deduct points if you don't do it.

Problem 3:
In part a), every $\alpha$ is a $\delta$. You should look up universal hashing. Even though you may be able to avoid hashing of any kind for this part, it will be useful to know for later parts that hashing can be supported in constant expected amortized time per operation. For part b), 9 is clearly not the best one can do. But obviously, if you can prove it for 4, it automatically implies 9. Sorry if this confuses you---we were just trying to give you some wiggle room.

For part c), think about an incremental construction--it will help you in part d). For even more suggestions, suppose you have an incremental algorithm, where you "bucket" the given points into a $\delta$ by $\delta$ grid. If a new point comes in,
you find the bucket it should belong to. What can you say if there are more than $4$ (or $9$) points in that bucket already? If there are fewer than $4$, what do you do? The $X$ there was a typo--it should be $A$.

In the last part, try inserting points in a random order, just like what we did in incremental 2d convex hull. What is the probability that your new point is going to decrease the distance between the current closest pair? (Answer: $2/i$ for the $i$-th point).

Problem 4:
The main idea is max-flow and the max-flow min-cut theorem. To answer some question from office hours, it is okay even if your construction of graph only gives edge-disjoint paths: it's a byproduct and it doesn't hurt your solution.

For starters, make $r$ your source, create a new sink $t$, and link all the terminals to $t$, all with edge capacity $1$. Can you express an (s,t)-cut value in terms of the number of terminals, the number of real edges you cut, and the number of fake edges you cut? How does it relate to the objective function in this problem? How do you find a min-cut?

Problem 5:
You only need two applications of max-flow.

Typos in HW3

Andrea Qualizza found two typos in HW3. Thanks Andrea!

1b) In the second part of Farkas's Lemma, every entry of y has to be at least zero

2a) For the extra credit, the full statement isn't actually correct. The correct statement is that $\max_p \min_q p^T M q = \min_q \max_p p^T M q$

Sorry for the confusion.

Kanat's Office Hours

Kanat has to cancel his Monday office hours for this week, but he will hold extra office hours on Tuesday from 3 to 4pm.

Homework 3 Hints

We hope the following hints will let you have more time to enjoy the spring break.

1. Problem 1b. You are given the Farkas's lemma for free. To use it, you should realize that the matrix $A$ and the vector $b$ that appear in the statement of the lemma need not be the same $A$ and $b$ that show up in the primal or dual program. In fact, you might want to play with Farkas's lemma using the following matrix/vector: Let $A'$ be obtained by appending $c^T$ to the rows of the matrix $A$ of the primal program, and let $b'$ be obtained by appending $z$, the value of the optimal primal program, to the original vector $b$. That is,
   
   
   $A' = \left(\begin{array}{c} A \\ c^T \end{array}\right)$ and $b' = \left(\begin{array}{c} b \\ z \end{array}\right)$.
   
   
   
2. Problem 2a. We will solve a seemingly unrelated problem for you. Suppose have linear functions $f(x)$, $g(x)$, and $h(x)$, where $x$ here is a vector, say, $x = (x_1, x_2, ..., x_n)$. What we want to do is to write the following problem as an LP:
   

   
   maximize $\min \{3f(x), 4g(x), 2h(x)\}$
   subject to $f(x) \geq 0, g(x) \geq 0, h(x) \geq 0$, and $x\geq 0$.
   

   
   How? We introduce a new variable $\lambda$ and enforce the constraints $\lambda \leq 3f(x)$, $\lambda \leq 4g(x)$, and $\lambda \leq 2h(x)$. The LP should look like:
   

   
   maximize $\lambda$
   subject to $f(x) \geq 0, g(x) \geq 0, h(x) \geq 0$, $\lambda \leq 3f(x)$, $\lambda \leq 4g(x)$, $\lambda \leq 2h(x)$, and $x\geq 0$.
   

   
   This is a trick that will be helpful for solving 2a.