[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


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.1

  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) = 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)].

  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 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.

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

2014-06-17 11:58