Introduction to Algorithms (SMA 5503), Problem Set 9 Solutions

Introduction to Algorithms Massachusetts Institute of Technology Professors Erik D. Demaine and Charles E. Leiserson December 14, 2005 6.046J/18.410J Handout 35 Problem Set 9 Solutions Problem 9-1. More parallel merge sort In this problem we will improve the parallel merge-sort algorithm from lecture. The algorithm described in class has work �(n lg n) and parallelism �(n/ lg2 n). We shall develop an algorithm with the same work, but higher parallelism. (a) Given two sorted arrays containing a total of n elements, give an algorithm to find the median of the n elements in �(lg n) time on one processor. Solution: The basic idea is that if you are given two arrays A and B and know the length of each, you can check whether an element A[i] is the median in constant time. Suppose that the median is A[i]. Since the array is sorted, it is greater than exactly i − 1 values in array A. Then if it is the median, it is also greater than exactly j = ∨n/2� − (i − 1) elements in B. It requires constant time to check if B[j] � A[i] � B[j + 1]. If A[i] is not the median, then depending on whether A[i] is greater or less than B[j] and B[j + 1], you know that A[i] is either greater than or less than the median. Thus you can binary search for A[i] in �(lg n) worst-case time. The pseudocode is as follows: 1 2 3 4 5 6 7 8 9 M EDIAN -S EARCH (A[1 . . l], B[1 . . m], left, right) if left > right then return M EDIAN -S EARCH (B, A, max(1, ∨n/2� − l), min(m, ∨n/2�) i � ≤(left + right)/2√ j � ∨n/2� − i if (j = 0 ← A[i] > B[j]) and (j = m ← A[i] � B[j + 1]) then return (A, i) � median = A[i] elseif (j = 0 ← A[i] > B[j]) and j �= m and A[i] > B[j + 1] then return M EDIAN -S EARCH (A, B, left, i − 1) � median < A[i] else return M EDIAN -S EARCH (A, B, i + 1, right) � median > A[i] Let the default values for left and right be such that calling M EDIAN -S EARCH (A, B) is equivalent to M EDIAN -S EARCH (A[1 . . l], B[1 . . m], max(1, ∨n/2� − m), min(l, ∨n/2�)) The invariant in M EDIAN -S EARCH (A, B) is that the median is always in either A[left . . right or B. This is true for the initial call because A and B are sorted, so by the definition of median it must be between max(1, ∨n/2� − m) and min(l, ∨n/2�), inclusive. It is Handout 35: Problem Set 9 Solutions 2 also true the recursive calls on lines 8 and 9, since the algorithm only eliminates parts of the array that cannot be the median by the definition of median. The recursive call on line 2 also preserves the invariant since if left > right the median must be in B be­ tween the new left and right values. When the algorithm terminates, the return value is the median by the definition of median. This algorithm is guaranteed to terminate because at each step right − lef t decreases and the median must be either in A or B. The asymptotic worst-case running time of M EDIAN -S EARCH is the same as for performing two binary searches, which is �(lg n). Alternatively, you can find the median by repeatedly comparing the median of the two arrays and discarding the part that cannot contain the median. It runs for at most 2∨lg n� iterations because each iteration discards half of one of the input arrays. There­ fore this algorithm’s running time is also �(lg n). (b) Using the algorithm in part (a) as a subroutine, give a multithreaded algorithm to merge two sorted arrays. Your algorithm should have �(n) work and �(n/ lg 2 n) parallelism. Give and solve the recurrences for work and critical-path length, and show that the parallelism is �(n/ lg2 n), as required. Solution: We can write a multithreaded algorithm for merging in which the smaller and larger halves of the sorted arrays are merged recursively in parallel: 1 2 3 4 5 6 7 8 P-M ERGE (A[1 . . l], B[1 . . m], T [1 . . n]) if n � 0 then return (A, k) � M EDIAN -S EARCH (A, B) � wlog assume median is in A if n = 1 then T [1] � A[1] else spawn P-M ERGE (A[1 . . k − 1], B[1 . . ∨n/2� − k − 1], T [1 . . ∨n/2� − 1) spawn P-M ERGE (A[k . . l], B[∨n/2� − k . . m], T [∨n/2� . . n]) sync This algorithm merges two sorted arrays into a buffer T . We can assume without loss of generality that the median is in A; if it is in B, we can just swap A and B in the remainder of the algorithm. The work of this algorithm is T1 (n) = 2T1 (n/2) + �(lg n) = �(n). The critical path length T� (n) = T� (n/2) + �(lg n) = �(lg2 n). Therefore the parallelism is T1 /T� = �(n/ lg2 n). (c) Optional: Generalize the algorithm in part (a) to find an arbitrary order statistic. Using this algorithm, describe a merge-sorting algorithm with �(n lg n) work that achieves a parallelism of �(n/ lg n). Handout 35: Problem Set 9 Solutions 3 Solution: We first need a subroutine to find arbitrary order statistics. The following algorithm finds kth order statistic of all the elements from two sorted arrays. O RDER -S TATISTICS (A[p..q], B[r..s], k) 1 if q � p + 1 or s � r + 1� One of the arrays has less than 3 elements 2 then Find the kth order statistic in constant time trivially and return it. 3 if k � s + q − � p− � r + 2� � kth � element is less than or equal to the median element p+q r+s 4 then if A[ 2 ] < B[ 2 ] � 5 then return O RDER -S TATISTICS (A[p..q], B[r.. r+s ], k) 2 � p+q 6 else return O RDER -S TATISTICS (A[p.. 2 ], B[r..s], k) 7 if k > s + q − � p − r + 2� � kth element is greater than the median element p+q 8 then if A[ 2 ] < B[ r+s ] 2 9 10 then else � � � return O RDER -S TATISTICS (A[ p+q ..q], B[r..s], k − p+q + p − 1) 2 � � � 2 r+s r+s return O RDER -S TATISTICS (A[p..q], B[ 2 ..s], k − 2 + r − 1) We now use this subroutine into 2 sub-� � � � to merge two arrays. Instead of dividing arrays arrays, n−1 equally spaced order statistics (for k = n, 2 n, . . . , ( n− � we instead find � 1) n) and merge n subarrays in�parallel. Therefore, the critical path of the merg­ of is ing subroutine is M� (n) = M� ( n) + lg n and the solution � � this recurrence � M� n = �(lg n). The work of the merge is M1 (n) = nM1 ( n) + �( n lg n), whose solution is M1 (n) = �(n). Therefore, the work of merge-sort remains �(n), while the critical path reduces to T� (n) = T� (n/2) + �(lg n) = �(lg2 n).