Algorithms-1 10

Coupon collector problem

Let there be a set of different types of coupons. The goal is to collect all of them. Assuming that each type is equally likely to appear when acquired, what is the expected number of coupons required to collect all of them?

Hitting set

Uniform shuffling

The purpose of uniform shuffling is to take elements of some collection (array) and shuffle them randomly to avoid worst case orderings.

The first algorithm to achieve this is as follows:

The second algorithm relies on a different approach: