CSc 109 Final Examination     Friday  18 May 2001
   SUGGESTED ANSWERS

   1.  Suppose we added the symbol ">>" to the syntax of bool expression in
   the Simple Language.  In particular, <exp1> >> <exp2> would be true if the
   absolute value of <exp1> is >= the absolute value of <exp2).  Also suppose
   that the virtual stack starts at FF and "goes down" in memory. Finally,
   suppose that the values of <exp1> and <exp2> are stored on the virtual
   stack, <exp1> at StkPtr+2 and <exp2> at StkPtr+1. Write the function
   GREATABS() which stores in a file the Simple Machine code which
   should be generated for the expression
       IF <exp1> >> <exp2> GOTO ONE
   where the code for evaluating and storing <exp1> and <exp2>) on the virtual
   stack has already been generated.  The call to GREATABS() would take the
   form
      GREATABS(out,StkPtr,PC,ONE_ADD);
   where "out" is of type ostream, StkPtr, PC, and ONE_ADD are integers.  PC
   gives the current value of the program counter (the number of words of
   Simple Machine code generated so far), and ONE_ADD is the address
   corresponding to the Simple Language variable "ONE".  This question is
   similar to question 4 on test 2.  There you were asked to write the
   sasm code; here you are asked to write the C++ code which generates the
   simple machine code.
   Hint:  You would be wise to write some functions to call.

       void digit(ostream &out,int d){
          if(d<10)
            cout<<d;
          else
            cout<<char('A'+d-10);
       }

       void genCode(ostream &out,int &PC, int op, int add){
        digit(out,op);
        digit(out,add/16);
        digit(out,add%16);
        PC++;
        if(PC>255){
          cerr<<"Code overflow";
          exit(1);
        }
        out<<endl;
       }

       void GREATABS(ostream &out,int &StkPtr, int &PC,int add){
        const int LOAD=3,MULT=7, SUB=6, BRANCHGE=10;
        genCode(out,PC,LOAD,StkPtr+2);
        genCode(out,PC,LOAD,StkPtr+2);
        genCode(out,PC,MULT,0);
        genCode(out,PC,LOAD,StkPtr+1);
        genCode(out,PC,LOAD,StkPtr+1);
        genCode(out,PC,MULT,0);
        genCode(out,PC,SUB,0);
        genCode(out,PC,BRANCHGE,add);
        StkPtr+=2;  //pop values of <exp1> and <exp2> off the virtual stack
       }
   2.  (This question and question 3 are related. Design your answer to this
   question so that it can be used in question 3.) Write a template class
   PRay for "protected arrays."  A protected array does not let you access
   entries outside the preset bounds of the array.  For such a class the
   following code should compile, but should crash at runtime, because it
   accesses entries outside the bounds of the array.

      PRay<double,-3,10> x;  //only allow x[-3], x[-2], ... x[10]

      for(int j=5; j<9;j++)
        x[j]=j*j+0.01;
      for(int j=7; j<12; j++)
        cout<<x[j]<<endl;    //CRASH HERE WHEN J==11

   #include <fstream.h>
   #include <stdlib.h>
   #include <math.h>

   template <class T,int lo, int hi>
   class PRay{
   public:
     PRay();
     PRay(const PRay & p);
     T & operator[] (int n);
   protected:
     T ray[hi-lo+1];
     static void check(bool ok,char *mess);
   };

   template <class T,int lo, int hi>
   PRay<T,lo,hi>::PRay(){
   }

   template <class T,int lo, int hi>
   PRay<T,lo,hi>::PRay(const PRay<T,lo,hi> & p){
     for(int j=0;j<hi;j++)
         ray[j]=p.ray[j];
   }

   template <class T,int lo, int hi>
   T & PRay<T,lo,hi>::operator[](int n){
     check(n>=lo && n<=hi,"([]) Range error");
     return ray[n-lo];
   }

   template <class T, int lo, int hi>
   void PRay<T,lo,hi>::check(bool ok,char *mess){
     if(!ok){
         cerr<<"ERROR: "<<mess<<endl;
         exit(1);
     }
   }

   3.  Write a template subclass, OPRa, of the class PRay above.  An
   instance of OPRa stores the number of actual entries in the array,
   starting at the lower bound.  Instances of OPRa have a member function
   sort() which sorts the first n entries in the array.  For such a class
   the following code should compile and produce the output which appears
   in the comments. (I am tempted to ask you to create a second subclass
   WINfree, but I will resist.)

     OPRa<int,3,10> x;  //only allow x[3], x[4], ... x[10]
     for(int j=3; j<9;j++)
       x[j]=abs(30-j*j);
     x.setN(6);
     x.sort();
     cout<<"I sort "<<x.getN()<<" entries to get\n";
     for(int j=3;j<9;j++)
       cout<<x[j]<<endl;

     /*
     I sort 6 entries to get
     5
     6
     14
     19
     21
     34      */

   template <class T, int lo, int hi>
   class OPRa: public PRay<T,lo,hi>{
   public:
     OPRa();
     OPRa(const OPRa & op);
     void sort();
     int getN();
     void setN(int j);
   private:
     int n;
   };

   template <class T, int lo, int hi>
   OPRa<T,lo,hi>::OPRa(){
     n=0;
   }

   template <class T, int lo, int hi>
   OPRa<T,lo,hi>::OPRa(const OPRa & op): PRay<T,lo,hi>(){
     n=0;
   }

   template <class T, int lo, int hi>
   void OPRa<T,lo,hi>::sort(){
     bool done;
     int loc;
     do{
       done=true;
       for(int j=0; j<n-1;j++)
         if(ray[j]>ray[j+1]){
           T temp=ray[j];
           ray[j]=ray[j+1];
           ray[j+1]=temp;
           done=false;
         }
     }while(!done);
   }

   template <class T, int lo, int hi>
   void OPRa<T,lo,hi>::setN(int j){
     check(j>=0 && j<=hi-lo+1,"(setN() Bad value of n");
     n=j;
   }

   template <class T, int lo, int hi>
   int OPRa<T,lo,hi>::getN(){
     return n;
   }

   4.  Below, for two different tables, I ask you to depict, step-by-step, the
   probes made when an item is put in a hash table using a quadratic probe.
   Both tables have the same three entries in the same three places, but the
   first table has room for 8 entries, and the second has room for 11 entries.
   Suppose we probe until a place is found.  State which of the two tables
   below is inappropriate for using a quadratic probe and state why it is
   inappropriate.

     The table with 8 entries is innapropriate, because the quadratic probe
     is only guaranteed to be effective when the size of the table is prime.
     When the size is prime, then the quadratic probe will search at least
     half the table before probing the same location twice.

   Assume the word "Tom" produces the hash number 91.  For each table below
   list, in order, the first 10 locations probed when trying to find a place
   to store "Tom", using a quadratic probe.  If it takes fewer than 10 probes,
   list the complete sequence.

      Table 1              Table 2
      -------              -------
      0                    0
      1                    1
      4                    2
      3 "COLD"             3 "COLD"
      4 "HOT"              4 "HOT"
      5                    5
      6                    6
      7 "Hal"              7 "Hal"
                           8
                           9
                          10

    In Table 1.  91%8 == 3.  Thus we probe 3, 3+1=4, 4+3=7, 7+5=12%8=4,
       4+7=11%8=3, 3+9=12%8=4, 4+11=15%8=7, 7+13=20%8=4, 4+15%8=3,
       3+17=20%8=4.  Gee, this may never quit.  I tried 10 times....

    In Table 2.  91%11=3.  Thus we probe 3, 3+1=4, 4+3=7, 7+5=12%11=1
       a free space.  Store "Tom" in location 1.

   5.  Write a program that simulates recursion for the following algorithm
   for finding the nth fibonacci number:
       int fib(int n){
         if(n<=1)
           return 1;
         else
           return fib(n-1)+fib(n-2);
   I provide the main program; you provide the rest.
      int main(){
         int n;
         cout<<"Enter n, and I find fibonacci(n)- ";
         cin>>n;
         cout<<fib(n)<<endl;
         return 0;
      }
   YOUR JOB IS NOT TO FIND A BETTER ALGORITHM BUT TO SIMULATE THE RECURSION
   OF THE ALGORITHM GIVEN.  YOUR PROGRAM SHOULD MAKE NO RECURSIVE CALLS.

   #include <fstream.h>
   #include "stack.h"
   #include "fibstack.h"

   const int START=0, PUSH=1, POP=2, EXEC=3, QUIT=4;

   class Frame{
   public:
     int n, left, right, result, PC;
   };

   int fib(int n);
   void pop(FibStack<Frame,100> & st, int &state);
   void start(FibStack<Frame,100> & st,int &state, int n);
   void exec(FibStack<Frame,100> &st, int &state);
   void push(FibStack<Frame,100> &st, int &state);

   int fib(int n){
    FibStack<Frame,100> st;
    int state;

    state=START;
      while(state!=QUIT)
        switch(state){
            case START: start(st,state,n); break;
            case EXEC: exec(st,state); break;
            case PUSH: push(st,state); break;
            case POP: pop(st,state); break;
        }
    return st.discarded().result;
   }

   void pop(FibStack<Frame,100> & st, int &state){
    st.pop();
     if(st.empty())
        state=QUIT;
     else
       state=EXEC;
   }

   void start(FibStack<Frame,100> & st,int &state, int n){
    Frame f;
      f.n=n;
      f.PC=0;
      st.push(f);
      state=EXEC;
   }

   void exec(FibStack<Frame,100> &st, int &state){
    switch(st.peek().PC){
      case 0: if(st.peek().n<=0){
              st.peek().result=1;
              state=POP;
              }
              else
               state=PUSH;
              break;
      case 1:
          st.peek().left=st.discarded().result;
          state=PUSH;
          break;
      case 2:
          st.peek().right=st.discarded().result;
          st.peek().result=st.peek().left+st.peek().right;
          state=POP;
    }
   }

   void push(FibStack<Frame,100>&st,int &state){
    Frame f,peek;
    peek=st.peek();
    switch(peek.PC){
      case 0: f.n=peek.n-1;
              f.PC=0;
              st.peek().PC=1;
              break;
      case 1: f.n=peek.n-2;
              f.PC=0;
              st.peek().PC=2;
              break;
      default: cout<<"Programmer error (push 0)"; exit(2);
    }
    st.push(f);
    state=EXEC;
   }

#ifndef STACK_H
#define STACK_H

#include <stdlib.h>
template <class T,int stSize>
class Stack{
public:
  Stack(const Stack & st);
  Stack();
  T & peek();
  T pop();
  void push(const T &t);
  bool empty();
  bool full();
protected:
  T stk[stSize];
  int max,ptr;
  static void check(bool ok,char *mess);
};

template <class T,int stSize>
Stack<T,stSize>::Stack(){
  ptr=-1;
  max=stSize;
}

template <class T,int stSize>
void Stack<T,stSize>::check(bool ok, char *mess){
  if(!ok){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}

template <class T,int stSize>
Stack<T,stSize>::Stack(const Stack &st){
  check(stSize==st.max,"(Stack(Stack)) Mismatch of stack size");
  ptr=st.ptr;
  max=stSize;
  for(int j=0;j<=ptr;j++)
    stk[j]=st.stk[j];
}

template <class T, int stSize>
T & Stack<T,stSize>::peek(){
  check(ptr>=0,"(peek()) Empty stack");
  return stk[ptr];
}

template <class T, int stSize>
T Stack<T,stSize>::pop(){
  check(ptr>=0,"(peek()) Empty stack");
  ptr--;
  return stk[ptr+1];
}

template <class T, int stSize>
bool Stack<T,stSize>::full(){
  return ptr>=max-1;
}

template <class T, int stSize>
bool Stack<T,stSize>::empty(){
  return ptr<0;
}

template <class T,int stSize>
void Stack<T,stSize>::push(const T &t){
  check(ptr<max-1,"(push(T)) Full stack");
  ptr++;
  stk[ptr]=t;
}

#endif


   6. Write a program which checks to see whether there is at least two command
   line arguments.  If there are fewer than two arguments, it diagnoses an
   error and quits. If there is a second argument, the program checks to see
   whether the file exists. If it does not, it opens a file of that name for
   output.  If it does exist, it copies the file to a file which has the name
   of the original file with the string ".BAK" appended, and then opens the
   file for output.  Finally, it stores the string "SUCCESS" in the output file
   and closes it.

   #include <fstream.h>
   #include <string.h>

   void check(bool ok,char *mess){
     if(!ok){
       cerr<<"ERROR: "<<mess<<endl;
       exit(1);
     }
   }

   void copyfile(ifstream &in,char*name){
     ofstream temp;
     char *cpName,ch;
     cpName=new char[strlen(name)+5];
     check(cpName!=NULL,"Heap overflow");
     strcpy(cpName,name);
     strcat(cpName,".BAK");
     temp.open(cpName);
     check(temp.good(),"Failure to open backup file");
     ch=in.get();
     while(in.good()){
       temp.put(ch);
       ch=in.get();
     }
     temp.close();
   }

   int main(int argct,char *arg[]){
     check(argct>=2,"Too few command line arguments");
     ifstream test;
     ofstream out;
     test.open(arg[2]);
     if(test.good()){
       copyfile(test,arg[2]);
       test.close();
     }
     out.open(arg[2]);
     out<<"SUCCESS"<<endl;
     out.close();
   }


   7.  Write the declaration and definitions (code) for a class Dictionary.
   An instance of Dictionary stores word pairs with the member function
   atPut(), retrieves the second member of a stored pair with the member
   function at(), and removes pairs with the member functin remove().  With
   your class Dictionary, the code below should create a Dictionary which
   can hold up to 50 entries and should produce the output in the comments.
   You may assume that the you can include word.h and word.cc, the files
   for class Word, which I made available for p8.
     Dictionary french(50);
     french.atPut("One","un");
     french.atPut("Two","deux");
     cout<<french.at("One")<<" "<<french.at("Two")<<endl;
     french.remove("One");
     cout<<french.at("One")<<" "<<french.at("Two")<<endl;
     /*
     un deux
     NULL-WORD deux  */
   #include <fstream.h>
   #include "word.cc"

   class Rek{
    public:
     Word key,entry;
     Rek();
     Rek(const Rek &r);
   };

   Rek::Rek(){
    key=NULL;
    entry=NULL;
   }

   Rek::Rek(const Rek &r){
     key=Word(r.key);
     entry=Word(r.entry);
   }

   class Dictionary{
    public:
     Dictionary(int n=100);
     Dictionary(const Dictionary &d);
     ~Dictionary();
     Word at(char *key)const;
     void atPut(char *key,char *entry);
     void remove(char *key);
    private:
     int size,count;
     int locate(char *key)const;
     static void check(bool ok, char *mess);
     Rek **table;
   };

   Dictionary::Dictionary(int n){
    check(n>0,"(Dictionary(int)) non-positive argument");
    size=n;
    count=0;
    table=new Rek *[n];
    check(table!=NULL,"(Dictionary(int)) Heap overflow");
    for(int j=0;j<n;j++)
      table[j]=NULL;
   }

   Dictionary::Dictionary(const Dictionary &d){
    size=d.size;
    count=d.count;
    table=new Rek *[size];
    check(table!=NULL,"(Dictionary(int)) Heap overflow");
    for(int j=0;j<count;j++){
      table[j]=new Rek(*(d.table[j]));
      check(table[j]!=NULL,"(Dictionary(Dictionary) Heap overflow");
    }
    for(int j=count;j<size;j++)
      table[j]=NULL;
   }

   Dictionary::~Dictionary(){
    for(int j=0; j<count; j++)
     delete table[j];
    delete [] table;
   }

   Word Dictionary::at(char *key)const{
    int loc;
    loc=locate(key);
    if(loc>=count)
      return Word(NULL);
    return Word(table[loc]->entry);
   }

   void Dictionary::atPut(char *key, char *entry){
     int loc;
     loc=locate(key);
     if(loc<count)
       table[loc]->entry=entry;
     else{
       table[count]=new Rek();
       check(table[count]!=NULL,"(atPut()) Heap overflow");
       table[count]->key=key;
       table[count]->entry=entry;
       count++;
     }
   }

   void Dictionary::remove(char *key){
    int loc;
    loc=locate(key);
    check(loc>=0 && loc<count,"(remove()) Missing key");
    for(int j=loc;j<count-1;j++)
     table[j]=table[j+1];
    delete table[count];
    table[count]=NULL;
    count--;
   }

   int Dictionary::locate(char *key)const{
    int loc;
    loc=0;
    while(loc<count && !(table[loc]->key==key))
      loc++;
    return loc;
   }

   void Dictionary::check(bool ok, char *mess){
    if(!ok){
      cerr<<"ERROR[Dictionary]: "<<mess<<endl;
      abort();
    }
   }

   8.  Write the declarations and definitions (code) for a class Parse which
   peforms a recursive descent parse on strings of characters, based on the
   syntax diagrams below.  Instances of class Parse should read from cin and
   send output to cout.  With your class Parse the code below should take
   the string of characters entered by the user and should write "The string
   is acceptable" if the string satisfies the syntax of the diagrams below;
   otherswise it should write "The string is not acceptable."

   Parse p;
   cout<<"Enter a string- ";
   p.parse();

   Note: In these diagrams [] denotes a box and () denotes a circle.

    S      ----------->(5)--->[A]--->[B]------------------>
             |
             +-------->[A]--->[S]------------------------->
             |
             +-------->[B]--->[S]------------------------->

    A      ------->(1)--->[A]--->[B]---------------------->
             |
             +---->(2)------------------------------------>

    B      ------->(3)--->[A]--->[S]---------------------->
             |
             +---->(4)------------------------------------>

   #include <fstream.h>

   class Parse{
   public:
     Parse();
     void parse();
   private:
     char ch;
     bool s();
     bool a();
     bool b();
     void getch();
   };

   Parse::Parse(){}

   void Parse::parse(){
     getch();
     if(s() && ch=='\n')
       cout<<"String is acceptable\n";
     else
       cout<<"String has an error\n";
   }

   bool Parse::s(){
     switch(ch){
      case '1':
      case '2': return (a() && s());
      case '3':
      case '4': return (b() && s());
      case '5': getch(); return(a() && b());
      default: return false;
     }
   }

   bool Parse::a(){
    switch(ch){
     case '1': getch(); return(a() && b());
     case '2': getch(); return true;
     default: return false;
    }
   }

   bool Parse::b(){
     switch(ch){
      case '3': getch(); return(a() && s());
      case '4': getch(); return true;
      default: return false;
     }
   }

   void Parse::getch(){
     if(cin.good())
       cin.get(ch);
     if(!cin.good())
       ch='\n';
   }