Simple, Optimal Algorithms for RandomSampling Without Replacement

Description: 

Consider the fundamental problem of drawing a simple random sample (SRS) of size k without replacement from [n] := {1, . . . , n}. Although a number ofclassical algorithms exist for this problem, we construct algorithms that are even simpler, easier to implement, and have optimal space and time complexity.

Authors: 
Daniel Ting
Publication Date: 
Sunday, April 11, 2021
Publication Information: 
Arxiv