## Description

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.

** **

**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 person’s 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):

** **

**The Algorithm**

**Notation**: if *arr* is an array, we use *arr[s…e]* 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[s…e].*

The recursive divide-and-conquer algorithmic:

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

**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:

(Supplied)*main***:**

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

(Supplied)*PrintSum***:**

* *

*$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.

(To be implemented)*FindMaxNeg2***:**

*$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.

* *

(To be implemented)*FindMaxNeg3***:**

*$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:

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

(To be implemented)*MaxNegSumBoundary***:**

The input is a subarray *arr[s…e]* and a direction (*d*).

- If
*d==0*, it computes the maximum negative sum of any subbarray of*arr[s…e]*__that includes__Thus, it considers the most negative sum among subarrays:*arr[e]*.*arr[e] arr[e-1…e] arr[e-2…e] … arr[s…e]* - If
*d==1*, it computes the most negative sum of any subarray of*arr[s…e]*__that include__Thus, it considers the most negative sum among subarrays:*arr[s]*.

*arr[s] arr[s…s+1] arr[s…s+2] … arr[s…e]*

*$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:

- if
*s==e*, return*arr[s]*. - 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)*

(To be implemented)*MaxNegCrossingSum***:**

*$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:

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

(To be implemented)*MaxNegSubArraySum***:**

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

This function does the following:

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

**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 didn’t 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.