# CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

HW5 has been posted; it’s due on Monday April 4th.

Update: for Exercise #2, the expression $E_{T \gets \mathcal{D}} [\max_{v \in V} d(v, F_T)]$ is indeed correct. (It is $d$ and not $d_T$ —you want to show that the solution $F_T$ found using the tree is lousy when used on the original metric.)

A simpler problem, if you’re stuck, is the furthest pair problem. Here, you are given a metric and want to output a pair of points whose distance is the largest. A natural (yet lousy) algorithm would be: embed the metric into a random tree while maintaining distances in expectation, find a furthest pair in the tree, and output this pair. Show an example where this algorithm sucks.