# CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

## HW #5 Open Thread

March 21, 2011

Posted by on 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.

Advertisements

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!

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.