[Solved] CESC328 Programming assignment 7

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

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

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