Question

In: Computer Science

When finding the minimum positive subsequence sum (mpss) for an array a = a0, a1, ....

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.

Solutions

Expert Solution

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


Related Solutions

Consider the problem of finding if an array contains a pair of integers with a sum...
Consider the problem of finding if an array contains a pair of integers with a sum of 100. The array contains n integers. a. Define the signature (header) of a C++ function that solves this problem (hint: inputs/outputs of function) b. Write the pseudocode or C++ body of the function (extra credit: write the most efficient algorithm) c. What is the asymptotic complexity of your algorithm? d. What would be the complexity of the best algorithm for this problem if...
1. Define the elements of the following equation: P = a0 ‒ a1 × Qd. 2....
1. Define the elements of the following equation: P = a0 ‒ a1 × Qd. 2. Given P = $150 ‒ 0.005 × Qd as the demand for a professional sports team: a. If P = $60, what is Qd? b. If P = $40, what is Qd? 3. Imagine these two possible changes from the demand curve listed in Question 2: a. P = $175 ‒ 0.005 × Qd b. P = $125 ‒ 0.005 × Qd For each,...
Write a procedure that accepts a byte string(base address in $a0, length in $ a1) and...
Write a procedure that accepts a byte string(base address in $a0, length in $ a1) and returns its XOR checksum, defined as the exclusive-OR of all its bytes, in $v0. (by MiniMIPS)
Sum An a series and |An| cnverges to 0. If the partial sum Sn (A1+A2+...+An) is...
Sum An a series and |An| cnverges to 0. If the partial sum Sn (A1+A2+...+An) is bounded, is the partial sum Sn' of all absolute value of An (|A1|+|A2|+...+|An|) also bounded?
Dynamic Programming Question. Make the table for finding a LCS (Longest Common Subsequence) of the strings...
Dynamic Programming Question. Make the table for finding a LCS (Longest Common Subsequence) of the strings SLWOVNNDK and ALWGQVNBKB. You need to Show the traceback for the LCS.
The filter coefficients of a second-order digital IIR filter are: a0 = 1, a1 = -2,...
The filter coefficients of a second-order digital IIR filter are: a0 = 1, a1 = -2, a2 = 2, b0 = 1, b1 = 1/2, b2 = 1/8. (a's are numerator coefficents and b's are the denominator coefficients). Compute the magnitude response |H(ej?)| where ? = 2.721 rad/sec.
6) (a) Denote the successive intervals that arise in the bisection method by [a0,b0, [a1,b1] ,...
6) (a) Denote the successive intervals that arise in the bisection method by [a0,b0, [a1,b1] , [a2,b2], and so on    Show that   bn – an = 2-n(b0-a0) (b) The bisection method is said to have a linear convergence. Explain as clearly as possible what that means c) For the bisection method, prove that |cn – cn+1| = 2-n-2 (b0 – a0)    where cn is the midpoint of each interval (ie) cn = (an + bn) /2
2. Write the hexadecimal numbers in the registers of $a0, $a1, $a2, $a3 after the following...
2. Write the hexadecimal numbers in the registers of $a0, $a1, $a2, $a3 after the following codes running: ori $a0, $0, 11 ori $a1, $0, 19 addi $a1, $a1, -7 slt $t2, $a1, $a0 beq $t2, $0, label addi $a2, $a1, 0 sub $a3, $a1,$a0 j end_1 label: ori $a2, $a0, 0 add $a3, $a1, $a0 end_1: xor $t2, $a1, $a0 *Values in $a0, $a1, $a2, $a3 after the above instructions are executed.
Solve the following recurrence relation (A) an = 3an-1 + 4an-2 a0 =1, a1 = 1
  Solve the following recurrence relation   (A) an = 3an-1 + 4an-2 a0 =1, a1 = 1   (B) an = 2an-1 - an-2, a0 = 1, a2= 2
A four-bit binary number is represented as A3A2A1A0, where A3, A2, A1, and A0 represent the...
A four-bit binary number is represented as A3A2A1A0, where A3, A2, A1, and A0 represent the individual bits and A0 is equal to the LSB. Design a logic circuit that will produce a HIGH output whenever the binary number is greater than 0010 and less than 1000. how can I do this by using sum of product, not K map
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT