6.046J Design and Analysis of Algorithms, Problem Set 5 Solutions

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Dana Moshkovitz and Bruce Tidor 6.046J/18.410J Handout 14 Problem Set 5 Solutions This problem set is due at 9:00pm on Wednesday, March 21. Problem 5-1. High Probability Bounds on Randomized Select Recall that in lecture, we discussed an algorithm for randomized select, for which you can find pseudocode in CLRS on page 216 in section 9.2. In this problem, you’ll explore the problem of high probability bounds for randomized select. We’ll go through a few steps to disprove the following statement, which we will refer to as (∗): Let T (n) be the running time of R ANDOMIZED -S ELECT on an input of size n. Then there exist 1 integers n0 , c ≥ 1 such that for all n ≥ n0 , P (T (n) > cn) ≤ . n (a) Let b be a real number such that 1/2 < b < 1, and let Ai be the array in the ith recursion. Define a bad pivot choice in the ith recursion as one that results in |Ai+1 | > b|Ai |. (Note that in class, we have been using b = 9/10.) Give a lower bound on the probability of having k bad pivot choices in a row. (The lower bound should hold for any input to R ANDOMIZED -S ELECT. Make it as tight as you can; you’ll need it in part (c).) Solution: A lower bound is (1 − b)k . For most inputs, the probability of getting a single bad pivot will actually be 2(1 − b), as there are two regions the pivot could be picked from that would leave an array of size greater than b|Ai |. However, in cases where the rank of the element being looked for is very small (< (1 − b)n) or very large (> bn), one of these regions may not be applicable for finding bad pivots, and therefore when Select is called on these elements, the probability of getting a bad pivot is only (1 − b). (b) If our initial array size is n, then after one bad pivot choice, the next array is of size at least bn. Recall that the running time at each recursive call requires time equal to at least the size of the array. Give a precise lower bound (do not use big-O notation) on the total running time of k recursive calls to R ANDOMIZED -S ELECT, if in every recursive call we chose a bad pivot. Solution: After i recursive calls where each pivot chosen is a bad pivot, the smallest possible array size we could have at that point is bi n. Because the running time at iterationP i is at least the P size of the array P |Ai |, we have a lower bound on the running time of ki=0 |Ai | = ki=0 bi n = n( ki=0 bi ) = n((1 − bk+1 )/(1 − b)). Handout 14: Problem Set 5 Solutions 2 (c) Use a proof by contradiction to disprove the statement (∗) above. (Hint: Suppose there exists a c, n0 satisfying the equation above. Then pick b = 1 − 21c .) Solution: As suggested in the hint, suppose there exists a c and n0 satisfying the equation above, and pick b = 1 − 21c . Now we will investigate the running time and probability of choosing k bad pivots in a row from the start, where k is some constant to be determined later. By part (b), the running time for the first k recursive calls is at least n((1 − bk+1 )/(1 − b)) = 2cn(1 − bk+1 ). Pick k to be a constant large enough so that bk+1 < 1/2. Then (1 − bk+1 ) > 1/2, so the total running time is greater than cn. By part (a), this situation occurs with probability at least (1 − b)k , which is a constant. Therefore we can pick an n >> k (to ensure that the algorithm does not terminate after k recursive calls) such that n > n0 and (1 − b)k < 1/n, contradicting the statement (∗) (which must hold for all n > n0 ). Therefore, we have a contradiction, and no pair c, n0 can exist satisfying the conditions. Problem 5-2. Random Vectors and Matrices Random vectors are good choices for hashing and testing, because they are unlikely to be orthogonal to a given (non-zero) input vector. In this problem, we will perform all operations in Zp for some prime number p (which is to say we take the result of any arithmetic operation mod p). (a) You are given a non-zero vector ~u ∈ Znp , and some number c ∈ Zp . Prove that if another vector ~v ∈ Znp has each element chosen independently and uniformly at random from Zp , then the probability that ~v · ~u = c is 1/p. (Hint: Observe that any non-zero vector ~u of size n has n − 1 elements which can be arranged into a non-zero vector of size n − 1. Then use induction to prove the claim.) Solution: First, we show the base case, for v, u ∈ Zp . The goal for the base case is to show that the probability that vu = c is 1/p for any c ∈ Zp . Note that, because we know that u is nonzero, it has a multiplicative inverse in Zp , so we can divide this whole equation by u. So we want to find the probability that v = c/u, where c/u is some fixed number in Zp . Because v is chosen uniformly at random from Zp , this probability is therefore 1/p. Now we show the inductive step. Assume the property is true for vectors of size n − 1. Additionally, note that if ~u of size n is non-zero, then it must have at least one nonzero element. If we take this element together with any other n − 2 elements of ~u, then the resulting u~′ of size n − 1 is non-zero. So, without loss of generality assume that the non-zero element is at some index less than n. Handout 14: Problem Set 5 Solutions 3 Then Pr(~v · ~u = c) = Pr( n X i=1 vi ui = c) = Pr( n−1 X vi ui = c − vn un ) = Pr( i=1 n−1 X vi ui = c′ ) i=1 We can do the last step because the elements of ~v are independent. Now using the induction hypothesis, we can conclude that the probability is 1/p. In class, we have seen a couple examples of universal hash families. We will now devise another universal hash family based on random matrices. (b) You are given two vectors ~x, ~y ∈ Znp such that ~x 6= ~y . Using the result from part (a), show that if ~v is a random vector as before, then Pr(~v · ~x = ~v · ~y ) = 1/p. Solution: ~v · ~x = ~v · ~y ⇐⇒ ~v · (~x − ~y ) = 0 Using the result from part (a) with ~u = ~x − ~y and c = 0, this happens with probability 1/p. (c) Using the result from part (b), show that if A is an m × n matrix with each element chosen independently and at random from Zp , then Pr(A~x = A~y ) = 1/pm . Solution: Note that A~x = A~y holds if and only if, for every row a~i of A, it holds that a~i · ~x = a~i · ~y . For each a~i , the probability that a~i · ~x = a~i · ~y is 1/p by part (b). Because each of the m rows of A are independent, we can multiply these probabilities to get a total probability of 1/pm that A~x = A~y . (d) Conclude that the family H of all such functions hA (~x) = A~x where A is an m × n matrix with elements in Zp , is universal. Solution: Each function in H maps an input vector to a hash value that is a vector of size m (in other words, a vector in Zm p ). The total number of possible hash values m is therefore p . Choosing one of these functions at random results in us getting a random matrix A. Using the result from part (c), the probability that hA (~x) = hA (~y ) for a given pair of vectors ~x and ~y that are not equal is 1/pm , fulfilling the definition of a universal hash family. In the implementation of the encryption algorithm BitWhipperTM, the key step is to perform the composition of two hashes to compute the vector ~y ∈ Zk2 such that ~y = hB (hA (~x)), where ~x ∈ Zn2 , A is an m × n matrix, B is a k × m matrix, and hA and hB are defined as in part (d) with p = 2. 4 Handout 14: Problem Set 5 Solutions Note that all operations here are performed in Z2 , which means all additions are bit-wise XOR. Ben Bitdiddle gives you a k × n matrix C over Z2 , which he says is equal to B · A. If he’s right, you could just use hC (~x) in the implementation of BitWhipperTM , in lieu of hB (hA (~x)). You want to make sure that C = B · A, but you don’t want to multiply the matrices because it will take you O(kmn) time. In part (e), you will come up with a randomized algorithm that runs much faster than O(kmn) time, and also runs faster than any known algorithm for rectangular matrix multiplication. (e) Using the result from part (a), devise a randomized algorithm to determine if C = B · A. Show that your algorithm is correct with probability at least 90%. Solution: Pick a random input vector ~x and compare the output of C~x to B(A~x). If they are unequal, we conclude that the Ben’s matrix is incorrect, otherwise we conclude it’s correct. 6 B · A, but the two outputs The output of this algorithm will be incorrect if C = 6 generated are equal. To analyze the probability of this happening, suppose that C = B · A and consider (C − B · A)~x, which is the product of a nonzero k × n matrix with a vector. This nonzero matrix must have at least one nonzero row. Consider the dot product of this row with ~x. Using (a), the probability that this product is equal to 0 is 1/p = 1/2, which is an upper bound for when the algorithm will be wrong. If we repeat 4 times, the probability of all four tries being wrong is 1/16, meaning we have at least 15/16 probability of correctness, which is more than 90%.