CSE 109 Final Examination  Monday 5 April 2003
CLOSED BOOK. CLOSED NOTES.
<><><><><><><><><><><><><><SUGGESTED ANSWERS><><><><><><><><><>
1.  Given two unsorted lists of integers, one twice the length of the
other, and given the problem of writing a program to determine whether
any entry in one list is in the other list, determine the complexity
of the following algorithm as a function of the length of the lists.
     For each entry in the first list, scan the second list to see
     if it matches any entry in the second list.
Now assume both lists are in increasing order.  Write the code for a function
dup() which uses a more efficient algorithm than the one above and then
determine the (reduced) complexity of this algorithm.  Given int n,*list1,
*list2; the call dup(list1,list2,n) should return true if and only iff one of
the entries list1[0],..., list1[n-1] matches one of the entries list2[0],
... list2[2*n-1].
-------------------------------------------------------------
 a. For one element of the first list we have to search 2n elements of the
    second list for a potential match. But there are n elements in the first
    list.  This implies  n*2n operations ==> O(n^2).
 b.
 bool dup(int*a, int *b, int n)
{int aLoc,bLoc;
 aLoc=0;
 bLoc=0;
 while(aLoc<n && bLoc<2*n && (a[aLoc]!=b[bLoc]) )
  if(a[aLoc]<b[bLoc])
    aLoc++;
  else
    bLoc++;
 return aLoc<n && bLoc<2*n && a[aLoc]==b[bLoc];
}
The most frequent operation(s) are the comparison(s) controlling the while
loop. At the very worst, we repeat the loop n+2n+1=3n+1 times. Thus the
algorithm is O(n).

2.  Assume P is a postive prime number and we have the declaration
int hList[P];  Further assume that hList is a hash table of positive
numbers, where the numbers themselves serve as the hash numbers and
where a quadratic probe has been used to resolve collisions. Any entry
less than zero indicates an empty cell, i.e., a hash number has not yet
been placed in the cell.  Write an O(1) function inTable() such that
the call inTable(hList,P,4) returns true if and only if 4 is in hList,
inTable(hList,P,26) returns true if and only if 26 is in hList, etc.
-----------------------------------------------------------------------
//Precondition: target>0
bool inTable(int x[],int P, int target)
{int probe, loc;
 probe=0;
 while(probe<P/2 && x[(target+probe*probe)%P]>0
       && x[(target+probe*probe)%P]!=target)
    probe++;
 return x[(target+probe*probe)%P]==target;
}
3.  Assume you are to develop a template class for the Abstract Data
Type for a set.  Here I ask you to start developing the class by
writing a template that has sufficient functionality for the code
below to compile and produce the output indicated.  Recall that a
set is a collection of objects to which I can add objects and upon
which I can perform operations like union, complement, intersection,
etc.  Also I can ask whether the set contains a specific object. Once
an object is in the set, adding it again has no effect.
Set <int> x(10);
x+=3;
x+=3;
x+=209;
cout<<x<<endl; //  output: { 3 209 }
if(x.contains(3)) cout<<"Yes\n");   // output: Yes
if(!x.contains(12)) cout<<"Yes\n";  // output: Yes
-----------------------------------------------------------------
template <class T>
class Set
{public:
  Set(int n=100);
  ~Set();
  bool contains(const T & t)const;
  Set & operator+=(const T & t);
 template <class X>
 friend ostream & operator<<(ostream &out,const Set<X> &t);
  private:
   T *data;
   int size,max;
   static void assert(bool b, char *mess);
};

template <class X>
ostream & operator<<(ostream &out,const Set<X> & t)
{out<<"{";
 for(int j=0; j<t.size;j++)
  out<<" "<<t.data[j];
 out<<"}";
 return out;
}

 template <class T>
 Set<T>::Set(int n)
 {assert(n>0," Negative set size");
  data=new T[n];
  size=0;
  max=n;
  assert(data!=NULL,"Heap overflow");
 }

 template <class T>
 Set<T>::~Set()
 {delete [] data;}

 template <class T>
 Set<T> & Set<T>::operator+=(const T &t)
 {if(!contains(t))
    {assert(size<max-1,"Set overflow");
     data[size]=t;
     size++;
    }
    return *this;
 }

 template <class T>
 bool Set<T>::contains(const T &t)const
 {int loc;
  loc=0;
  while(loc<size && data[loc]!=t)
   loc++;
  return loc<size;
 }

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

4. For this and the next question we are concerned with a language whose
symbols are "LT", "GT", "EQ", "AND", "OR", and the digits '0', ..., '9', and
whose syntax is given by the diagrams below, where [] indicate a rectangular
box, and () indicate a circle and where legal expressions in the language are
those which satisfy diagram A.
  A                           B
  ----[B]---------------->    ----[C]-------------------->
          ^            |                 ^             |
          |            |                 |             |
          +--[B]--(OR)-+                 +--[C]--(AND)-+
  C
  ---+-[D]------(LT)---+
     |       |         |
     |       +--(GT)---+
     |       |         |
     |       +--(EQ)---+---[D]-+
     |                         |
     +---([)--[A]--(])---------+----->
  D is a single digit '0', ... '9'
Write a tokenizer for the above language, where the input to the tokenizer
is an array of strings.  In particular, the class Token, which you provide
in answering this question, enables the following code to compile, where
next() returns Token::DIGIT, Token::LESS, Token::GREATER, Token::EQ,
Token::OR, Token::AND, Token::LBRACK, or Token::RBRACK, corresponding to
the symbols in the above language, or returns Token::EOLN when there are no
more strings to process, or returns Token::JUNK otherwise.
 char *exp[]=
   {"9", "LT", "3", "AND", "[" "2", "EQ", "3", "OR", "4", "GT", "5", "]"};
   // 9<3 & {2=3 | 4>5]
 Token t(exp,13);  //13 strings in the list exp
 t.next();  //returns Token::DIGIT
 t.next();  //returns Token::LESS, etc.
------------------------------------------------------------------------
#include <fstream.h>

class Token
 {public:
      static int const DIGIT=0,LESS=1,GREATER=2,EQ=3,OR=4,AND=5,LBRACK=6,
       RBRACK=7,JUNK=8;
      Token(char *toks[],int count);
      int next();
      ~Token();
 private:
   Token(){} //forbid Token without arguments
      char **list;
      int loc,max;
   static void verify(bool b);
 };


void Token::verify(bool b)
{if(!b)
  {cerr<<"Error: Heap overflow\n";
   exit(1);
  }
}

Token::Token(char *toks[],int count)
{list=new char * [count];
 verify(list!=NULL); 
  for(int j=0;j<count;j++)
    {list[j]=new char(strlen(toks[j])+1);
     verify(list[j]!=NULL);
     strcpy(list[j],toks[j]);
    }
   loc=0;
   max=count;
}

Token::~Token()
{for(int j=0;j<max;j++)
  delete [] list[j];
 delete [] list;
}

int Token::next()
{if(loc>=max)
      return JUNK;
   loc++;
   if(strcmp(list[loc-1],"OR")==0)
     return OR;
   if(strcmp(list[loc-1],"AND")==0)
     return AND;
   if(strcmp(list[loc-1],"EQ")==0)
     return EQ;
   if(strcmp(list[loc-1],"LT")==0)
     return LESS;
   if(strcmp(list[loc-1],"GT")==0)
     return GREATER;
   if(strcmp(list[loc-1],"[")==0)
     return LBRACK;
   if(strcmp(list[loc-1],"]")==0)
     return RBRACK;
   if(list[loc-1][0]>='0' && list[loc-1][0]<='9' &&
      list[loc-1][1]=='0')
     return DIGIT;
   return JUNK;
}


5. Assume that class Token from the previous question functions as
advertised.  Write a program which uses class Token and determines whether
the strings entered on the command line obey the syntax of the above
syntax diagram for A, displaying "Yes" if they do and "No" if they do not.
For example, if the executable file for the program is "a.out", then
the commands
 a.out 6 LT 7 OR 9 GT 8
 a.out 6 EQ 7
 a.out [ 8 GT 0 ] OR [ 9 EQ 8 ]
would each display "Yes", because they satisfy the syntax of A, while
 a.out  [ M AND 6 ]
 a.out  [ 2 AND 3
 a.out  90 LT 20
 a.out  [6LT7]
would each display "No". (The last would display "No", because only one
string is read, and it is not a legitimate symbol.)
-----------------------------------------------------------------
 bool A(Token&t,int & tok);
 bool B(Token&t,int & tok);
 bool C(Token &t,int &tok);

 int main(int argCt, char *arg[])
 {Token t(arg,argCt);
  int tok;
  tok=t.next();  //path name of executable program
  tok=t.next();  //first "real" token
  if(A(t,tok) && tok==Token::EOLN)
   cout<<"Yes\n";
  else
   cout<<"No\n";
  return 0;
 }
  bool A(Token&t,int & tok)
  {if(!B(t,tok))
     return false;
   while(tok==Token::OR)
    {tok=t.next();
     if(!B(t,tok))
      return false;
    }
   return true;
 }

 bool B(Token&t,int & tok)
 {if(!C(t,tok))
    return false;
  while(tok==Token::AND)
   {tok=t.next();
    if(!C(t,tok))
      return false;
   }
  return true;
 }

 bool C(Token &t,int &tok)
 { if(tok==Token::LBRACK)
   {tok=t.next();
    if(!A(t,tok) || tok!=Token::RBRACK)
      return false;
    tok=t.next();
      return true;
   }
   if(tok!=Token::DIGIT)
      return false;
   tok=t.next();
   switch(tok)
   {case Token::LESS :
    case Token::GREATER:
    case Token::EQ: tok=t.next(); break;
    default: return false;
   }
   if(tok!=Token::DIGIT)
     return false;
   tok=t.next();
   return true;
 }

6. I created a class word with the following interface.
   class Word
   {public:
      Word(char *str="");
      ~Word();
      bool less(const Word & w)const; //am I less than w?
      bool equal(const Word & w)const; //am I the same as w?
    private:
      char *wd;
      static void assert(bool b,char *mess); //error message and exit if !b
   };
  Create a subclass of Word, OpWord, which implements the operators <, <=, <
  >=, ==, and != for instances of OpWord.  NOTE: You cannot change class Word.
-------------------------------------------------------------------------
class OpWord : public Word
{public:
  OpWord(char * str="");
  bool operator<(const OpWord & p)const;
  bool operator<=(const OpWord & p)const;
  bool operator>(const OpWord & p)const;
  bool operator>=(const OpWord & p)const;
  bool operator==(const OpWord & p)const;
  bool operator!=(const OpWord & p)const;
};
OpWord::OpWord(char * str):Word(str){}

bool OpWord::operator<(const OpWord & p) const
{return less(p);}

bool OpWord::operator<=(const OpWord & p) const
{return *this<p || *this==p;}

bool OpWord::operator>(const OpWord & p) const
{return p<*this;}

bool OpWord::operator>=(const OpWord & p) const
{return !(*this<p);}

bool OpWord::operator==(const OpWord & p) const
{return equal(p);}

bool OpWord::operator!=(const OpWord & p) const
{return !equal(p);}

7.  Given the class Node below, write a function same() which assumes that
we have declared  Node *root,*rootb; and root and rootb point to properly
constructed binary trees.  The call same(root,rootb) should return true
if and only if the trees to which root and rootb point have the same entries
in the same locations.
  class Node
  {public:
      int entry;
      Node *left,*right;
  };
-----------------------------------------------------------------------------
bool same(Node * a, Node * b)
{return a==NULL && b==NULL ||
    a!=NULL && b!=NULL &&
    a->entry==b->entry &&
    same(a->left,b->left) &&
    same(a->right,b->right);
}

8.  Modify the definition of class Word above and provide the definitions
(code) corresponding to the modifications so that the following code compiles
and produces the output indicated in the comment.
 Word a("Hello");
 a[0]='J';
 cout<<a<<endl; //output: Jello
-----------------------------------------------------------------------------
   class Word
   {public:
      Word(char* str="");
      ~Word();
      bool less(const Word & w)const;
      bool equal(const Word & w)const;
      friend ostream &operator<<(ostream & out,const Word & w); //NEW ADDITION
      char & operator[](int index); //NEW ADDITION
    private:
      char *wd;
      static void assert(bool b,char*mess);
   };

ostream &operator<<(ostream & out,const Word &w)
{out<<w.wd;
return out;
}

char & Word::operator[](int index)
{assert(index>=0 && index<strlen(wd),"Index out of range");
 return wd[index];
 }