CS39001 Assignment 4 Solved

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. 1

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.

n
det(A) = 􏰁(−1)i+j Mi,j · A[i][j] (1)

j=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 determinant

of 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 returns the first element in the stack.
4. “printMatrix” : This function takes two parameters- the positive integers n (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 n′ and the address of any intermediate ma- trix A′ stored in the two-dimensional n′ × n′ integer array. It returns the determinant of the matrix A′.

If required, you can write additional functions as well, but with proper com- ments 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). These numbers 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

2. Write a recursive function named recursive sort that takes the start ad- dress, 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 message as “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 it

   to the stack.

3. “SWAP” : The function takes two array elements as inputs and perform swap operation.
4. “printArray” : This function takes the array address and array size and prints the elements of A.

If required, you can write additional functions as well, but with proper com- ments and descriptions.

Algorithm 1 recursive sort(A,left,right)

1: 2: 3: 4: 5: 6: 7: 8: 9:

10: 11: 12:

l ← left,r ← right,p ← left; whilel<r

while A[l] ≤ A[p] and l < right l + +;

while A[r] ≥ A[p] and r > left r − −;

if l ≥ r then
SWAP(A[p], A[r]); // Swap the array elements recursive sort(A, left, r-1);
recursive sort(A, r+1, right);
return;

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). Read

an integer (n) from the user to be searched in the array.

3

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 success message 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, such as “< 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 it

   to the stack.

3. “printArray” : This function takes the array address and array size and

   prints the elements of A.

If required, you can write additional functions as well, but with proper com-

ments and descriptions.

Algorithm 2 recursive search(A, start, end, key)

1: 2: 3: 4: 5: 6: 7: 8: 9:

10: 11: 12: 13: 14:

while start ≥ end
mid1 ← start + (end − start)/3; mid2 ← end − (end − start)/3; if key == A[mid1] then

return mid1;
else if key == A[mid2] then

return mid2;
else if key < A[mid1] then

return recursive search(A, start, mid1 − 1, key); else if key > A[mid2] then

return recursive search(A, mid2 + 1, end, key); else

return recursive search(A, mid1 + 1, mid2 − 1, key); return −1

4