Reservoir sampling is a family of algorithms used to randomly select k items from a population of unknown size n. It requires only one pass over the population and does not require all n items to fit into main memory. The algorithm cannot look back at previous items, but must be able to extract a random sample without replacement at any point.
Stanford University
Fall 2022
This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required.
No concepts data
+ 37 more concepts