Read about "Morris's Algorithm of Counting\" before attempting Counting the Number of tokens in a stream It is trivial to see that if there are m tokens in the stream, then [(032m) many bits suffice to keep track of the number of tokens. Now consider the following randomized algorithm. Probabilistic Counting: LetX 0. For this part, we consider an alternate (and somewhat more elegant) way of modifying the basic estimator1 to achieve better estimates. Suppose you modify the 1 (1+a)x ' given algorithm as follows - you increment X with probability for some a > 0 (a = 1 in the above algorithm). What should the algorithm return now? Determine the value of a that you need to choose in order to find an estimate Y such that IY ml 5 6m. with probability at least 9/10? [1] Basic estimator: Let Y ( 1 h : {1, 2, .., n} -> [0,1] {h is an idealized hash func) While (stream is nonempty) Let i be the next element/token Y i S 512 using Chebyshev'slnequality. n+1 n+1 using Chebyshev's Inequality