Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a stream a of m items, where m is either very large or unknown until the list is traversed. (Google if this term/concept is new to you) Suppose we used reservoir sampling on a stream 01 of length m1 and stored a k-sample (with replacement) 51. We also used reservoir sampling on another stream 02 of length m2 and stored a k-sample (with replacement) $2. a) Show how you can use reservoir sampling to obtain a k-sample (with replacement) 5 for the concatenated stream a = 01 - 02 from $1 and 52 in 0(k) space. Please give a formal description for your algorithm (pseudo-code or better) and prove that your algorithm does indeed randomly sample (uniformly) from the concatenated stream. b) Generalize for the concatenation of h streams 01, 02, . . . , ah of lengths m1, m2, . . . , mh and associated k-samples Si, 52, . . . , Sh in 0(hk) space. Please give a formal description (pseudo-code or better) for your algorithm and prove that your algorithm does indeed randomly sample (uniformly) from the concatenated stream