1. (2 points) Many sketching algorithms are very useful because they are mergeable. In this problem, you will investigate how to merge the sketches produced by the distinct element algorithms. (a) Suppose there are two streams g; and 02. Let 01 02 denote the concantenation of two streams. Let f (o) denote the sketch after we run the algorithm on the stream o. In the tidemark algorithm, the sketch contains an integer f(a).. Given two data streams 01 and 02, let f(01) and f(2) be the sketches produced by the tidemark algorithm. Assume that the tidemark algorithm are using the same hash function (chosen from a 2-universal family) for the two streams. Describe how to construct the sketch f (01 002) from f(01) and f(02) (i.e. how to set f(01 002).2) so that the ouptut 2(01009).3+1/2 would be an (0(1), V2/3)-estimate for 01 002. You do not have to analyze your algorithm. Figure 1: Algorithm The BJKST algorithm for DISTINCT-ELEMENTS Initialize: 1: Choose a random hash function h: N N from a 2-universal family 3:270 4: B Process (token j): S: if zeros(h(:)) > z then 6 BBU{ i zeros(h(i))} 7: while B c/e do 8: 2+2+1 9 shrink B by removing all (a,) with B z then 6 BBU{ i zeros(h(i))} 7: while B c/e do 8: 2+2+1 9 shrink B by removing all (a,) with B