CSCI 159 Quiz 3 Sample Solutions Monday lab

Question 1 Arrays [7 marks]
Write the body of the transform function below so that it behaves as dictated by the comments. You may assume there already exists a swap function to exchange the values of two doubles, e.g. void swap(double &x, double &y);

// swaps the contents of the first k elements of the two arrays
//       (leaving the rest of the array elements unchanged)
//    and returns the sum of the values swapped
// e.g. if k was 4 and the first 4 elements of arr1 were { 1, 0, 3, 2 }
//    and the first 4 elements of arr2 were { 9, 6, 3, 1 }
// then after running exchangeK the first 4 elements of arr1 would be { 9, 6, 3, 1 },
//    the first 4 elements of arr2 would be { 1, 0, 3, 2 },
// and the value returned would be 24 (the sum of all 8 values)
double exchangeK(double arr1[], double arr2[], int k)

Corrections: (i) the name is exchangeK, not transform
(ii) the value returned would be 25

Sample solution

double exchangeK(double arr1[], double arr2[], int k)
{
   double total = 0;
   for (int pos = 0; pos < k; pos++) {
       swap(arr1[pos], arr2[pos]);
       total += arr1[pos];
       total += arr2[pos];
   }
   return total;
}

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-decreasing order and the last N values are not necessarily sorted at all.
For example, with M=5 and N=6, ARR might contain { 3, 7, 8, 19, 206 } in the first 5 positions and { 18, 2, 97, 96, -3, 32 } 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 part (ii) the third parameter in the calls should be M+N-1, not N-1

Sample solution

(i) First M use binary search since the values are sorted in the way binary search expects
    and binary is more efficient than linear

(ii) Last N we have to use linear search since the values are not sorted

(iii)  We need to call binary on the first chunk,
       if that returns anything but -1 then we found it, return the position
       otherwise call linear on the second chunk and return whatever it returns

   int modSearch(float arr[], int M, int N, float target)
   {
       int res = binary(arr, 0, M-1, target);
       if (res != -1) {
          return res;
       } else {
          return linear(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=0; j < N; j++) {
           if (arr[i] > arr[i+1]) {
              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) The output generated for the first two passes is simply
      Pass 0: 5 5 5 5
      Pass 1: 8 8 8 8
    Working through the code line by line, the outer loop goes through
       values 0,...,3 for i
    and on each of these passes it goes through positions 0..N-1 for j,
       but each time it's comparing arr[i] with arr[i+1],
           which is using the wrong index (should be comparing arr[j] with arr[j+1])
       Pass 0: swaps 8,5,        prints arr[0], i.e. 5
               doesn't swap 5,8, prints arr[0], i.e. 5
               doesn't swap 5,8, prints arr[0], i.e. 5
               doesn't swap 5,8, prints arr[0], i.e. 5

       so after Pass 0 the new array contents are
            5, 8, 9, 6, 3, 1
       and the output it has displayed is
            Pass 0: 5 5 5 5

       Pass 1 follows a similar process, and outputs
            Pass 1: 8 8 8 8 (since now it's comparing arr[1] with arr[2] and printing arr[1] each time)

(ii) The problems and fixes:
         The big problem is that inside the j for loop it keeps using the wrong
             index variable, all the i's inside that loop should actually be j's
         Fix: inside the inner for loop, change the i's to j's

         A second problem is that it's comparing past the Nth element:
             when j = N-1 it compares arr[N-1] with arr[N],
             which is past the first N elements we're supposed to be sorting
                and potentially could swap that element into the array portion
                we are supposed to be sorting
         Fix: change the condition check of the inner for loop to j < (N-1);