3. We are given a length-n binary list L. In other words, LDle {0, 1} for all j = 1.2, , n. Our problem is to count the number of 0's in L. We could of course solve this problem in (n) time by simply scanning L, but we want to solve it faster and so we turn to randomization. The randomized algorithm we use is the following function CouNTZEROES(L) n length(L) count 0 for j l to 100 do Comment: pick a random index i between 1 and n i random(1, n) if L[i] = 0 then count count 1 return r count/100 (a) What is the running time of this algorithm? Please show all your work. (b) Suppose that n = 106 and exactly a quarter of the elements in L are 0, what is the probability that the CouNtZEROES function returns 0? (c) A random variable X has binomial distribution with parameters m (a positive integer) and p (a real number between 0 and 1) if Pr(X = k] =CE).pk " (1-p)'n-k The way to think about X being binomially distributed is that we perform m indepen dent random trials and each trial can either succeed or fail. The "success" probability of a trial is p and so the failure probability of a trial is 1 - p. Then the random variable X represents the number of successful trials, out of m total random trials. To understand the formula in (1) note that the probability of k successful trials is p*, the probability of (m-k) unsuccessful trials is (1-p)m-k, and there are (79 ways of distributing the k successful trials among the m random trials. As in (b) suppose that n = 106 and exactly a quarter of the elements in L are 0. Using the above expression for a binomial distribution, write down the expression for the probability that CoUNTZEROES returns the correct answer, namely 106/4