0. Note:  There is a pop quiz sometime this week (hmmm, wonder when that could be) on this material.  Also, please have your assignments available at start of class tomorrow for on-the-spot grading prior to the quiz.

Also note:  You must work alone on this assigment.

1.  Make sure that you did Part B of Assignment 24.  Of course you did, right?

2.  Look at the code in apvector.cpp.  Whenever it finds a bug, it prints a helpful message and then crashes the program (by calling "exit(1)").  Your task here is to create your own version of apvector.cpp which includes assert statements so that the program breaks into the debugger before it crashes (which, obviously, gives you a better chance to debug it).  Do this by the following steps:

a.  Create a program which uses apvector but which has a bug which makes it crash (say, by accessing an out-of-bounds index of a vector).  You may start from a pre-existing program, such as your answer to Assignment 23.
b.  Run it, make sure it crashes.
c.  Save apvector.h in your project directory, but under the name myapvector.h
d.  Save apvector.cpp in your project directory, but under the name myapvector.cpp
e.  Change the last line of myapvector.h to include myapvector.cpp
f.   In your main program (the one which crashes), include "myapvector.h" instead of "apvector.h"
g.  Recompile your main program and run it.  It should still crash.  If not, panic.
h.  Now you are using a custom version of apvector.  Kudos.  Continue.
i.   Modify myapvector.cpp -- everywhere you see "exit(1)" (that is, the crash points), add a line just preceding that call with an appropriate assert.  Be sure that myapvector.h includes <assert.h>.
j.  Now, re-compile and run your main program -- instead of crashing, one of the asserts you added should fire, and you should wind up in the debugger.
k.  What to turn in:  the modified myapvector.cpp, that's all.

4.  Goedelization:  Recall that goedelizing reduces a set of objects to the positive integers.  Here, your task is to goedelize all possible rectangles with integer side lengths.  We'll represent these rectangles as rect(width,height).  So rect(3,4) is a rectangle of width 3 and height 4.  Your task is to come up with a mapping which reduces all such rectangles to integers.  This requires providing two functions:  RectangleToInteger(rectangle) and IntegerToRectangle(integer).   The first function takes a rectangle, say rect(3,4), and returns the goedel number, say 13.  The second function takes a goedel number, say 13, and produces the corresponding rectangle, say rect(3,4).  Note that once you have done this, there is a very simple way to iterate over all possible rectangles:

// Code which uses your goedelization to compute something
// over all possible rectangles:
for (int goedelNumber=0; true; goedelNumber++)
{
    rect = IntegerToRectangle(goedelNumber);
    // do something with rect...
}

Also note:  do not overthink this problem.  It should be fairly straightforward.  What's more, any mapping will do just fine.  You do not have to search for some kind of ideal mapping.

5.  (This part may be done over the weekend):  Read Section 11.4 of Brookshear on the Halting Problem.  Note that "bare bones" is a programming language the author invented earlier in Chapter 11.  You do not need to deeply understand "bare bones" in order to understand the essence of Section 11.4.

6.  (Appended)  See the Hints on Assignment 25 section below.

//////////////////////////////////////////////////
/////  Debugging Demonstration Code
/////
/////  An intentionally-corrupted version of the
/////  Sort Functions Demonstration Code
/////  by David Kosbie
//////////////////////////////////////////////////

// This program demonstrates the following 6 sorts:
// insertionSort, selectionSort, bubbleSort,
// mergeSort, quickSort, radixSort.

// The IntroCS students are responsible for the first 4
// sorts (all but quickSort and radixSort).

// The AP CS students are responsible for all 6 sorts.

//////////////////////////////////////////////////
/////  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;

//////////////////////////////////////////////////
/////  loadVector(), printVector(), and swap()
//////////////////////////////////////////////////

// loadVector() loads the vector v with
// random elements in [0,BASE^MAX_EXPT)
// (presently 10^6).
void loadVector(intVectorByReference v)
{
 // load vector with numbers mostly random in [0,BIG_NUM]
 int len = v.length();
    for (int i = 0; i < len; i++)
        v[i] = rand() % int(pow(BASE,MAX_EXPT));
}

// This function is provided here for debugging purposes,
// and is not currently called by any functions below.
void printVector(intVectorByReference v)
{
 // print vector elements separated by two spaces with
 // a carriage return at the end
    for (int i = 0; i < v.length(); i++)
        cout << v[i] << "  ";
    cout << endl;
}

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

//////////////////////////////////////////////////
/////  insertionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly inserts the element at the
// cursor into the sorted vector to the left of the cursor.

void insertionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
    for (cursor=0; cursor<len; cursor++)
        for (i=0;i<cursor;i++)
            if (v[i] > v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  selectionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly finds the smallest element from
// the cursor to the right end of the vector and swaps
// that element with the cursor.

void selectionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
    for (cursor=0; cursor<len; cursor++)
        for (i=cursor+1;i<len;i++)
            if (v[i] < v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  bubbleSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly sweeps through the vector and
// swaps each pair of elements which are out of order.
// This is repeated until an entire sweep results in no swaps.

void bubbleSort(intVectorByReference v)
{
 int len, cursor;
 bool unsorted;

 len = v.length();
 unsorted = true;

 while (unsorted == true)
 {
  unsorted = false;
  for (cursor=0; cursor < len; cursor++)
   if (v[cursor] < v[cursor-1])
   {
    swap(v[cursor],v[cursor-1]);
    unsorted = true;
   }
 }
}

//////////////////////////////////////////////////
/////  mergeSort()
//////////////////////////////////////////////////

// This O(n log n) sort is much faster than the O(n^2) sorts
// above.  It is also recursive whereas the above sorts are
// iterative.  It operates by recursively sorting the left
// and right halves of the vector and then merging the sorted
// halves into a sorted whole.

void merge(intVectorByReference v,int lo,int hi)
{
 // 1. Declare variables
 int mid, mergeIndex, mergeSize, leftIndex, rightIndex;
 int leftMaxIndex, rightMaxIndex;
 bool leftHalfDone, rightHalfDone;
 intVector mergeVector;

 // 2. Initialize variables
    mid = hi + lo / 2;
    leftIndex = lo;
 leftMaxIndex = mid;
    rightIndex = mid+1;
 rightMaxIndex = hi;
 leftHalfDone = false;
 rightHalfDone = false;
 mergeSize = 1 + hi - lo;
 mergeVector.resize(mergeSize);

 // 3. Merge into the mergeVector
    for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
    {
  // Get the next element from either left half or right half,
  // place into mergeVector and advance the appropriate index.
  // Use the left half if:
  //  a)  The right side is done, or
  //  b)  The left side is not done, and the left side is smaller
        if ((rightHalfDone == true) ||
            ((leftHalfDone == false) && (v[leftIndex] < v[rightIndex])))
  {
   // Use the next element on the left half
            mergeVector[mergeIndex] = v[leftIndex];
   leftIndex++;
   if (leftIndex > leftMaxIndex)
    leftHalfDone = true;
  }
        else
  {
   // Use the next element on the right half
            mergeVector[mergeIndex] = v[rightIndex];
   rightIndex++;
   if (rightIndex > rightMaxIndex)
    rightHalfDone = true;
  }
    }

 // 4. Copy from mergeVector back into v
    for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
  v[lo + mergeIndex] = mergeVector[mergeIndex];
}

// This function sorts the elements from v[lo] to v[hi].
void mergeSort(intVectorByReference v,int lo,int hi)
{
 int mid;

 // 1 Base Case: if there is 1 (or fewer) elements,
 // then the vector is sorted, so just return.
    if (hi <= lo)
  return;

 // 2.  Recursive Case
    mid = (hi + lo) / 2;
    mergeSort(v,lo,mid);   // Sort the left half
    mergeSort(v,mid+1,hi); // Sort the right half
 merge(v,lo,hi);        // And merge the sorted halves
}

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

//////////////////////////////////////////////////
/////  quickSort()
//////////////////////////////////////////////////

// This O(n log n) sort is also recursive like mergeSort.
// It is typically about twice as fast as mergeSort.  However,
// while the average performance for quickSort is O(n log n),
// its worst-case performance (if you pick the worst pivot each
// time) is O(n^2).  Conversely, mergeSort's worst-case performance
// is the same as its average-case performance:  both are O(n log n).

// This sort operates by choosing a pivot, then splitting the
// vector so that the elements less than or equal to the pivot
// are to the left of the pivot, and those greater than the
// pivot are to the right of the pivot.  Then the two portions
// to the left and right of the pivot are recursively sorted.

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)
{
 int cursor;
 for (cursor=v.length()-1; cursor>0; cursor--)
  if (v[cursor] < v[cursor-1])
  {
   cout << "Uh oh -- vector not sorted at index "
     << cursor << endl;
   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);
 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 << "------------------------------";
   if (useSlowSorts)
   {
    testSortFunction("insertionSort",insertionSort,v);
    testSortFunction("selectionSort",selectionSort,v);
    testSortFunction("bubbleSort",bubbleSort,v);
   }
   testSortFunction("mergeSort",mergeSort,v);
   testSortFunction("quickSort",quickSort,v);
   testSortFunction("radixSort",radixSort,v);
   cout << "------------------------------" << endl << endl;
  }
    }
}

1.  Regarding debugging:  there is a line which has two identical changes to be made on it.  Despite the two changes, this is only *one* bug.  Thus, there are still two other bugs besides that one.

2.  More on debugging:  the cursor on insertionSort() starts at 0, and you are used to it starting on 1.  This is not necessary, but neither is it a bug.  Prove to yourself that this does not affect execution at all (because the inner loop runs from i=0 while i<cursor, but on the first iteration that is while 0<0, which of course is never, so the inner loop is just skipped on that iteration).

3.  On the mapping:  In the hopes that it helps, here is a sample mapping which is incorrect (thus, it is a bad idea for you to use it), but might clarify what a suitable mapping is:  Given rect(width,height),
the resulting number N is just the concatenation of the two numbers. So, rect(1,2) maps to N=12.  Simple enough.  The problem, though, is that this maps in only one direction.  Consider that rect(1,23) maps to N=123, but rect(12,3) *also* maps to N=123.  Thus, we can't map from N back to rectangles -- what would we map N=123 to?  You need to find a way to map that works in both directions:  given a rect(width,height), you generate an N, but also given an N, you generate a single rect(width,height).

Good luck.

DK