Lecture 6: Randomized Algorithms

Lecture 6 Randomized Algorithms 6.046J Spring 2015 Lecture 6: Randomized Algorithms • Check matrix multiplication • Quicksort Randomized or Probablistic Algorithms What is a randomized algorithm? • Algorithm that generates a random number r ∈ {1, ..., R} and makes decisions based on r’s value. • On the same input on different executions, a randomized algorithm may – Run a different number of steps – Produce a different output Randomized algorithms can be broadly classified into two types- Monte Carlo and Las Vegas. Monte Carlo Las Vegas runs in polynomial time always runs in expected polynomial time output is correct with high probability output always correct Matrix Product C =A×B Simple algorithm: O(n3 ) multiplications. Strassen: multiply two 2 × 2 matrices in 7 multiplications: O(nlog2 7 ) = O(n2.81 ) Coppersmith-Winograd: O(n2.376 ) 1 Lecture 6 Randomized Algorithms 6.046J Spring 2015 Matrix Product Checker Given n × n matrices A, B, C, the goal is to check if A × B = C or not. Question. Can we do better than carrying out the full multiplication? We will see an O(n2 ) algorithm that: • if A × B = C, then P r[output=YES] = 1. • if A × B = C, then P r[output=YES] ≤ 12 . We will assume entries in matrices ∈ {0, 1} and also that the arithmetic is mod 2. Frievald’s Algorithm Choose a random binary vector r[1...n] such that P r[ri = 1] = 1/2 independently for r = 1, ..., n. The algorithm will output ’YES’ if A(Br) = Cr and ’NO’ otherwise. Observation The algorithm will take O(n2 ) time, since there are 3 matrix multiplications Br, A(Br) and Cr of a n × n matrix by a n × 1 matrix. Analysis of Correctness if AB = C Claim. If AB = C, then P r[ABr = Cr] ≥ 1/2. Let D = AB − C. Our hypothesis is thus that D = 0. Clearly, there exists r such that Dr = 0. Our goal is to show that there are many r such that Dr = 0. Specifically, P r[Dr = 0] ≥ 1/2 for randomly chosen r. D = AB −C = 0 =⇒ ∃ i, j s.t. dij = 0. Fix vector v which is 0 in all coordinates except for vj = 1. (Dv)i = dij = 0 implying Dv = 0. Take any r that can be chosen by our algorithm. We are looking at the case where Dr = 0. Let r' = r + v Since v is 0 everywhere except vj , r' is the same as r exept rj' = (rj + vj ) mod 2. Thus, Dr' = D(r + v) = 0 + Dv = 0. We see that there is a 1 to 1 correspondence between r and r' , as if r' = r + V = r'' + V then r = r'' . This implies that number of r' for which Dr' = 0 ≥ number of r for which Dr = 0 From this we conclude that P r[Dr = 0] ≥ 1/2 2 Lecture 6 Randomized Algorithms 6.046J Spring 2015 Quicksort Divide and conquer algorithm but work mostly in the divide step rather than combine. Sorts “in place” like insertion sort and unlike mergesort (which requires O(n) auxiliary space). Different variants: • Basic: good in average case • Median-based pivoting: uses median finding • Random: good for all inputs in expectation (Las Vegas algorithm) Steps of quicksort: • Divide: pick a pivot element x in A, partition the array into sub-arrays L, consisting of all elements < x, G consisting of all elements > x and E consisting of all elements = x. • Conquer: recursively sort subarrays L and G • Combine: trivial Basic Quicksort Pivot around x = A[1] or A[n] (first or last element) • Remove, in turn, each element y from A • Insert y into L, E or G depending on the comparison with pivot x • Each insertion and removal takes O(1) time • Partition step takes O(n) time • To do this in place: see CLRS p. 171 3 Lecture 6 Randomized Algorithms 6.046J Spring 2015 Basic Quicksort Analysis If input is sorted or reverse sorted, we are partitioning around the min or max element each time. This means one of L or G has n − 1 elements, and the other 0. This gives: T (n) = T (0) + T (n − 1) + Θ(n) = Θ(1) + T (n − 1) + Θ(n) = Θ(n2 ) However, this algorithm does well on random inputs in practice. Pivot Selection Using Median Finding Can guarantee balanced L and G using rank/median selection algorithm that runs in Θ(n) time. The first Θ(n) below is for the pivot selection and the second for the partition step. (n) T (n) = 2T + Θ(n) + Θ(n) 2 T (n) = Θ(n log n) This algorithm is slow in practice and loses to mergesort. Randomized Quicksort x is chosen at random from array A (at each recursion, a random choice is made). Expected time is O(n log n) for all input arrays A. See CLRS p.181-184 for the analysis of this algorithm; we will analyze a variant of this. “Paranoid” Quicksort Repeat choose pivot to be random element of A perform Partition Until resulting partition is such that |L| ≤ 34 |A| and |G| ≤ 34 |A| Recurse on L and G 4 Lecture 6 6.046J Spring 2015 Randomized Algorithms “Paranoid” Quicksort Analysis Let’s define a ”good pivot” and a ”bad pivot”­ Good pivot: sizes of L and G ≤ 34 n each Bad pivot: one of L and G is ≤ 34 n each bad pivots good pivots n 4 bad pivots n 2 n 4 We see that a pivot is good with probability > 1/2. Let T (n) be an upper bound on the expected running time on any array of n size. T(n) comprises: • time needed to sort left subarray • time needed to sort right subarray • the number of iterations to get a good call. Denote as c · n the cost of the partition step Expectations 2cn (2cn)/4 (2cn)/16 3(2cn)/16 3(2cn)/4 9(2cn)/16 O(1) O(1) T (n) ≤ maxn/4≤i≤3n/4 (T (i) + T (n − i)) + E(#iterations) · cn Now, since probability of good pivot > 12 , E(#iterations) ≤ 2 5 Lecture 6 Randomized Algorithms T (n) ≤ T (n) 4 +T 3n 4 6.046J Spring 2015 + 2cn We see in the figure that the height of the tree can be at most log 4 (2cn) no matter 3 what branch we follow to the bottom. At each level, we do a total of 2cn work. Thus, expected runtime is T (n) = Θ(n log n) 6