Design an algorithm to sample k items uniformly at random from a stream of unknown and potentially massive length N, using O(k) memory and one pass. (a) Write the algorithm for k=1 and generalize to k>1. (b) Prove by induction that after processing i items, each seen item has probability k/i to be in the reservoir. (c) Discuss time and memory complexity, and outline how you would adapt it for weighted sampling.