CS39001 I Assignment 3 Solution

MIPS Assignment 3
AIM: To get proficient in writing recursive functions in MIPS along with handling arrays, allocating variables dynamically, writing function subroutine and passing parameters to functions. No credit will be given for an iterative (linear) implementation. Your program must have recursive function as specified in the questions.
INSTRUCTIONS: Make one submission per group in the form of a single zipped folder containing your source code(s). Name your submitted zipped folder as Assgn 3 Grp GroupNo.zip and (e.g. Assgn 3 Grp 25.zip). Inside each submitted source files, there should be a clear header describing the assignment no., problem no., semester, group no., and names of group members. The file name should be of the format QuestionNo Grp GroupNo.s (e.g. Q1 Grp 25.s). Liberally comment your code to improve its comprehensibility.
Question 1
Write a complete MIPS-32 program that -
1. Prompts the user for four positive integers n, a r, m as “Enter three positive integers (n, a, r and m) : ”.
2. Allocates space for an n × n square matrix in integer array A. Populate the array A in a row major fashion using a Geometric Progression (GP) series with initial value a and common ratio r such that the ith element A[i] = (ari) mod m.
3. Print the elements of matrix A.
4. Recursively computes the determinant of the matrix A. The value of determinant of a matrix can be calculated by following Laplace expansion.
Laplace expansion expresses the determinant of a matrix A in terms of determinants of smaller matrices, known as its minors. The minor Mi,j is defined to be the determinant of the (n − 1) × (n − 1) matrix that results from A by removing the ith row and the jth column. The expression (−1)i+jMi,j is known as a cofactor. For every i, one has the equality given in Equation 1 which is called the Laplace expansion along the ith row. The computation of minor is recursive in nature.
] (1)
The above expression reduces the matrix dimension considering any i-th row. It can similarly be done w.r.t. any j-th column.
5. Prints the final determinant with suitable message as “Final determinantof the matrix A is ”.
Follow these implementation-level constraints while writing your code. Write the following functions:
1. “initStack” : Initialise the stack pointer ($sp) and frame pointer ($fp).
2. “pushToStack” : This function takes one argument as input (in $a0) and push it to the stack.
3. “popFromStack” : This function does not take any argument and returnsthe first element in the stack.
4. “printMatrix” : This function takes two parameters- the positive integersn (in $a0) and the address of the two-dimensional n × n integer array A (in $a1). It prints the elements of A in a row-major fashion.
5. Write a recursive subroutine recursive Det that is passed the following parameters- a positive integer n0 and the address of any intermediate matrix A0 stored in the two-dimensional n0 × n0 integer array. It returns the determinant of the matrix A0.
If required, you can write additional functions as well, but with proper comments and descriptions.
Question 2
Write a complete MIPS-32 program that -
1. Reads an array of ten integers from the user (can also be negative). Thesenumbers are collected from the input console using a loop and stored in the memory in an array called ‘array’. Do not store the numbers as scalars in ten different non-contiguous locations or in ten different registers.
2. Write a recursive function named recursive sort that takes the start address, start index and end index of an array in order to sort the array recursively. You have to implement your code following Algorithm 1 as given below.
3. After sorting, print the sorted array on the console with a proper messageas “Sorted array :” .
Follow these implementation-level constraints while writing your code. Write the following helper functions:
1. “initStack” : Initialise the stack pointer ($sp).
2. “pushToStack” : This function takes one argument as input and push itto the stack.
3. “SWAP” : The function takes two array elements as inputs and performswap operation.
4. “printArray” : This function takes the array address and array size andprints the elements of A.
If required, you can write additional functions as well, but with proper comments and descriptions.
Algorithm 1 recursive sort(A,left,right)
1: l ← left,r ← right,p ← left;
2: while l < r
3: while A[l] ≤ A[p] and l < right
4: l + +;
5: while A[r] ≥ A[p] and r > left
6: r − −;
7: if l ≥ r then
8: SWAP(A[p], A[r]); // Swap the array elements
9: recursive sort(A, left, r-1);
10: recursive sort(A, r+1, right);
11: return;
12: SWAP(A[l], A[r]);

Question 3
Write a complete MIPS-32 program that -
1. Reads an array of ten integers from the user (can also be negative). Readan integer (n) from the user to be searched in the array.
2. Sort the 1-D array in ascending order using the recursive sort function implemented in the previous question, and print the sorted array with the message – “Sorted array: ”.
3. Write a recursive function recursive search to search the array for the presence of the value key in the array following the Algorithm 2 given below. The address of the sorted array and key are passed as argument to implement the recursive search function. The function returns the index where key is found, or return -1 if not found.
4. If the search is successful, the program will print an appropriate successmessage with the array index (i) where the value was found, such as“< n > is FOUND in the array at index < i >.”.
5. If the search is unsuccessful, the program will print a failure message, suchas “< n > NOT FOUND in the array.”.
Follow these implementation-level constraints while writing your code. Write the following helper functions:
1. “initStack” : Initialise the stack pointer ($sp).
2. “pushToStack” : This function takes one argument as input and push itto the stack.
3. “printArray” : This function takes the array address and array size andprints the elements of A.
If required, you can write additional functions as well, but with proper comments and descriptions.
Algorithm 2 recursive search(A,start,end,key)
1: while start ≤ end
2: mid1 ← start + (end − start)/3;
3: mid2 ← end − (end − start)/3;
4: if key == A[mid1] then
5: return mid1;
6: else if key == A[mid2] then
7: return mid2;
8: else if key < A[mid1] then
9: return recursive search(A,start,mid1 − 1,key);
10: else if key > A[mid2] then
11: return recursive search(A,mid2 + 1,end,key);
12: else
13: return recursive search(A,mid1 + 1,mid2 − 1,key);
14: return −1