In this problem, we will combine ideas from Count- min sketch for finding heavy-hitters with the Alon-Matias-Szegedy algorithm for estimating the 2 frequency moment of a stream. This will allow us to estimate heavy hitters of a stream with a tighter guarantee in certain cases. Recall that in Count-Min Sketch, we maintained d hash functions h,..., hd, corresponding to d hash tables, each of size w. For the datum that appears at time t, (it, ct) where it is the identifier, and ct is a count, for each j = [d], we increment a counter C; in entry h; (it) of the jth hash table by c. At the end of the stream, for a given identifier i, we can return fi = minjeld] C; (h; (i)) to get an estimate of fi - Etiti. In particular, setting w = 0(1/E) and d = O(log(1/8)), with probability at least 1-8, this will give an estimate fi - fil < F, where F = fi (we assume that fi 20 for all i). Consider making the following changes to the algorithm. Instead of storing just d hash functions, we instead store 2d hash functions. The second set of hash functions, 91,..., 9d maps to the range {+1}. The modification to counter C; at time t is still at entry h; (it), but now we increment it by gj(it)ct. Finally, our estimate fi is now median jeld] 95 (i)C; (h; (i)). We will obtain a guarantee which is in terms of VF2, where F = f. Let fij = 9; (i)C,(h, (i)). (a) For some given i and j, compute E[fi]. (b) For some given i and j, upper bound Var[fij]. (c) Given these two quantities, choose values of d and w, upper-bounding the probability that fij-fil 22 by a constant, and (in turn) upper-bounding the probability that fi - fil EVF by 8. (d) Compare this type of guarantee with that of Count-Min Sketch. When is each guarantee better? Give a set of frequencies (i.e., a set of fi's) illustrating where one might be better than the other.