CSCI 159 Quiz 3 (F25N02) 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.

The quiz is worth a total of 20 marks. Attempt all three 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. When a complete program is requested, on the other hand, you should provide the entire program (#includes, int main, etc).

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)

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)

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.