Quiz 3 prep material

Quiz 3 preparation material

Quiz 3 will be 50 minutes long, handwritten, and conducted in the first half of the weekly lab session.

The quiz will be closed book, closed notes, and no electronics permitted, but students will be permitted one double-sided 8.5x11" 'cheat sheet'. (These do not need to be handwritten.)

Some questions on the quiz may ask you to write short explanations/descriptions of different aspects of C++, some will ask you to write short C++ code segments to achieve specific results, some will ask you to show and/or explain the results of short C++ code segments.

The topics and suggested preparation activities for the quiz are listed below.

As with prior quizzes, the best way to practice coding in general is to write and debug as many small programs as you have time for. The best way to practice for hand-written quizzes and exams is to try writing small programs on paper then take your answers and type them in/debug them to see where the bugs are. If you need a refresher on how to write/compile 'from scratch' programs (as opposed to the ones in the provided lab and make files), see the notes near the top of the quiz 1 prep material.

arrays

There will be one general question on arrays: likely with the array passed as a parameter to a function that is supposed to process the data somehow. Typical objectives for the function would be things like

fill the array with user-supplied data
print the array contents
copy N elements of one array into another (with two array parameters)
find the smallest/largest value in an array
count the number of values in the array that are bigger than some target,
etc

searching

This will likely include one part that checks that you know the circumstances under which one should choose linear/binary search, then a second part that checks you know how binary search works (e.g. given the following binary search algorithm, show the sequence of midpoints that are visited)

sorting

This will check that you know how bubblesort works, e.g. given the initial array content and sorting algorithm shown below, show the revised array content after each of the first three passes through the outer loop.

Last year's quiz questions and sample solutions

Question 1: Arrays
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

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