/Solutions

1. Bureaucratic part

This part you will not be graded on, but you should do it anyway.

Send me email. My address is <aspnes@cs.yale.edu>. In your message, include:

1. Your name.
2. Your status: whether you are an undergraduate, grad student, auditor, etc.

3. Whether you have ever taken a class that used Grade-o-Matic before.¹

4. Anything else you'd like to say.

2. Random sets

Suppose we are given a set of size S, and generate two subsets A and B by including each element of S in A with independent probability p and in B with independent probability q.

1. What is the probability that A⊆B?
2. What are the expected sizes of A, B, A∩B, and A∪B?

3. Recurrences

1. Let T(n) = 1 + T(n-X), where X = 0 with probability p and ⌈n/2⌉ with probability q = 1-p. Give the best upper bound you can on E[T(n)].

2. Let T(n) = n² + T(n-X), where X is a uniformly distributed integer-valued random variable in the range 1..n. Give the best upper bound you can on E[T(n)].

3. Let T(n) = 1 + T(n-X), where the distribution of X depends on n and E[X] = μ(n), where μ satisfies the conditions of the Karp-Upfal-Wigderson bound. Give an example of a family of processes for which the K-U-W bound on E[T(n)] for some n is an arbitrarily large multiple of the actual value of E[T(n)].

4. Random hitting sets

In the hitting set problem, one is given a collection of subsets A₁,A₂...A_k of a set S of n elements, and the goal is to find as small a set B as possible such that A_i∩B≠∅ for all i.

Suppose that |A_i| = m for all i, and that we choose B by including each element of S with independent probability c/m. As a function of n, k, and m, how large does c need to be so that you can show there is at least a constant probability that B∩A_i≠∅ for all i?

You may find it helpful to use the fact that 1+x ≤ e^x for all x.