(Solved): An Assignment Help Is Required, Modern Algorithm Design

Exercise-1: Probabilistic Counting In this problem, we are going to explore an interesting algorithm for counting the number of tokens in a stream (not the number of distinct tokens!). It is trivial to see that if there are m tokens in the stream, then [log₂ m] many bits suffice to keep track of the number of tokens. Now consider the following randomized algorithm. In the following, let Y be the final value returned by the algorithm (a) Show that E [Y] = n + 1 (b) Show that Var [Y] = n (n − 1)/2 (c) It can be shown that the value of X grows only till log log m with high probability - the proof is highly non-trivial and we just need to believe this for now. Using this fact, the analysis above and the idea of using parallel estimators, show how to modify the basic algorithm to return an estimator with error ε with probability at least 1−δ using at most (With high probability)., where ε, δ > 0 (d) For this part, we consider an alternate (and somewhat more elegant) way of modifying the basic estimator to achieve better estimates. Suppose you modify the 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 |Y − m| <= ε m with probability at least 9/10?

An Assignment Help Is Required, Modern Algorithm Design

Related Study Services

Post your Answer - free or at a fee

Answer Review

An Assignment Help Is Required, Modern Algorithm Design

Related Study Services

Post your Answer - free or at a fee

Login to your tutor account to post an answer