Programming assignment 6.
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:
➢ Use the same idea of 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)
To find MPSSmiddle:
- For each subarray there are n/2 such subsequence sums. (Find them and save them in 2 different arrays called SL and SR) (e.g. Let’s say that the left subarray is: aL = [ 2, -3, 1, 4, -6] ➔ SL = [-2, -4, -1, -2, -6])
- Using quicksort, sort SL in ascending order and SR in descending
- Define two markers: i and j: Let i be the index marker of SL, and j for SR.
- Set smin = inf. Now start iterating through SL and SR:
- If s = SL(i) + SR(j) ≤ 0, then increment i.
- Else if s < smin, then set smin = s, and increment j,
- Otherwise, we have s > smin, in which case we increment j.
- Set MPSSmiddle = smin when the elements of SL or SR have been exhausted.
- 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).
- Explain how/why the algorithm for MPSSmiddle (You may write your answer on paper)
Ask the user for the size of the array (n) and generate n random numbers between -20 to 20.
Example:
Input: A = [2, -3, 1, 4, -6, 10, -12, 5.2, 3.6, -8], Output: MPSS = 0.8
Reviews
There are no reviews yet.