YOUR NAME:

CSCI 159 Quiz 4 (F24N01/02) Monday lab

The quiz is closed book, closed notes, no electronics permitted, and to be completed as a strictly individual exercise. You are permitted one double-sided 8.5" x 11" sheet of notes.

There are four equally-weighted questions, worth a total of 10 marks. Attempt all questions, answering directly on the exam paper.

Note that when a code segment is requested you are only expected to put the requested lines of code, not the rest of a larger program it would be part of. If a complete program is requested, on the other hand, you should provide the entire program (#includes, int main, etc).

Question 1: Arrays [2.5 marks]
Provide an implementation for the copy function below. 
// copy the first N elements of arr2 into arr1 (assumes both arrays are big enough)
void copy(float arr1[], float arr2[], int N)

Question 2: Searching [2.5 marks]

(i) Suppose we have an array of N elements, for some large value of N, where the element values were provided by the user.

If we have no further information about the values provided but need to search for some value, K, which should we use: binary search or linear search, and why?

(ii) Suppose the binary search function below was called on an array of six elements whose values were { 3, 17, 23, 24, 27, 30 } and the target to search for was 11.

Show the sequence of midpoints that would be output before the function eventually returns a value, and show what value would be returned. 

int binarySearch(int arr[], int size, int target)
{
   int low = 0;
   int high = size-1;
   while (low <= high) {
      int mid = (low+high)/2;
      cout << "Current midpoint: " << mid << endl;
      if (arr[mid] == target) {
         return mid;
      } else if (arr[mid] < target) {
         low = mid+1;
      } else {
         high = mid-1;
      }
   }
   return -1;
}

Question 3: Sorting [2.5 marks]
Suppose the bubblesort function below was to be run on an array of six elements, where the initial contents were { 23, 17, 30, 3, 27, 24 }. 

void bubblesort(int arr[], int N)
{
   for (int pass = 1; pass < N; pass++) {
       for (int pos = 1; pos < N; pos++) {
           if (arr[pos-1] > arr[pos]) {
              // manually swap the contents
              int tmp = arr[pos-1]
              arr[pos-1] = arr[pos];
              arr[pos] = tmp;
           }
       }
   }
}

(i) Show what the re-arranged array content would look like after the first complete pass through the outer loop.

(ii) Show what the re-arranged array content would look like after the second complete pass through the outer loop.

Question 4: null-terminated char arrays [2.5 marks]
Each of the following questions assume the arrays in question are character arrays and use the null terminator ('\0') to mark the end of the currently-relevant portion of the array.

(i) The stringcompare function below operates differently than the strcmp from the cstring library. Study the function then explain what it returns to indicate if the two arrays have matching content and what it returns if their content differs. 
int stringcompare(char str1[], char str[2])
{
   int pos = 0;
   while (str1[pos] == str2[pos]) {
      if (str1[pos] == '\0') {
         return -1;
      } else {
         pos++;
      }
   }
   return pos;
}

(ii) The stringlength function described below is very similar to the strlen function from the cstring library. Provide an implementation stringlength. 
// counts and returns the number of characters in str prior to the null terminator
int stringlength(char str[])