473 Homework 5 #1a Pseudocode

pseudocode.py

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

Python code with testing: https://gist.github.com/chrisshroba/2f94fc85b8f14d0a137c