In this problem, you will modify the CountMin algorithm so that it obtains a different guarantee, which s better in certain cases. For example, if the frequency vector is f=(1,1,11)+nei (where ei is the ith basis vector), then, to detect that item i has frequency n+1, the CountMin algorithm would need space (n). The new algorithm will instead use space O(logn) only. 2 We build one array S[1w] as follows, using a random hash function h:[n][w] (as before), as well as a random hash function :[n]{1,+1}. Then S[i]=x:h(x)=i(x)fx. Note that the only lifference is the use of random signs (which is similar to the Tug-of-War). a) Prove that, for any x[n], with probability at least 90%, we have that S[h(x)](x)fx O(f2/w). Hint: for a 0 -mean variable X, one can bound X by bounding X2 instead. b) Now suppose we take L=O(logn) such arrays S1,SL, each of size w, and each with iid hash functions hi:[n][w],i:[n]{1,+1}, where i[L]. Define the estimator f^x for fx as f^x=mediani[L]Si[hi(x)]i(x). Prove that, for any fixed x[n], with probability at least 112, we have that f^xfxf2, for some w=O(21)3 Hint: you can use the following central limit theorem (Chernoff bound): for iid random variables X1,Xk[0,1] with X=E[iXi], we have that Pr[iXiXk]eck2 for some constant c>0. c) Show that in the above example, the space required by the modified CountMin to find the entry i where fi=n+1 is only O(logn). d) Now consider a slightly different query/setting than the standard heavy hitter query for the entire stream. Assume the stream is composed of items i1,i2,im[n]. For time stamp t[m], let S(t)=(S1(t),SL(t)) be the values stored in the arrays S1,SL after seeing items i1it only. (E.g., note that S(t) is obtained from S(t1) via updates Sj(t)[hj(it)]=Sj(t1)[hj(it)]+j(it) for all j[L]). Now suppose we have stored a sketch S(t) at some time t