1.  What does F11 do?
2.  What key(s) "Step Over"?
3.  What does Shift-F11 do?
4.  What key(s) "Run to Cursor"?
5.  How do you "Set Next Statement"?
6.  How do you "Remove Breakpoint"?
7.  What kind of statement has no effect other than to verify that a certain condition is true, and to raise an error in a dialog box otherwise?  (Provide a 1-word answer).
8.  What do we call the process where we select certain cases to debug our code?
9.  How do you continue running after a breakpoint?
10.  What do you call the list of functions which, after a break, indicate which function called which function which ultimately called the function where the break occurred?

Note:  This is a programming quiz.  You must use Visual C++.  You must begin with a new project, and you may not use any notes or any pre-written code besides the code appended below.

Your task:  Find the two bugs in the code below.  Find the radixSort bug first, then the quickSort bug second.  It is anticipated that you do not know how either radixSort or quickSort works.  That is not necessary for finding the bugs in the manner in which we have covered in class.

Finally:  when you find the radixSort bug, position your debugger so that the next F10 will make the program crash.  When you have done so, let me know and I will hit F10 to confirm this.

Good luck.

//////////////////////////////////////////////////
/////  Includes, Typedefs, Constants
//////////////////////////////////////////////////

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <math.h>
#include "apvector.h"

typedef apvector<int> intVector;
typedef intVector& intVectorByReference;
typedef int& intByReference;

const int BASE = 10;
const int MAX_EXPT = 6;

void loadVector(intVectorByReference v)
{
 int len = v.length();
    for (int i = 0; i < len; i++)
        v[i] = rand() % int(pow(BASE,MAX_EXPT));
}

void swap(intByReference x, intByReference y)
{
 int temp = x;
 y = temp;
 x = y;
}

int getPivotIndex(intVectorByReference v,int lo,int hi)
{
 return lo;
}

int pivot(intVectorByReference v, int lo, int hi)
{
 int pivotIndex;
 // 1. get a pivot index and swap it to the first position
 pivotIndex = getPivotIndex(v,lo,hi);
 swap(v[pivotIndex],v[lo]);

 // 2. Swap elements as necessary so those less than or
 //    equal to the pivot are in the left portion, and
 //    those greater than the pivot are in the right portion
 //    of the vector.
 int loPointer = lo + 1; // lo is the pivot, and we don't count it
 int hiPointer = hi;

 while (loPointer < hiPointer)
 {
  if (v[loPointer] <= v[lo])
   loPointer++;
  else if (v[hiPointer] > v[lo])
   hiPointer--;
  else
   // Both left and right elements are on the wrong
   // side, so swap them and continue.
   swap(v[loPointer],v[hiPointer]);
 }

 // 3. Swap the pivot into the new location
 assert(loPointer == hiPointer);
 int newPivotIndex;
 if (v[loPointer] <= v[lo])
  newPivotIndex=loPointer;
 else
  newPivotIndex=loPointer-1;
 swap(v[newPivotIndex],v[lo]);
 return newPivotIndex;
}

void quickSort(intVectorByReference v,int lo, int hi)
{
 if (lo >= hi)
  return;

 int p = pivot(v,lo,hi);

 quickSort(v,lo,p-1);
 quickSort(v,p+1,hi);
}

void quickSort(intVectorByReference v)
{
 quickSort(v,0,v.length()-1);
}

//////////////////////////////////////////////////
/////  radixSort()
//////////////////////////////////////////////////

// This sort is O(n log RANGE), where RANGE is the range of
// the elements in the vector.  For example, here we are using
// elements from 0 to 999,999, so our range is 10^6, and this
// requires 6 iterations, thus this is O(6 * n), which in fact
// is O(n).

// Thus, for large enough n, this sort will be arbitrarily
// faster than either mergeSort or quickSort (and of course
// will completely bury insertionSort, selectionSort, and bubbleSort).

typedef apvector<intVector> intVectorVector;

void radixSort(intVectorByReference v)
{
 intVectorVector buckets(BASE);
 intVector bucketCount(BASE);
 int i, len, bucket, bucketSize;
 len = v.length();

 // Initialize buckets
 int defaultBucketSize = 10 + 2 * len / BASE;
 for (i=0;i<BASE;i++)
 {
  bucketCount[i] = 0;
  buckets[i].resize(defaultBucketSize);
 }

 // Iterate over each expt up to MAX_EXPT
 int divver, modder = 1;
 for (int expt=0; expt < MAX_EXPT; expt++)
 {
  modder *= BASE;
  divver = modder / BASE;
  // 1.  Place each element v[j] into the approprate bucket
  //     based on the expt'th digit in v[j]
  for (int j=0;j<len;j++)
  {
   bucket = (v[j] % modder) / divver;
   bucketSize = buckets[bucket].length();
   // add v[j] to this bucket now
   // first make sure there is room
   if (bucketCount[bucket] >= bucketSize)
    buckets[bucket].resize(2*bucketSize);
   buckets[bucket][bucketCount[bucket]] = v[j];
   (bucketCount[bucket])++;
  }

  // 2.  Copy the buckets, from bucket[0] to bucket[BASE-1],
  //     back into v.
  //     AND clear the buckets for the next iteration by
  //     resetting the bucket count to 0!
  int vIndex = 0;
  for (bucket = 0; bucket <= BASE; bucket++)
  {
   for (i=0; i<bucketCount[bucket];i++)
    v[vIndex++] = buckets[bucket][i];
   bucketCount[bucket] = 0;
  }
 }
}

//////////////////////////////////////////////////
/////  verifySorted() and testSort()
//////////////////////////////////////////////////

void verifySorted(intVectorByReference v,
      intVectorByReference vOriginal)
{
 int cursor, sum1, sum2;
 for (cursor=v.length()-1; cursor>0; cursor--)
  if (v[cursor] < v[cursor-1])
  {
   cout << "Uh oh -- vector not sorted at index "
     << cursor << endl;
   assert(false);
   return;
  }
 // Now check that the sorted vector is not corruped
 sum1 = 0;
 sum2 = 0;
 for (cursor=v.length()-1; cursor>=0; cursor--)
 {
  sum1 = sum1 + v[cursor];
  sum2 = sum2 + vOriginal[cursor];
 }
 if (sum1 != sum2)
 {
   cout << "Uh oh -- sorted but corrupted!" << endl;
   assert(false);
   return;
 }
 cout << "Wahoo -- the vector is sorted!" << endl;
}

// Note:  IntroCS students are *not* responsible
// for any part of the following function.
void testSortFunction(char* name,void(*sortFn)(intVector&v),intVector& v)
{
    intVector v2;
 int time1,time2;
    v2 = v;
 cout << endl << "Starting " << name << ": ";
 cout.flush();
 time1 = time(NULL);
    sortFn(v2);
 time2 = time(NULL);
 verifySorted(v2,v);
 cout << "Sort took: " << (time2 - time1) << " seconds" << endl;
}

//////////////////////////////////////////////////
/////  main()
//////////////////////////////////////////////////

void main()
{
    intVector v;
    int vSize;
 bool useSlowSorts;

 useSlowSorts = true;
    while (true)
    {
        cout << "Enter size of vector (0 to toggle slow sorts, <0 to exit): ";
        cin >> vSize;
        if (vSize < 0)
            return;

  if (vSize == 0)
  {
   useSlowSorts = !useSlowSorts;
   if (!useSlowSorts)
    cout << "not ";
   cout << "using slow sorts." << endl << endl;
  }
  else
  {
   v.resize(vSize);
   loadVector(v);
   cout << endl << "------------------------------";
   testSortFunction("quickSort",quickSort,v);
   testSortFunction("radixSort",radixSort,v);
   cout << "------------------------------" << endl << endl;
  }
    }
}