CS2110-Homework 7 Recursive Assembly Solved

In this assignment, you will be implementing several subroutines in assembly, taking advantage of the calling convention that has been outlined in class/lecitation. For each subroutine, you will be required to implement the entire calling convention. This includes the buildup and teardown on the stack.

1         Instructions
You have been provided three assembly files, string ops.asm, handshake.asm, and buildheap.asm. These files contain a label for each of the subroutines that you will be asked to implement. DO NOT RENAME THE LABELS! You can add more to suit your needs, but don’t change the existing ones. Implement the following subroutines, use complx to debug them, and submit your files on Gradescope.

It is in your best interest to do the problems in order. The last one builds on the first two.

1.1        Part 1: String Operations 
The first part of this assignment is to implement a method to count the occurrences of a character in a string. This will utilize the strlen subroutine, which has been implemented for you.

1.1.1       String Length
To help you get started on the homework, we have provided you with the implementation of strlen. It includes the buildup of the stack, body of the function, and teardown of the stack. The pseudocode is provided here for your reference, but you do not have to implement this yourself. You will, however, have to call it from the next subroutine, so make sure you are familiar with how it works.

Pseudocode
int strlen(String s) { int count = 0; while (s.charAt(count) != "\0") { count++;

}

}

1.1.2       Count Character
Complete the count occurrence function in the string ops.asm file. This function should count how many times a given character appears in a string. This method should call the strlen method that you implemented in the previous part.

Pseudocode

int count_occurrence(String s, char c) { int count = 0; for (int i = 0; i < strlen(s); i++) { if (s.charAt(i) == c) { count++;

}

} return count;

}

1.2        Part 2: Handshaking 
The second part of this assignment is solving the handshake problem.

Background
With n people at a party, find the maximum number of handshakes possible given that any two people can only shake each other’s hand once. This problem can be easily solved using recursion and the pseudocode for this problem is in the next section!

Pseudocode
int handshake(int n) { if (n == 0)

return 0;

else return (n - 1) + handshake(n - 1);

}

1.3        Part 3: Build Heap 
Background

If you have taken CS 1332 (don’t worry if you haven’t), then you might be familiar with the data structure known as the binary heap. A binary heap (specifically a max heap) is essentially a binary tree with the property that for every node, its children are less than or equal to it. This means that the root node of the heap is the largest element. The cool thing about binary heaps is that they can be represented as arrays, where a node at index n has its left child at index 2n + 1 and its right child at index 2n + 2. The goal of the next two problems will be to implement a function that will order an array of elements so that they form a valid heap. While it may help you to know more about binary heaps in order to understand what is going on

(you can ready about them at https://www.geeksforgeeks.org/binary-heap/), you don’t actually have to know anything about them since we give you the pseudocode.

1.3.1       Heapify 
The first subroutine that we will have you implement is heapify. Heapify takes in an array, its length, and a given node i and then ensures that the heap property of a node being larger than its children is maintained for that node. If you have to swap two elements, then heapify recursively re-checks the heap property for child nodes. Once we have implemented, we will be able to call it for every node to actually convert a given array into a heap.

Your job is to implement heapify in the buildheap.asm file, starting at the heapify label.

Heapify Pseudocode
void heapify(int[] arr, int n, int i) {

// The following are all indices, not values

int largest = i; // Initialize largest as root int leftChild = 2*i + 1; // left = 2*i + 1 int rightChild = 2*i + 2; // right = 2*i + 2

// If left child is larger than root if (leftChild < n && arr[leftChild] arr[largest]) largest = leftChild;

// If right child is larger than largest so far if (rightChild < n && arr[rightChild] arr[largest]) largest = rightChild;

// If largest is not root if (largest != i)

{ swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree heapify(arr, n, largest);

}

}

1.3.2       Build Heap 
Once you’ve implemented heapify, buildheap is easy. All you have to do is start at the end of the array and iterate backwards over each element, calling heapify on each one.

In buildheap.asm, implement the following pseudocode, starting at the buildheap label.

Build Heap Pseudocode
void buildheap(int arr[], int n) { for (int i = n; i = 0; i--) heapify(arr, n, i);