# [Solved] CESC328 Programming assignment 7

Click And Check all our Assignments

10 USD \$

Category: Tag:

Write a recursive function to calculate the minimum positive subsequence sum (MPSS). In other words, of all subsequences whose sum adds to a positive number, you want to determine the minimum of such sums.

Hint:

1. Use the same divide and conquer algorithm for MSS, but now it is not so easy to compute

MPSSmiddle, Explain why? (You could make a counter example on a piece of paper)

1. For each subarray there are n/2 such subsequence sums. (Find them and save them in 2 different arrays called SL and SR) (g. Let’s say that the left subarray is: aL = [ 2, -3, 1, 4, -6] ➔ SL = [2, -1, 0, 4, -2])
2. Using quicksort, sort SL in ascending order and SR in descending
3. Define two markers: i and j: Let i be the index marker of SL, and j for SR.
4. Set smin = inf. Now start iterating through SL and SR:
1. If s = SL(i) + SR(j) ≤ 0, then increment i.
2. Else if s < smin, then set smin = s, and increment j,
3. Otherwise, we have s > smin, in which case we increment j.
4. Set MPSSmiddle = smin when either the elements of SL or SR have been exhausted.
5. Calculate the time complexity of your algorithm for finding MPSS on paper and show your answer to me. Running time should satisfies T(n) = Θ(nlog2 n).
6. Explain how/why the algorithm for MPSSmiddle (You may write your answer on paper)

Example: Ask the user to give you the size of the array (n) and generate n random numbers between -20 to 20.

A = [2, -3, 1, 4, -6, 10, -12, 5.2, 3.6, -8], Output:

MPSS = 0.8

## Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart  [Solved] CESC328 Programming assignment 7
10 USD \$