CSc 109 Final Examination Sunday  12 May 2002
>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1. (25 pts) I am interested in a class, CheckList, whose instances keep
track of whether instances of some class have been added or removed from the
CheckList.  By default, the CheckList can hold up to 100 items, but an
instances of CheckList of other sizes can be created.  One can add an
item to a CheckList with the += operator (which does nothing if the
item has been previously added, one can remove an item with the -= operator
(which does nothing if the item is not in the CheckList), and one can ask
whether an item is in the CheckList with the inList() function.  Below is
some code using the class. Write a template for class CheckList.
int main()
{ CheckList<int> a(200),b;
  CheckList<double> d;
  a+=3;
  a+=2000;
  a+=2000;
  if(a.inList(2000)) cout<<"2000 is in the list\n";//should print
  b+=5;
  a-=2000;
  if(!a.inList(2000)) cout<<"2000 is not in the list\n";//should print
  return 0;
}
==========================
#include <fstream.h>

template <class T>
class CheckList
{public:
  CheckList(int j=100);
  ~CheckList();
  CheckList & operator+=(const T &j);
  CheckList& operator-=(const T &j);
  bool inList(const T &j)const;
private:
  T **table;
  int size,count;
  void err(bool b, char *mess);
};


template <class T>
CheckList<T>::CheckList(int j)
{err(j<1,"Bad size");
size=j;
count=0;
table=new T*[size];
err(table==NULL,"Heap overflow");
for(int j=0;j<size;j++)
  table[j]=NULL;
}

template <class T>
CheckList<T>::~CheckList()
{for(int j=0;j<count;j++)
  delete table[j];
 delete [] table;
}

template <class T>
CheckList<T> & CheckList<T>::operator+=(const T &j)
{int loc=0;
 while(loc<count && *table[loc]!=j)
   loc++;
 if(loc<count)
 return *this;
 err(count>=size,"CheckList overflow");
 table[loc]=new T(j);
 err(table[loc]==NULL,"Heap overflow");
 count++;
 return *this;
}

template <class T>
CheckList<T> & CheckList<T>::operator-=(const T &j)
{int loc=0;
 while(loc<count && *table[loc]!=j)
   loc++;
 if(loc>=count)
 return *this;
 delete table[loc];
 for(int j=loc;j<count-1;j++)
  table[j]=table[j+1];
 table[count-1]=NULL;
 count--;
 return *this;
}

template <class T>
bool CheckList<T>::inList(const T &t)const
{for(int j=0;j<count;j++)
  if(*table[j]==t)
    return true;
return false;
}

template <class T>
void CheckList<T>::err(bool b, char *mess)
{if(b)
  {cerr<<"ERROR: "<<mess<<endl;
  exit(1);
  }
}

int main()
{ CheckList<int> a(200),b(0);
  a+=3;
  a+=2000;
  a+=2000;
  if(a.inList(2000)) cout<<"2000 is in the list\n";//should print
  b+=5;
  a-=2000;
  if(!a.inList(2000)) cout<<"2000 is not in the list\n";//should print
  return 0;
}


2.  (35 pts)  Write a class Parse, which checks whether a line of text entered
at the console satisfies the syntax of the diagram for EXP below, diagnoses
the first error, if any, and, if the syntax is correct, generates a StakMach
program which reads in int values to x and y and then writes the resulting
value when evaluating the line of text. An error free line of text should have
no blanks or tabs and should terminate with a '\n'. Below I show a sample line
of text and the StakMach code generated.  Below that I show how Parse is used,
and then I show the syntax diagram. (Hints: you only need space for x and y.
This space can be allocated at the beginning of the code, as I did in the
example below.  This means no program counter is needed, and only one pass
is needed.  Octal output can be handled with / and % by 8, 64, etc.)
Text:  x*y
Code:  -5003
       0000
       0000
       3000
       -4001
       3000
       -4002
       4001
       4002
       2000
       -3000
       0000
       E

Prog:  int main()
       {ofstream code("out.code");
        Parse p(code);
        p.parse();
        code.close();
        return 0;
       }

   ( () indicates a circle, [] indicates a rectangle )

   EXP
   ---------[TERM]--------------------+------->
                    ^                 |
                    |        |--(*)---|
                  [TERM]<----+--(+)---+
   TERM
   ----------(x)---------------->+
         |---(y)---------------->|
         +----(()-->[EXP]-->())--+---------->

   HALT=0,ADD=1,SUB=-1,MUL=2,DIV=-2,READ=3,WRITE=-3,PUSH=4,POP=-4,PUSHI=5,
   JMP=-5,JMPL=6,JMPG=-6,JMPE=7,JMPNE=-7
==================================================================
#include <fstream.h>
#include <stdlib.h>

class Parse
{public:
  Parse(ostream &out=cout);
  void parse();
  void exp();
private:
  static const int
  HALT=0,ADD=1,SUB=-1,MUL=2,DIV=-2,READ=3,WRITE=-3,PUSH=4,POP=-4,PUSHI=5,
    JMP=-5,JMPL=6,JMPG=-6,JMPE=7,JMPNE=-7;
  char ch;
  ostream *code;
  void genCode(int op,int addr);
  void term();
  void errCheck(bool b,char *mess);
  void getch();
};

int main()
{ofstream code("out.code");
 Parse p(code);
  p.parse();
  code<<"E";
 code.close();
   return 0;
}

Parse::Parse(ostream &out)
{code=&out;
}

void Parse::getch()
{cin.get(ch);
 cout<<ch;
}

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


void Parse::genCode(int op,int addr)
{*code<<op<<(addr/64)<<(addr%64/8)<<(addr%8)<<endl;}

void Parse::parse()
{
 genCode(JMP,3);//leave room for x(Memloc=1) and y(Memloc=2)
 genCode(0,0);  //blank space for x
 genCode(0,0);  //blank space for y
 genCode(READ,0);
 genCode(POP,1);
 genCode(READ,0);
 genCode(POP,2);
 getch();
 exp();
 errCheck(ch!='\n',"End of line expected");
 genCode(WRITE,0);//presume result of exp() left on stack
 genCode(HALT,0);
}

void Parse::exp()
{term();
 while(ch=='*' || ch=='+')
   {char saveCh=ch;
    getch();
    term();
    if(saveCh=='*')
      genCode(MUL,0);
    else
      genCode(ADD,0);
   }
}

void Parse::term()
{switch(ch)
  {case 'x': genCode(PUSH,1); break;
  case 'y': genCode(PUSH,2);  break;
  case '(': getch(); exp(); errCheck(ch!=')',"')' expected");
            break;
  default: errCheck(true," 'x', 'y', or '(' expected");
  }
 getch();
}

3.  (10 pts)  In the two hash tables below integers were added using the
integer itself for the hash number and using a quadratic probe to resolve
collisions. In the first table show why adding the number 96 is problematic.
In the second table, show where the number 79 would be stored.  Finally,
explain why the first table is not a good hashtable while the second one is.

      0   1   2   3   4   5   6   7   8   9  10  11
    -------------------------------------------------
    | 24| 37|   |   | 52|   |   |   |   | 69|   |   |
    -------------------------------------------------

      0   1   2   3   4   5   6   7   8   9  10
    ---------------------------------------------
    |101|   | 23| 46|   |   | 57| 68|   |   |   |
    ---------------------------------------------
========================================================================
  Using the quadratic probe, 96 hashes to the following sequence of locations:
  0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1, ....  It looks like it always looks
  at the locations 0, 1, 4, 9

  Using the quadratic probe, 79 hashes to the following sequence of locations:
  2, 3, 6, 0, 7, 5.   Store at 5.

  A size of a good table should be prime.  The first table has size 12, which
  is not prime, while the second table has size 11, which is prime.  When a
  table size is not prime a quadratic probe fails to have the property that
  at least half the table will be probed before the same place is probed
  twice.
4.  (10 pts) Assume a hash table of positive ints has been created with a
quadratic probe, assume that the ints themselves are used for the hash number,
assume there are no deletions, and assume that -1 indicates an emtpy location.
Write a function inTable() which uses a quadratic probe to determine
whether an int is in the table.  For example, given the delaration
    int table[17];
the call  inTable(table,17,49)  should return true if and only if the
number 49 is in the hashtable 'table,' which is of size 17.
======================================================================
#include <fstream.h>


//assume that if half the table is probed and item is not found
//the item is not there
bool inTable(int table[],int size,int item)
{int probe;
  probe=0;
  while(probe < size/2 &&
               table[(item+probe*probe)%size]!=item &&
               table[(item+probe*probe)%size]!=-1)
    probe++;
  return table[(item+probe*probe)%size]==item;
}

int main()
{int table[]={101, -1, 23, 46, -1, 79, 57, 68, -1, -1, -1};

 cout<<inTable(table,11, 79)<<endl;
}


5.  (10 pts)  Each question below refers to the following B-Tree of order 2
    (designed for up to 2*2=4 elements per node).
                   _______________________________________
                   15                                   60
                 /                    |                   \
               /                      |                    \
             /                        |                     \
       ________            _______________________           \_________
       6     12            22  28   35          50             80    90
      /   |    \          /   | __|__ |           \           |    |   \
     /    |     \        |    | 29 30 |            \          |    |    \
  __/_   _|_  ___\__   __|__  |____  _|_________   _|___   __/__  _|___  \____
  4  5   7 8   13 14   17 19  23 24  37 39 40 41   51 53   78 79  85 86  95 96


   a.  Show what the above tree looks like after the number 38 is added,
   where the balance is maintained using the alogorithm for B-tree insertion
   discussed in class.
================================================================
                   _______________________________________
                   15                35                 60
                 /           |              |             \
               /             |              |              \
             /               |              |               \
       ________            __|___        ___|_____           \_________
       6     12            22  28        39     50             80    90
      /   |    \          /   | __|__   /    |    \           |    |   \
     /    |     \        |    | 29 30  /     |     \          |    |    \
  __/_   _|_  ___\__   __|__  |____  _|___  _|___  _|___   __/__  _|___  \____
  4  5   7 8   13 14   17 19  23 24  37 38  40 41  51 53   78 79  85 86  95 96

   b.  Starting with the first tree above, show what the tree looks like after
   the number 13 is removed from the tree, where balance is maintained using
   the algorith for B-tree deletion discussed in class.
===========================================================================
                   _______________________________________
                   22                                   60
                 /                    |                   \
               /                      |                    \
             /                        |                     \
       ______________         ____________________           \_________
       6           15          28   35          50             80    90
      /   |          \        | __|__ |           \           |    |   \
     /    |           \       | 29 30 |            \          |    |    \
  __/_   _|_______     \____  |____  _|_________   _|___   __/__  _|___  \____
  4  5   7 8 12 14     17 19  23 24  37 39 40 41   51 53   78 79  85 86  95 96

6.  (10 pts)  Given the class A declared below, create a subclass B which has a
single prototype and single definition overloading "+" so that the code in
main() compiles and produces the output indicated.
class A
{public:
  A(int j=0);
  friend ostream & operator<<(ostream &out,const A &a);//simply print data
 protected:
  int data;
};
int main()
{B a(2),b(3);
 cout << (a+5) << (5+b) << (a+b) << endl;
  //prints out   785
}
======================================================
class B : public A
{public:
  B(int j=0);
  friend B  operator+(const B&b1,const B &b2);
};


B::B(int j):A(j){}

B operator+(const B&b1,const B&b2)
{return B(b1.data+b2.data);}