Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1, . . . , n} written in some arbitrary order (this means that A is a permutation of the set {1, . . . , n}). Our goal in this problem is to design a very fast randomized algorithm that can find an index i in this array such that A[i] mod 3 = 0, i.e., A[i] is divisible by 3. For simplicity, in the following, we assume that n itself is a multiple of 3 and is at least 3 (so a correct answer always exist). So for instance, if n = 6 and the array is A = [2, 5, 4, 6, 3, 1], we want to output either of indices 4 or 5. (a) Suppose we sample an index i from {1, . . . , n} uniformly at random. What is the probability that i is a correct answer, i.e., A[i] mod 3 = 0? (5 points) (b) Suppose we sample m indices from {1, . . . , n} uniformly at random and with repetition. What is the probability that none of these indices is a correct answer? (5 points) Now, consider the following simple algorithm for this problem: Find-Index-1(A[1 : n]): Let i = 1. While A[i] mod 3 6= 0, sample i {1, . . . , n} uniformly at random. Output i. The proof of correctness of this algorithm is straightforward and we skip it in this question. (c) What is the expected worst-case running time of Find-Index-1(A[1 : n])? Remember to prove your answer formally. (7 points) The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never terminate! For this reason, let us consider a simple variation of this algorithm as follows. Find-Index-2(A[1 : n]): For j = 1 to n: Sample i {1, . . . , n} uniformly at random and if A[i] mod 3 = 0, output i and terminate; otherwise, continue. If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i] mod 3 = 0 and output it as the answer. Again, we skip the proof of correctness of this algorithm. (d) What is the worst-case running time of Find-Index-2(A[1 : n])? What about its expected worst-case running time? Remember to prove your answer formally.

Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1,..., n} written in some arbitrary order (this means that A is a permutation of the set {1,...,n}). Our goal in this problem is to design a very fast randomized algorithm that can find an index i in this array such that A[i] mod 3 = 0, i.e., A[i] is divisible by 3. For simplicity, in the following, we assume that n itself is a multiple of 3 and is at least 3 (so a correct answer always exist). So for instance, if n = 6 and the array is A = (2,5,4,6,3,1), we want to output either of indices 4 or 5. (a) Suppose we sample an index i from {1,...,n} uniformly at random. What is the probability that i is a correct answer, i.e., A[i] mod 3 = 0? (5 points) (b) Suppose we sample m indices from {1,..., n} uniformly at random and with repetition. What is the probability that none of these indices is a correct answer? (5 points) Now, consider the following simple algorithm for this problem: Find-Index-1(A[1: n]): Let i = 1. While A[i] mod 3 + 0, sample i e {1,..., n} uniformly at random. Output i. The proof of correctness of this algorithm is straightforward and we skip it in this question. (C) What is the expected worst-case running time of Find-Index-1(A[1:n])? Remember to prove your answer formally. (7 points) The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never terminate! For this reason, let us consider a simple variation of this algorithm as follows. Find-Index-2(A[1:n]): For j =1 to n: - Sample i E {1,..., n} uniformly at random and if A[i] mod 3 = 0, output i and terminate; otherwise, continue. If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i] mod 3 = 0 and output it as the answer. Again, we skip the proof of correctness of this algorithm. (d) What is the worst-case running time of Find-Index-2(A[1 : n])? What about its expected worst-case running time? Remember to prove your answer formally. (8 points) Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1,..., n} written in some arbitrary order (this means that A is a permutation of the set {1,...,n}). Our goal in this problem is to design a very fast randomized algorithm that can find an index i in this array such that A[i] mod 3 = 0, i.e., A[i] is divisible by 3. For simplicity, in the following, we assume that n itself is a multiple of 3 and is at least 3 (so a correct answer always exist). So for instance, if n = 6 and the array is A = (2,5,4,6,3,1), we want to output either of indices 4 or 5. (a) Suppose we sample an index i from {1,...,n} uniformly at random. What is the probability that i is a correct answer, i.e., A[i] mod 3 = 0? (5 points) (b) Suppose we sample m indices from {1,..., n} uniformly at random and with repetition. What is the probability that none of these indices is a correct answer? (5 points) Now, consider the following simple algorithm for this problem: Find-Index-1(A[1: n]): Let i = 1. While A[i] mod 3 + 0, sample i e {1,..., n} uniformly at random. Output i. The proof of correctness of this algorithm is straightforward and we skip it in this question. (C) What is the expected worst-case running time of Find-Index-1(A[1:n])? Remember to prove your answer formally. (7 points) The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never terminate! For this reason, let us consider a simple variation of this algorithm as follows. Find-Index-2(A[1:n]): For j =1 to n: - Sample i E {1,..., n} uniformly at random and if A[i] mod 3 = 0, output i and terminate; otherwise, continue. If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i] mod 3 = 0 and output it as the answer. Again, we skip the proof of correctness of this algorithm. (d) What is the worst-case running time of Find-Index-2(A[1 : n])? What about its expected worst-case running time? Remember to prove your answer formally. (8 points)