CSc 17  Final Examination   Tuesday  18 December 2001
>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1. (25 pts)  The code below will compile but not link, because the
function f() is not defined. Add code for a single function f() to
the code below so that the code compiles and runs and produces the output
between the dashed lines.
   #include <fstream.h>
   void a(int x)
   {cout<<(x*x)<<endl;}
   void b(double y)
   {cout<<y<<endl;}
   int main()
   {f(a,3);
    f(b,2.5);
   }
   /*-----------------------
    9
    2.5
   --------------------------*/
-------ANSWER
template <typename T, typename V>
void f(T g,V x){
  g(x);
}


2.  (25 pts) Assume that the class Node below is used to build a binary
tree.  Further assume that as the tree is built the height of each Node
is stored in the data member 'height'. Write a function balanced() which
returns 'true' if and only if the tree is balanced.  If rt is declared
as Node *rt, the call to determine whether the binary tree with root rt
is balanced would be balanced(rt).
  class Node
  {public:
     double data;
     int height;
     Node *child[2];
  };
ANSWER
-------------
int h(Node *rt)
{if(rt==NULL)
  return -1;
 return rt->height;
}

bool balanced(Node *rt)
{if(rt==NULL)
  return true;
 int lHt,rHt;
 bool tBal;
 lHt=h(rt->child[0]);
 rHt=h(rt->child[1]);
 tBal=lHt-rHt<2 && rHt-lHt<2;
 return balanced(rt->child[0]) && balanced(rt->child[1]) && tBal;
}

3.  (25 pts)  Write a function, g, which reads text from a file f, of type
istream, and displays a faithful copy of the file on the screen, except
that it appends an asterisk (*) after every line whose first character
is a digit (0, 1, ..., 9) and whose last character is a period (.). The
call to the function would read g(f).
ANSWER
--------
   void getch(istream &f,char &ch)
   {if(f.good())
     f.get(ch);
    if(!f.good())
     ch='\n';
   }

   void g(istream &f)
   {bool digit;
    char ch,oldch;
    getch(f,ch);
    while(!f.eof())
    {digit=ch>='0' && ch<='9';
     while(ch!='\n')
      {cout<<ch;
       oldch=ch;
       getch(f,ch);
      }
     if(digit && oldch=='.')
       cout<<'*';
     cout<<endl;
     getch(f,ch);
    }
   }

4.  (25 pts)  The merge sort uses the following recursive algorithm:  To
sort the entries in an array between index i and j inclusive, divide that
part of the array in half, sort each half, and merge the two sorted halves.
Write the function mergeSort() which implements this algorithm.  If we
have int x[30], n; and we wish to sort the entries x[0],...,x[n-1], the initial
call to mergeSort() should be mergeSort(x,0,n-1).  You may assume that you
have available the function merge() described below.

//PreConditions: entries x[low],...,x[mid] are in ascending order
//               entries x[mid+1],....,x[hi] are in ascending order
//PostConditions: entries x[low],...,x[hi] are the original entries
//                from x[low],...,x[hi], but in ascending order
//Example:   if low=0, mid=3, hi= 6, x={1,5,7,9,2,6,12} before
//           then after merge(x,0,6) x={1,2,5,6,7,9,12}
void merge(int x[],int low, int mid, int hi);
ANSWER
---------
  void mergeSort(int x[],int low,int high)
  {int mid;
   if(low<high)
    {mid=(low+high)/2;
     mergeSort(x,low,mid);
     mergeSort(x,mid+1,high);
     merge(x,low,mid,high);
    }
  }

5.  (25 pts) The function merge() in question 4 is a bit challenging to
write.  A simpler function merges the two parts of the array into a
second array.  Write that function.  If we have
int x[30],y[30],low,mid,high; and assume that the entries x[low],...,x[mid]
are in ascending order and the entries x[mid+1],...,x[high] are in
ascending order, then after the call merge(x,low,mid,high,y) the array
y[low],...,y[high] will have the entries from x[low],...,x[high] in
ascending order.
ANSWER
------------
  void copy(int x,int &y,int &xLoc,int&yLoc)
  {y=x;
   xLoc++;
   yLoc++;
  }

  void merge(int x[],int low1,int top1,int top2,int y[])
  {int low2,newLoc;
   low2=top1+1;
   newLoc=low1;
   while(low1<=top1 && low2<=top2)
     if(x[low1]<x[low2])
       copy(x[low1],y[newLoc],low1,newLoc);
     else
       copy(x[low2],y[newLoc],low2,newLoc);
   while(low1<=top1)
     copy(x[low1],y[newLoc],low1,newLoc);
   while(low2<=top2)
     copy(x[low2],y[newLoc],low2,newLoc);

  /* a simpler alternative, but this depends on knowing
     exactly how ++ behaves, something we did not cover
  while(low1<=top1 && low2<=top2)
       if(x[low1]<x[low2])
         y[newLoc++]=x[low1++];
       else
         y[newLoc++]=x[low2++];
     while(low1<=top1)
       y[newLoc++]=x[low1++];
     while(low2<=top2)
       y[newLoc++]=x[low2++];
  //*/
  }

6.  (25 pts) Assume that classes Stack and Queue implement the ADT's Stack
and Queue, respectively.  As usual, I forgot to document the function below.
Provide the documentation.
   void quizzical(istream &in)
   {Stack st(50);
    Queue q(50);
    int x;

    in>>x;
    while(!in.eof())
     {st.push(x);
      q.enqueue(x);
      in>>x;
     }
    while(!st.empty())
     cout<<st.pop()<<endl;
    while(!q.empty())
     cout<<q.remove()<<endl;
  }

/*Purpose:  Display the ints in the file "in" in reverse order in which
          they appear in "in" and then display the ints in the order
          in which they appear in "in".
  PreConditions:  The file "in" is open for reading
                  The (rest of the) file "in" contains only ints
                  The (rest of the) file "in" has no more than 50 ints
  PostConditon: "in" is at the end of the file
*/

7.  (25 pts) As you know from experience, writing or reading beyond either
end of an array is a nasty error.  To ameliorate this problem create a class
SafeIntArray which stores ints and only allows access within the given bounds
of the array. In conjunction with the code below, your class should compile,
run, and produce the output between the dashed lines.
 #include <fstream.h>
 #include <stdlib.h>
 int main()
 { SafeIntArray list(20);
   for(int j=0;j<14;j++)
     list.store(j,2*j+3);
   cout<<list.get(3)<<"  "<<list.get(5)<<endl;
   list.get(27);
   //list.store(23,42);  should crash; array index out of bounds
 }
 /*------------------------------------
 9  13
 ERROR: array index out of bounds
 -------------------------------------*/
ANSWER
----------
 class SafeIntArray
 {public:
   SafeIntArray(int size);
   ~SafeIntArray();
   void store(int index,int value);
   int get(int index);
  private:
    int max,*data;
    SafeIntArray();
    void errCheck(bool b,char *mess);
 };

 SafeIntArray::SafeIntArray(){}
 SafeIntArray::~SafeIntArray()
 {delete []data;}
 SafeIntArray::SafeIntArray(int size)
 {errCheck(size<=0,"Bad size for array");
  max=size;
  data=new int[max];
  errCheck(data==NULL,"Heap overflow");
 }

 void SafeIntArray::store(int index,int value)
 {errCheck(index<0 || index>=max,"array index out of bounds");
  data[index]=value;
 }

 int SafeIntArray::get(int index)
  {errCheck(index<0 || index>=max,"array index out of bounds");
   return data[index];
  }

  void SafeIntArray::errCheck(bool b,char *mess)
  {if(b)
    {cerr<<"ERROR: "<<mess<<endl;
     exit(1);
    }
  }

8.  (25 pts)  Write a function location() which assumes an array of
ints is in ascending order and uses this information to efficiently
search for the index of some target.  If the target is not in the array,
location() returns -1.  If we have  int x[20],target,n; and we want
to find the index of 'target' among the first n entries in x, the call
to location() would be location(x,n,target).

ANSWER
---------
  int location(int x[],int n,int target)
  {do
    n--;
    while(n>=0 && x[n]>target);
   if(n<0 || x[n]!=target)
     return -1;
   return n;
   //*/ a more efficient (binary) search is below
  /*
    int bot,mid;
     bot=0;
     n--;
     while(n>bot+1)
     {mid=(n+bot)/2;
      if(x[mid]<target)
        bot=mid;
      else
        n=mid;
      }
      if(x[bot]==target)
        return bot;
      if(x[n]==target)
        return n;
      return -1;
  //*/
  }