CMU Randomized Algorithms

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 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.


2 responses to “HW #5 Open Thread

  1. Kevin March 24, 2011 at 3:54 am

    In Problem 2, parts b and c, what is F_2? Also, what is ||x||_2? The magnitude of the vector x should just be D, right? Thanks in advance!

  2. cmurandomized March 24, 2011 at 10:31 am

    F_2 is defined to be \sum_i x_i^2. And ||x||_2 = sqrt(F_2), which is also the Euclidean length of the vector x.

    x is a vector in R^D, and the sum of the entries in x is the total number of elements you have seen in the stream. This is the same object we saw in the J-L lecture—it may be useful to check out the notes for that lecture.

%d bloggers like this: