Randomized Algorithms, Carnegie Mellon: Spring 2011
HW #5 Open Thread
HW5 has been posted; it’s due on Monday April 4th.
Update: for Exercise #2, the expression is indeed correct. (It is and not —you want to show that the solution 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.