CSCI 159 Quiz 3 Sample Solutions Wednesday lab

Question 1 Arrays [7 marks]
Write the body of the transform function below so that it behaves as dictated by the comments.

// for each of the first k elements of the two arrays, arr1 and arr2,
//    subtract the value of arr2's element from arr1's element
//    (modifying the content in arr1)
// e.g. if k was 4 and the first 4 elements of arr1 were { 9, 6, 3, 1 }
//    and the first 4 elements of arr2 were { 1, 0, 3, 2 }
// then after running subFrom the first 4 elements of arr1 would be { 8, 6, 0, -1 }
//    (and the contents of arr2 would be unchanged)
void subFrom(double arr1[], double arr2[], int k)

Correction the name of the function is subFrom, not transform

Sample solution


void subFrom(double arr1[], double arr2[], int k)
{
   for (int pos = 0; pos < k; pos++) {
       // subtract arr2 element from arr1 element,
       //    put result back as new arr1 element
       arr1[pos] = arr1[pos] - arr2[pos];
   }
}

Question 2 Searching [7 marks]
The functions linear and binary below can be used to perform linear searches and binary searches on portions of an array, with the binary search assuming the array contents are already sorted in non-decreasing order.
Both functions assume that lowpos and hipos specify the first and last positions of the portion of the array that needs to be searched.

int linear(float arr[], int lowpos, int hipos, float target)
{
   for (int pos = lowpos; pos <= hipos; pos++) {
       if (arr[pos] == target) {
          return pos;
       }
   }
   return -1;
}

int binary(float arr[], int lowpos, int hipos, float target)
{
   while (lowpos < hipos) {
      int mid = (lowpos + hipos) / 2;
      if (arr[mid] == target) {
         return mid;
      } else if (arr[mid] < target) {
         lowpos = mid+1;
      } else {
         hipos = mid-1;
      }
   }
   return -1;
}

Suppose we have an int array name ARR whose size is M+N, and in which the first M values are sorted in non-increasing order (i.e. the opposite to what binary expects) and the last N values are sorted in non-decreasing order.
For example, with M=5 and N=6, ARR might contain { 206, 19, 8, 7, 3 } in the first 5 positions and { -3, 2, 18, 32, 96, 97 } in the remaining 6 positions.

(i) If we were looking for the value specified by variable T, identify which of the following calls would most appropriately search the first M positions of ARR and why: linear(ARR, 0, M-1, T) or binary(ARR, 0, M-1, T).

(ii) If we were looking for the value specified by variable T, identify which of the following calls would most appropriately search the last N positions of ARR and why: linear(ARR, M, N-1, T) or binary(ARR, M, N-1, T).

(iii) Write the modSearch function below, using appropriate calls to linear and binary to search arrays that are formatted in this unusual two-segment style.
I.e. modSearch calls either linear or binary on the first M elements and returns that position if the search was successful, otherwise it calls either linear or binary on the last N elements and returns the result of that search.)

int modSearch(float arr[], int M, int N, float target)

Correction: in (ii) the third parameter in the calls should be M+N-1 rather than N-1

Sample solution

(i) Use linear on the first M since they aren't sorted in the direction
    needed by binary so binary can't reliably work

(ii) Use binary on the last N since they are correctly sorted for binary
     and it will be more efficient than linear would

(iii) idea: call linear on the first M, if it finds it then we're done,
            otherwise call binary on the last N

      int modSearch(float arr[], int M, int N, float target)
      {
          int res = linear(arr, 0, M-1, target);
          if (res !=  -1) {
             return res;
          } else {
             return binary(arr, M, M+N-1, target);
         }
      }

Question 3 Sorting [6 marks]
The bubbleSort code below follows a typical pattern for re-arranging the contents of an array into sorted order, but contains a flaw.
(Assume the swap function already exists and is correct and that the appropriate libraries and using statements are in place.)

// sort the data in just the first N elements of the given array,
//    putting them in non-decreasing order
void sortBeginning(int arr[], int N)
{
   for (int i = 0; i < N; i++) {
       cout << "Pass " << i << ":";
       for (int j=1; j < N; j++) {
           if (arr[i-1] < arr[i]) {
              swap(arr[i], arr[i-1]);
           }
           cout << " " << arr[i];
       }
       cout << endl;
   }
}

(i) Show the output that would be generated by the first two passes through the outer loop of sortBeginning if the following code segment ran:

    int data[6] = { 8, 5, 9, 6, 3, 1 };
    sortBeginning(data, 4);

(ii) Explain what appears to be functionally wrong with the bubblesort code and outline a simple fix.

Sample solution

(i)  Working through the code line by line for the first two passes:

     On the first pass, i=0, it goes through j values 1 to N-1
        each time it compares arr[i-1] to arr[i],
           but it should be comparing based on j (the element position) not i (the pass number)
        on the very first pass, when i is 0, this means it's comparing
           arr[0-1] to arr[0], i.e. it's looking in arr[-1], which is off the bottom of the array
        the value there could be anything, 0, -1, some garbage, etc
           and in this case if it is anything less than 8 it will get swapped into arr[0]
        e.g. if the value there is 0 then we'll get 0 swapped into arr[0] and 8 swapped
             into the memory space before the array (doing who knows what there...)
        So the first time it hits cout it prints arr[i], i.e. arr[0], e.g. 0 (the garbage value)

        On the next pass through the inner loop the swap wouldn't swap anything
           since it's comparing arr[-1] and arr[0] again and has already swapped
           them if arr[-1] < arr[0]
        when it hits the cout it prints arr[0] again (since i is still 0)
        and again on the third pass

     So the first pass output is
        Pass 0: 0 0 0

     On the second pass it goes through a similar process,
        using i=1 and j values 1,2,3
     in this case we again get
        Pass 1: 0 0 0
     though at least this time it's not looking off the bottom end of the array

(ii) The first problem is that it's using the wrong index variable for
         everything inside the inner loop, it should be using j's not i's
     Fix: inside the inner for loop change all the i's to j's

     The second problem is that it's sorting backwards, 
         right now it says if (arr[i-1] < arr[i]) then swap them,
            which is the opposite of what we'd want
     Fix: change the < to >