In: Computer Science
When finding the minimum positive subsequence sum (mpss) for an
array a = a0, a1, . . . , an−1 of integers, one can use the
following divide-and-conquer algorithm. Divide the array into two
equal subarrays aleft and aright, and recursively compute the mpss
of both subarrays. Then compute the mpss, call if mpssmid, of any
subsequence that crosses the boundary between aleft and aright.
Finally, take the minimum positive value of the three answers.
Answer the following questions pertaining to how mpssmid is
computed.
5a. Step 1: compute the leftward (respectively rightward) sums of
aleft (respectively, aright). For k = 1, . . . , n/2 provide an
expression that gives the k th leftward sum LSk of aleft. Hint: LS1
= an/2.
5b. If every leftward sum is added to every rightward sum to form a
boundary-crossing sum, then exactly how many boundary-crosing sums
are formed? State the resulting running-time recurrence and running
time, according to the Master Theorem.
5c. On the other hand, if the leftward and rightward sums are first sorted, then what is the most number of boundary-crossing sums that must be computed? Determine the boundary-crossing sums that are computed for the array a = 12, 43, −65, 76, −32, 81, 19, −95, 27, −43.
Answer (a):
LS1 = a[n/2]
LS2 = a[n/2] + a[n/2 - 1] = LS1 + a[n/2 - 1]
LS3 = LS2 + a[n/2 - 2]
LSk = LS(k-1) + a[n/2 - (k-1)]
Answer(b):
If every leftward sum is added to every rightward sum to form a boundary-crossing sum, then n/2 * n/2 = n2/4 boundary-crosing sums are formed. Becuase there n/2 leftward sums and n/2 rightward sums and hence there are n2/4 combinations.
Answer(c):
if the leftward and rightward sums are first sorted, then n-1 boundary-crossing sums must be computed
a = 12, 43, −65, 76, −32, 81, 19, −95, 27, −43.
Compute the left sums starting from mid and moving left: -32, -32 + 76 = 44, 44 -65=-21, -21+43=22, 22+12=34.
Compute the right sums starting from mid+1 and moving right: 81, 81+19=100, 100-95=5, 5+27=32, 32-43=-11
Quicksort the left sums: leftsum = -32,-21,22,34,44
Quicksort the right sums: rightsum = -11,5,32,81,100
Round | i | j | leftsum[i] + rightsum[j] |
1 | 0 | 4 | -32 + 100 = 68 (>0 decrement j) |
2 | 0 | 3 | -32 + 81 = 49 (>0 decrement j) |
3 | 0 | 2 | -32 + 32 = 0 (<=0 increment i) |
4 | 1 | 2 | -21 + 32 = 11(>0 decrement j) |
5 | 1 | 1 | -21 + 5 = -16 (<=0 increment i) |
6 | 2 | 1 | 22 + 5 = 27 (>0 decrement j) |
7 | 2 | 0 | 22 - 11 = 11 (>0 decrement j) |
8 | 2 | -1 | end |
The maximum positive subsequence sum mpss middle returns 11