# 9.6: Exercises

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

1. Change the PrintIntArray subprogram so that it prints the array from the last element to the first element.
2. The following pseudo code converts an input value of a single decimal number from 1 ≤ n ≥ 15 into a single hexadecimal digit. Translate this pseudo code into MIPS assembly.
main
{
String a[16] a[0] = "0x0"
a[1] = "0x1"
a[2] = "0x2"
a[3] = "0x3"
a[4] = "0x4"
a[5] = "0x5"
a[6] = "0x6"
a[7] = "0x7"
a[8] = "0x8"
a[9] = "0x9"
a[10] = "0xa"
a[11] = "0xb"
a[12] = "0xc"
a[13] = "0xd"
a[14] = "0xe"
a[15] = "0xf"

int i = prompt("Enter a number from 0 to 15 ")
print("your number is " + a[i]
}

3. The AllocateArray subprogram is incorrect in that the allocation can fall on any boundary. This is a problem if the array is of elements that must fall on a specific boundary. For example, if the array is contains ints, the array allocation must fall on full word boundary.
1. Using the PromptString and AllocateArray subprograms, show how this problem can occur.
2. Change the AllocateArray program to always do allocations on a double word boundary.
4. The following pseudo code programs calculates the Fibonacci numbers from 1..n, and stores them in an array. Translate this pseudo code into MIPS assembly, and use the PrintIntArray subprogram to print the results.
main
{
int size = PromptInt(“Enter a max Fibonacci number to calc: “)
int Fibonacci[size]
Fibonacci[0] = 0
Fibonacci[1] = 1
for (int i = 2; i < size; i++)
{
Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2]
}
PrintIntArray(Fibonacci, size)
}

5. Change the sort in Program 9.2 to use a Selection Sort instead of a Bubble Sort.
6. Implement Program 9.2 so that the user is prompted for the maximum size of the array, and then fill the array with random numbers. Sort the array using any sort you choose. This will require the array be allocated in heap memory. Print out the array.
7. Implement a Binary Search algorithm, and using the results from Exercise 5, show how long the Binary Search takes (on average) for arrays of size 10, 100, and 1000. (You do not have to print out the values in the array).

This page titled 9.6: Exercises is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Charles W. Kann III.