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.
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.
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.
In the G(n,p) model of random graphs, what is the probability that a given pair of vertices are not tight?
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.)
What is the expected number of edges in a random graph with this probability?
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?