[Solved] Programming Project {Most Negative Subarray Sum}

The goal of this project is to implement the most negative sum subarray problem in MIPS. The most negative subarray sum takes as input an array of integers and produces as output the most negative sum of any contiguous subarray in the original array.

For example: The input can be the array {2, 5, -6, 2, 3, -1, -5, 6}. An example of a subarray is {5,-6,2} but {2,3,-5} is not a subarray. We seek to find the most negative sum of elements in any subarray of the given array. In this example, the highlighted subarray has the most negative sum, which is -7. (You can verify this for yourself by trying other subarrays; this value will be the most negative possible).

We solve this problem using divide-and-conquer. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

In this project, we will develop a program to take as input an array, use a divide-and-conquer (function MaxNegSubArraySum defined below) to calculate the most negative sum of any subarray of the array, and print the most negative sum and its starting and ending positions in the array on the console and exit.

2. Important Links

Your project must use the provided template file. While you are free to add any further helper functions, your code must implement the following functions according to the specifications given in this document.

The grader should be able to remove any of your functions (and any non-essential helper functions it may use) from your code and use it in another persons programming assignment without issue (i.e. do not flip the order of variables passed to functions via registers $a0 and $a1 or returned via $v0 and $v1 use the conventions given). Several functions are provided, along with all the text strings one needs to complete this project. These should not, in any form, be modified, unless explicitly instructed.

You should use MIPS assembly code best practices as far as register storing and stack management. See these quick guides for more info (they are excellent, so read them before asking questions):

• http://logos.cs.uic.edu/366/notes/mips%20quick%20tutorial.htm

3. The Algorithm

Notation: if arr is an array, we use arr[se] to indicate the subarray that starts with element with index s and ends with element with index e (inclusive).

We will develop a procedure called MaxNegSubarraySum.

The input: an array arr[], a starting index s, and an ending index e.

The output: the maximum negative subarray sum in arr[se].

The recursive divide-and-conquer algorithmic:

1. Divide the array arr[se] in the middle into a left subarray arr[sm] and a right subarray, arr[m+1e], where m is the middle index: m=(s+e)/2.
2. Recursively call the MaxNegSubarraySum function twice to find the most negative subarray sum for the left subarray and the right subarray.
3. Use a different function, called MaxNegCrossingSum to find the maximum negative sum of any subarray of arr[se] that includes elements from both left and right subarrays.
4. Return the most negative value among the two values computed in step 2 and the value computed in step 3.

4. Project Structure and Function Pseudo-Code

Your code must implement the following functions according to specification given below. Remember to manage your stack!

The following functions must be implemented or have been supplied:

• main (Supplied):

1. Saves state of all relevant registers on the stack.
2. Reads in the numbers and size of array from data segment.
3. Calls the MaxNegSumSubArray function to return the value of the maximum negative subarray sum.
4. Calls PrintSum to print the value returned by MaxNegSumSubArray on the console.
5. Calls syscall to terminate the program.

• PrintSum (Supplied):

• $a0 holds the value to be printed.
• This function has no return value.

It prints MaxNeg Sub Array Sum is: and a number on the console.

• FindMaxNeg2 (To be implemented):

• $a1 holds the first number.
• $a2 holds the second number.
• $v0 contains the more negative of the two input numbers.

This function returns the most negative of two numbers.

• FindMaxNeg3 (To be implemented):

• $a1 holds the first number.
• $a2 holds the second number.
• $a3 holds the third number.
• $v0 contains the most negative among the 3 numbers.

This function does the following:

1. Calls MaxNeg on the first 2 numbers and store return value.
2. Calls MaxNeg on the return value in the previous step and the third number; returns the maximum negative of the result.

• MaxNegSumBoundary (To be implemented):

The input is a subarray arr[se] and a direction (d).

• If d==0, it computes the maximum negative sum of any subbarray of arr[se] that includes arr[e]. Thus, it considers the most negative sum among subarrays: arr[e] arr[e-1e] arr[e-2e] arr[se]
• If d==1, it computes the most negative sum of any subarray of arr[se] that include arr[s]. Thus, it considers the most negative sum among subarrays:

arr[s] arr[ss+1] arr[ss+2] arr[se]

• $a0 contains address to arr[].
• $a1 contains s
• $a2 contains e
• $a3 is the direction (either 0 or 1)
• $v0 returns the maximum negative subarray

This function does the following:

1. if s==e, return arr[s].
2. If $a3==0:

Call MaxNegSumBoundary(arr,s,e-1,0) and save the result in a register x

Return MaxNeg(arr[e], arr[e]+ x)

Else:

Call MaxNegSumBoundary(arr,s+1,e,1) and save the result in register x

Return MaxNeg(arr[s], arr[s]+ x)

• MaxNegCrossingSum (To be implemented):

• $a0 contains arr[].
• $a1 contains s. // s is the minimum (i.e. leftmost) index of the input array.
• $a2 contains m. // m is the middle ((s+h)/2) index of the input array.
• $a3 contains // e is the maximum (i.e. rightmost) index of the array.
• $v0 returns the maxneg sum of arrays that includes arr[m] and arr[m+1]

This function does the following:

1. Call MaxNegSumBoundary on the left subarray a[s,m] with direction 0.
2. Call MaxNegSumBoundary on the right subarray a[m+1,e] with direction 1.
3. Return the sum of the above two values.

• MaxNegSubArraySum(To be implemented):

• $a0 contains arr[]
• $a1 contains s
• $a2 contains e

This function does the following:

1. If there is only one element i.e. (s==e) return arr[s]
2. Find the middle point of given array, m=(s+e)/2
3. Call MaxNegSubArraySum(arr[], s, m) to compute the maximum subarray sum of the left subarray arr[sm].
4. Calls MaxNegSubArraySum(arr[], m+1, e) to compute the maximum subarray sum of the right subarray arr[m+1e].
5. Calls MaxNegCrossingSum(arr[],s,m,e) to compute the maximum subarray sum that goes through the middle.
6. Calls MaxNeg3 to return the maximum value among the values computed in 3, 4, and 5

5. MIPS Program Requirements

You must submit your solution by emailing a completed file ABC_XYZ_winter2017_project.s, where ABC and XYZ are the @ucsd.edu of each student, to [email protected]

6. Other criteria

We expect your code to be well-commented. Each instruction should be commented with a meaningful description of the operation. Ask yourself what kinds of comments would be useful if you didnt touch this code for a year or two and have completely forgotten how to code in MIPS. For example, this comment is bad as it tells you nothing:

addi $s0, $t0, -1 # $s0 gets $t0 1

A good comment should explain the meaning behind the instruction. A better example would be:

addi $s0, $t0, -1 # Initialize loop counter $s0 to n-1

Each project team contributes their own unique code no copying, cheating, or hiring help. Even if only one of the two partners is culpable, both students will be reported to Academic Affairs.