CSCI 159 Quiz 4 (F24N01/02) sample solutions

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)
// Sample solution
{
   // for each of the first N elements (positions 0..N-1)
   //     copy that element from array 2 into array 1
   for (int pos = 0; pos < N; pos++) {
       arr1[pos] = arr2[pos];
   }
}

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?

Sample solution:
// we can't use binary search since it only reliably works if the data
//    is known to be sorted,
// thus we're pretty much stuck with linear search

(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;
}

Sample solution
low	high	calculated mid	array value at mid	action
0	5	2 (rounds down)	23	change high to mid-1 (1)
0	1	0 (rounds down)	7	change low to mid+1 (1)
1	1	1	17	change high to mid-1 (0)

At this point low(1) is greater than high(0) so the while condition fails, we break out of the loop, and 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.

// Sample solution: showing the step-by-step sequence of comparisons
23 17 30 3 27 24
^^^^^ out of order so swaps
17 23 30 3 27 24
   ^^^^^ ok, no swap
17 23 30 3 27 24
      ^^^^ out of order so swaps
17 23 3 30 27 24
        ^^^^^ out of order so swaps
17 23 3 27 30 24
           ^^^^^ out of order so swaps
17 23 3 27 24 30
(final result after first pass)

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

// Sample solution
17 23 3 27 24 30
^^^^^ ok, no swap
17 23 3 27 24 30
   ^^^^ out of order so swaps
17 3 23 27 24 30
     ^^^^^ ok, no swap
17 3 23 27 24 30
        ^^^^^ out of order so swaps
17 3 23 24 27 30

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;
}

// Sample solution
This checks each position starting from 0
If the array contents match then
   it checks if their ends have been reached (the '\0' null terminator)
       in which case it returns -1 [i.e. returns -1 if the contents are a match]
   it advances to the next position
If the contents don't match then it leaves the loop.

Thus if the arrays exactly match it returns -1,
otherwise pos will be the first array position containing a mismatch

(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[])
// sample solution
{
   // variable to store the number of characters we've counted
   // ... we'll also use length as the position of the next
   //     character to look at in the text
   int length = 0;
   while (str[length] != '\0') {
      length++;  // we've seen one more non-null
   }
   // we got out of the loop after eventually finding a null
   return length;
}