# An Assignment Help Is Required, Modern Algorithm Design

Posted Under: Algorithms

Order Now

#### Related Study Services

DESCRIPTION
Posted
Modified
Viewed 16
Computer Science, An assignment is enclosed herewith & topic is Modern Algorithm Design. Simple hand written jpg or pdf file is also allow, Writer is not necessary.
Attachments
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?