Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
473 Homework 5 #1a Pseudocode
GetKSamples(stream S, int k):
samples = list of length k // samples is the list we'll return
for i gets 1...k:
samples[i] = next item in S // Add the first five items in the
// stream to samples
l <- k // Count of things seen so far
while S is not done
x <- next item in S
l <- l+1 // Increment count
if Random(l) <= k // With 5/l probability...
samples[Random(k)] = x // Replace a random item with x
return samples

This comment has been minimized.

Copy link
Owner Author

@chrisshroba chrisshroba commented Mar 7, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.