(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 01 and 02. Let 010 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(o).z. Given two data streams o, and 02, let f(01) and f(02) 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(Q1 o 02) from f(a) and f(02) (i.e. how to set f(01 002).2) so that the ouptut 25(01002).z+1/2 would be an (O(1), 2/3)-estimate for 010 02. 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:20 4: B4 Process (token j): 5: if zeros(h()) > z then B+-BU{ zeros(h(t))} 7: while Bc/e? do 2+2+1 shrink B by removing all (a,b) with B z then B+-BU{ zeros(h(t))} 7: while Bc/e? do 2+2+1 shrink B by removing all (a,b) with B