Zylab 3 – Single Procedure Call Zylab 4 – Nested Procedure Call Zylab 5 – Recursive Procedure Call

Please complete by Mid day tomorrow else i will request refund for all. You you can’t let me know

12.14 Zylab 3 – Single Procedure Call
Given an array of at least one integer, write a program to create a new array
with elements equal to the exponent of each element in the original array
raised to the index, i.e., B[i] = A[i]^i.
For this, write two functions that will be called in main function
independently.
•
exponent
inputs: element (A[i]) and index (i)
o task: returns the value of element raised to index (A[i]^i).
append
o inputs: base address of new array B (*B), current size of B (n2)
and the new element (A[i]^i)
o task: add the new element at the end.
o This function does not return any value (void).
o
•
Following is a sample C code to perform the required task. You may modify
the code for the functions, but the task performed should not be changed.
int main() {
// Variable Declaration
int* A, B;
// Base addresses of A and B
int n1, n2;
// Lengths of arrays A and B
int exp;
// Return value from exponent function
// Task of main function
B[0] = 1;
// 0th element = A[0]^0 = 1
for (int j = 1; j < n1; j++) { n2 = j; // Current length of array B exp = exponent(A[j], j); append(B, n2, exp); } n2++; } int exponent(int x, int y) { int exp = x; for (int j = 1; j < y; j++) { exp = exp * x; } return(exp); } void append(int* B, int n2, int exp) { B[n2] = exp; } Registers Variables $s0 A $s1 n1 $s2 B $s3 n2 Addresses Contents $s0 A[0] $s0+4 A[1] Addresses Contents … … $s0+4*(n-1) A[n-1] Example Test: If the values of $s1 through $s7 are initialized in the simulator as: (Use the '+' button under the Registers display to initialize register values for $s0, $s1, $s2 and the '+' button under the Memory display to initialize the A array elements.) Registers Data $s0 4000 $s1 5 $s2 8000 $s3 0 Addresses Contents 4000 10 4004 5 4008 -5 Addresses Contents 4012 -2 4016 0 The resultant registers will be: Registers Data $s2 8000 $s3 5 The resultant array B is: Addresses Contents 8000 1 8004 5 8008 25 8012 -8 8016 0 Note: 4 automated tests each worth 5 points. The registers $s2, $s3 and the array B elements in memory will be checked by the automated tests. Register to Variable Mappings Register Variable $s0 A $s1 n1 $s2 B $s3 n2 12.15 Zylab 4 - Nested Procedure Call Write a MIPS program to add a given node in a linked list at the specified location, using Nested Procedure Calls. If your code runs perfectly, but you didn't use Procedure Execution correctly, you will be given zero points. Given Inputs: • • • • • the head of a linked list, i.e, address of the start (first node) of the list location: number of node in the linked list after which node is to be added (0 to add before the 1st node, 1 to add after 1st node and so on.) the address of the node to be inserted And each node contains: an integer value address to the next node (address is NULL (0) if it is the last node in the list) Write the following three functions that will be called in order to update the linked list by adding the new node. • main task: calls the addNode function and reads the value of the newly added node. addNode o inputs: head of linked list (head), location to add node (n) and address of node to be added (node) o task: calls the findNode function and add the node after the n^th node in the linked list. If the number is greater than the size of list, then add the node at the end of the list. o output: value of the inserted node. findNode o inputs: head of linked list (*head) and location to add node (n) o task: navigate the linked list to find the addresses of the n^th and (n+1)^th nodes o outputs: addresses of the n^th and (n+1)^th nodes. o • • Following is a sample C code segment to perform the required task. (this code is incomplete and does not include creating the linked list or a new node, so you cannot compile it using any C compiler.) You may modify the code for the functions, but the task performed should not be changed. // Parameters of a node in the linked list (need not declare or initialize in MIPS) typedef struct node { int value; node->value
// Value in the node accessed by
node* next;
node->next
// Address of next node accessed by
} node;
// Datatype for each node
node *head;
// address of head (first node) of
linked list (global pointer)
int main() {
// Variable Declaration
node *newNode;
// address of node to be added
int n;
// number of the node in the list after
which node is to be added
int value;
// Value of the node to be added
// Task of main function
value = addNode(head, n, newNode);
}
int addNode (node* head, int n, node* newNode) {
node *addr1, *addr2; // addr1 = address of n^th
node, addr2 = address of (n+1)^th node
if (n == 0) {
// If node should be
added at the beginning of the list
newNode->next = head;
head of original list
head = newNode;
the new node
// Next for new node =
// global head updated to
return(newNode->value); // value of the node =
data at the address of the node, and then return to
caller
}
[addr1, addr2] = findNode (head, n);
findNode function
addr1->next = newNode;
node to be added
// Call
// Next for n^th node =
newNode->next = addr2;
// Next for added node =
(n+1)^th node of original list
return(newNode->value);
// value of the node =
data at the address of the node
}
node* findNode (node* head, int n) {
node* curr = head;
// Start with head of linked
list
for (int i = 1; i < n; i ++) { curr = curr->next;
next node address
if (curr->next == 0)
of List
break;
// Update the pointer to
// Break if end
}
return([curr, curr->next]);
// Two return
values (need not return as array in MIPS)
}
Registers Variables
$s0
head
$s1
newNode
$s2
n
$s3
val
Linked List and New Node in Memory:
Addresses
Contents
newNode
newNode->value
head
node1->value
head + 4
node1->next
node1->next
node2->value
node1->next + 4
node2->next
Addresses
Contents
node2->next
node3->value
node2->next + 4
node3->next
…
…
Example Test: If the values of $s0 through $s3 and Memory contents are
initialized in the simulator as:
(Use the ‘+’ button under the Registers display to initialize register values
for $s0, $s1, $s2 and the ‘+’ button under the Memory display to initialize
the initial array elements.)
Registers Data
$s0
4000
$s1
8000
$s2
2
$s3
0
Addresses Contents
8000
230
Addresses Contents
4000
4
4004
3848
3848
-15
3852
6104
6104
-10
6108
5008
5008
0
5012
4500
4500
40
4504
0
The resultant registers are:
Registers Data
$s0
4000
Registers Data
$s1
8000
$s2
2
$s3
230
The resultant array is:
Addresses Contents
8000
230
8004
6104
4000
4
4004
3848
3848
-15
3852
8000
6104
-10
6108
5008
Addresses Contents
5008
0
5012
4500
4500
40
4504
0
Register to Variable Mappings
Register
Variable
$s0
head
$s1
newNode
$s2
n
$s3
val
12.16 Zylab 5 – Recursive Procedure Call
Write a MIPS program to compute the product of two 16-bit signed
numbers using *recursive procedure calls. *Note:* You CANNOT use the
mult or mul instructions.
Given the multiplicand (md) and multiplier (m) as inputs, write
the main and recursion functions to compute the product (p) using the shift
and add recursive algorithm for multiplication.
Write the following functions in MIPS.
•
main
task: initialize product, multiplicand and multiplier registers and
call the recursion function with iteration number equal to the
size of numbers (16-bit).
o Note: If numbers are negative, convert to positive numbers and
then multiply. Add sign separately at the end. Do not convert
the original input registers, only convert the argument registers
sent to the recursion function.
recursion
o inputs: product (p), multiplicand (md) and multiplier (m)
registers and the iteration number (n).
o task: compute the nth iterative step of multiplication,
call recursion function by decrementing n and return if n = 0.
o outputs: updated product (p).
o
•
Refer to the binary shift and add multiplication algorithm discussed in
class. While writing the code,
Following is a sample C code segment. You may modify the code for the
functions, but the task performed should not be changed, i.e., you should use
recursive procedure calls.
// multiplier and multiplicand are inputs (For
compilable C code, you should use argc and argv for
command line inputs)
int main(int m, int md) {
// Initialization of p, m, md registers
int p = 0;
// Product initialized to 0
int sign_p = 0;
// negate the operands if negative
if (m < 0 and md > 0) or (m > 0 and md < 0) sign_p = 1; if (m < 0) m = -m; if (md < 0) md = -md; p = recursion(p, md, m, 16); // 16-bit unsigned multiplication => recursion 16 times
if (sign_p == 1)
p = – p;
operands is negative
// negate if one of the
}
int recursion(int p, int md, int m, int n) {
if (n == 0)
return(p);
else {
int m_0 = m & 1;
bit of multiplier
if (m_0
// 0th or least significant
== 1)
p = p + md;
m = m >> 1;
md = md