# 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:

- Your name.
- Your status: whether you are an undergraduate, grad student, auditor, etc.
Whether you have ever taken a class that used Grade-o-Matic before.

^{1}- 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.

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

# 3. Recurrences

- 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)].
Let T(n) = n

^{2}+ 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)].- 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_{1},A_{2}...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.

Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)