Let RANDOM (1, k) be a procedure that draws an integer uniformly at random from [1,...

 

Transcribed Image Text:

Let RANDOM (1, k) be a procedure that draws an integer uniformly at random from [1, k] and returns it. We assume that a call of RANDOM takes O(1) worst-case time. The following recursive algorithm RANDOM-SAMPLE generates a random subset of [1, n] with m < n distinct elements. Prove that RANDOM-SAMPLE returns a subset of [1, n] of size m drawn uniformly at random. RANDOM-SAMPLE(m,n) if m=0 then return else S i← RANDOM(1, n) if i ES then return S = SU {n} else RANDOM-SAMPLE(m-1, n-1) return S = SU {i} end if return S end if Let RANDOM (1, k) be a procedure that draws an integer uniformly at random from [1, k] and returns it. We assume that a call of RANDOM takes O(1) worst-case time. The following recursive algorithm RANDOM-SAMPLE generates a random subset of [1, n] with m < n distinct elements. Prove that RANDOM-SAMPLE returns a subset of [1, n] of size m drawn uniformly at random. RANDOM-SAMPLE(m,n) if m=0 then return else S i← RANDOM(1, n) if i ES then return S = SU {n} else RANDOM-SAMPLE(m-1, n-1) return S = SU {i} end if return S end if

Answer rating: 100% (QA)

The algorithm provided in the image is known as random sampling without replacement To prove that RA... View the full answer