CS 6550, Design and Analysis of Algorithms
Homework 2
Thu, Feb 9, 2012 Due Thu, Feb 16, 2012
Problem 1: -Coupon Collection
Consider the usual coupon collecting process, where there are n types of coupons. Where T is
the random variable denoting the first time when all n types of coupons have been collected, we
showed that E [T] = O(n log n). Let , 0 < < 1, be a constant and let T be a random variable
denoting the first time when at least n types of coupons have been collected. Show that, for some
constant c = c(), E [T] ≤ cn = O(n). (Ie, you can collect 90%, 99%, 99.9%, etc of the coupons in linear
time; it is the last “few” ones that cause the log n factor in (all) coupon collection.)
Problem 2: -close to Median
Suppose that you are presented with a very large set S of real numbers and you’d like to approximate the median of these numbers by sampling. You may assume that all numbers in S are
distinct. Let n=jSj. W
The post CS 6550, Design and Analysis of Algorithms appeared first on Assignment Freelancers.