1. Bureaucratic part
This part you will not be graded on, but you should do it anyway.
Send me email. My address is <firstname.lastname@example.org>. 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?
- 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) = n2 + 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 A1,A2...Ak of a set S of n elements, and the goal is to find as small a set B as possible such that Ai∩B≠∅ for all i.
Suppose that |Ai| = 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∩Ai≠∅ for all i?
You may find it helpful to use the fact that 1+x ≤ ex for all x.
Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)