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.