In this assignment you will write a MIPS assembly program and test it using MARS instruction set simulator.
You will be given an integer array arr and a number num. The task is to find if a subset of array elements can sum up to the target num. If not possible you will output Not possible!. If it is possible, output Possible!. You can use every array element only once. Only positive integers are allowed as array elements. Finding only one combination is enough to output Possible!.
- In C++, you will write a recursive function named CheckSumPossibility as below:
int CheckSumPossibility(int num, int arr[], int size)
The function respectively gets the target number, the array and the size of the array. It returns 1 if a subset of the array can sum up to the target number and otherwise if it is not possible it outputs a 0. The sample output for six sample runs with 8 element array examples is as shown below. The numbers in parenthesis (black text) are for showing the possibility. Blue text is user input, red text is program output. 8 is the array size, 129 is the target number:
8 129
41 67 34 0 69 24 78 58
Not possible!
8 129
62 64 5 45 81 27 61 91
Not possible!
8 129
95 42 27 36 91 4 2 53
Possible! (36 91 2)
8 129
92 82 21 16 18 95 47 26
Possible! (92 21 16)
8 129
71 38 69 12 67 99 35 94
Possible! (35 94)
8 129
3 11 22 33 73 64 41 11 Not possible!
The main function is as below:
| int main(){ int arraySize; int arr[MAX_SIZE]; int num; int returnVal;cin >> arraySize; cin >> num;for(int i = 0; i < arraySize; ++i){ cin >> arr[i];} returnVal = CheckSumPossibility(num, arr, arraySize);if(returnVal == 1){ cout << Possible! << endl;} else { cout << Not possible! << endl;}return 0;} |
- (70pts) Write your program in MARS assembly with the guidance of the C++ code you wrote for part 1. You will read the input array from the console as shown in above main().
RULES:
- You can use pseudo instructions in MARS.
- Comment your assembly using your C++ code. For instance:
- Obey the contract, which defines the usage of MIPS registers.
- You have to write CheckSumPossibility as a procedure in assembly.
- Recursive backtracking implementation will get full credit. Any other accurately working implementation will get -15pts.
- For possible cases, if you also print the corresponding array elements in your assembly program (similar to shown in parenthesis in the above sample output) you get 10 extra points.
- For recursive backtracking you can check the lecture given by Marty Stepp from Stanford University:
- Anyone using a compiler instead of writing the assembly manually will get 0pts.
- Do not cheat, do not help anyone either. Otherwise both sides will get 0pts.
Hint for C++ part, which also affects the assembly program:
- Actually the recursive backtracking is an easier solution. An accurate implementation of the CheckSumPossibility function is even less than 20 lines of C/C++ code.
- As an optimization,
- you must ignore the next recursive calls when the sum exceeded the target number num.
- your program should stop when only one possible combination is found.
- You do not need any other helper function than the
CheckSumPossibility function.
Reviews
There are no reviews yet.