Homework #0

Due in class Thu, Sep 1. Please do this HW entirely on your own.

  1. Given a set \{1,2,...,n\} and a symmetric distance function d(i,j) between any pair of them (any distance function induces a metric, i.e., the distances satisfy the triangle inequality), consider the following clustering algorithm:
  • Select any point x_1 from the set.
  • For i=2 to k:
    • Find the farthest point to the currently selected set of points, i.e., the point j whose distance to the nearest of x_1, \ldots, x_{i-1} is largest (break ties arbitrarily); call it x_i.
    • Output the set x_1,\ldots,x_k.

Let the radius r be the maximum distance of any of the n points to the nearest of the k points output. Show that the greedy algorithm above finds a solution whose radius r is at most twice that of the minimum radius, i.e., minimum among all possible choices of subsets of k points from the given set.

2. Write a Boolean function (using only Boolean functions that take one or two bits as input and produce a single bit as output, e.g., AND, OR, NOT etc.) that takes as input two n-bit binary numbers and outputs 1 if the first number is at least as large as the second and 0 otherwise.

3. There are two TV channels in Whethertown that all predict whether it will rain the next day. Your strategy to decide if it will rain tomorrow is the following: you keep a table of both channels’ predictions each day and go with the prediction of the channel that has made the fewest wrong predictions so far. Show that this strategy can lead to nearly twice as many wrong predictions for you as the better of the two channels over time.