CS 263, Spring 2014, Homework 2

Due at the start of class, Thursday, April 17

  1. [Mitzenmacher and Upfal 3.8]

    Suppose that algorithm A chooses a single random number in the range from 1 to n and then performs a computation that, if all choices are equally likely, takes expected time O(n2). What can you say about the worst-case time for algorithm A?

    Hint: use Markov's inequality.

  2. [Mitzenmacher and Upfal 3.21]

    Let p be a random permutation of n items, with all permutations equally likely. What is the probability that item i is mapped to itself by permutation p? Use your answer and linearity of expectation to compute E[X] where X is the number of items that are mapped to themselves.

  3. Define a graph to be "tight" if every two vertices are either adjacent or connected by a path of length two (or both). We wish to find the threshold probability that determines whether a random graph is tight.

    1. In the G(n,p) model of random graphs, what is the probability that a given pair of vertices are not tight?

    2. Approximately how large does p need to be to ensure that with constant probability the whole graph is tight? (Apply Markov's inequality to the expected number of non-tight pairs.)

    3. What is the expected number of edges in a random graph with this probability?

  4. We saw in class that if n balls each choose the less full of two random bins, from a set of B bins, then:

    The aim of this problem is to interpolate between those two results.

    Recall the following facts:

    Now suppose that n is significantly smaller than B. Calculate (in terms of n and B) the expected number of components of G that have at least one edge, the expected number of components that have at least two edges, etc. Use Markov's inequality to find the maximum value c such that there is constant probability of having a component of size at least c. What does this bound on component size, together with the complete binary tree argument, imply about the maximum number of balls per bin?