CSE 109   Final Examination   Tuesday  12 December 2002
**************SUGGESTED ANSWSERS***************************
1. Write a template class for the ADT "Range."  Objects of type Range store
lists of objects of some type and return the maximum and minimum entry in
the list.  For example, the following code should produce the output indicated.
   Range <double> r(20);  //hold a maximum of 20 entries
   r+=4.2;
   r+=12;
   r+=-5;
   cout<<r.max()<<" "<<r.min(); //displays: 12 -5
==============================================================
#include <fstream.h>
#include <stdlib.h>
template <class T>
class Range
{public:
  Range(int m=100);
  ~Range();
  T max();
  T min();
  Range & operator+=(T a);
 private:
   T *list;
   int size,count;
   static void assert(bool b,char *mess);
};

template <class T>
Range<T>::Range(int m)
{assert(m>0,"(Range(int)) Need m>0");
 list=new T[m];
 assert(list!=NULL,"(Range(int))Heap overflow");
 size=m;
 count=0;
}

template <class T>
Range<T>::~Range()
{delete [] list;}

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

template <class T>
Range<T>& Range<T>::operator+=(T a)
{assert(count<size,"(Range +=) List overflow");
 list[count]=a;
 count++;
 return *this;
}


template <class T>
T Range<T>::max()
{assert(count>0,"(Range::max()) Empty list");
 T big;
 big=list[0];
 for(int j=1; j<size;j++)
  if(list[j]>big)
   big=list[j];
 return big;
}

template <class T>
T Range<T>::min()
{assert(count>0,"(Range::max()) Empty list");
 T small;
 small=list[0];
 for(int j=1; j<size;j++)
  if(list[j]<small)
   small=list[j];
 return small;
}

2.  Below is the main program from my implementation of asm2f, except that the
commented line was not there.  One of you discovered a bug when he wrote:
'asm2f input out input'  In particular, the file 'input' got wiped out and the
program crashed.  I could have repaired that and similar problems by rewriting
openFiles().  Instead I chose to add the function screen() indicated in the
commented line. Write the protoytpe and definition of screen() so that when
such problems occur the program terminates.  When there is no problem, screen()
does nothing and returns.
  int main(int ct,char **arg)
  {ifstream fin;
   ostream fout,fcode;
   //screen(ct,arg);
   openFiles(fin,fout,fcode,ct,arg);
   FullParser  p(fin,fout,fcode;
   p.parse();
  }
=============================================================
void screen(int ct, char **arg)
{if(ct!=4)
   exit(1);
 for(int j=0; j<ct; j++)
   for(int k=j+1; k<ct; k++)
      if(strcmp(arg[j],arg[k])==0)
       exit(2);
}

3. Your goal is to write a class for parsing and evaluating expressions which
satisfy the syntax diagrams and algebraic rules given in question 4.
In this question you should write a tokenizer for such expressions; in the
next question you should write the parser-evaluator for such expressions.
Your tokenizer should read input from a file.  The only legitimate characters
are '0', '1', '+', '*', '^', '(', and ')'.  Tabs, blanks, and '\n' should be
ignored.  Since all the items being tokenized are single characters, the
call to member function next() should return a character, either the character
being tokenized or the '$' when anything else besides a blank, tab, or '\n'
is encountered. The '$', i.e., any illegitimate character, signifies the end
of an expression.  Given the declaration  ifstream f;  THe creation of an
instance of the tokenizer would be Token t(f);   The only function you need
provide is next() which returns the next token.  Note that any piece of
"junk," including EOF is interpreted
as '$'.
=================================================================
class Token
{public:
  Token(istream &in);
  char next();
 private:
   char buff,ch;
   istream *fin;
};

Token::Token(istream &in):fin(&in)
{buff=in.get();}

char Token::next()
{while(fin->good() && (buff==' ' || buff=='\t' || buff=='\n'))
   buff=fin->get();
 if(!fin->good())
  ch='$';
 else switch(buff)
 {case '+':
  case '*':
  case '^':
  case '(':
  case ')':
  case '1':
  case '0': ch=buff; break;
  default: ch='$';
 }
 buff=fin->get();
 cout<<ch;  //echo input? problem does not say
 return ch;
}

4.  The syntax of the expressions alluded to in question 3 are given below.
Expressions are evaluated according to the following rules: 0+0 = 0,
0+1 = 1+0 = 1+1 = 1, 0*0 = 0*1 = 1*0 = 0, 1*1 = 1, 1^0 = 0^1 = 1, 0^0 = 1^1 = 0.
'^' has precedence over '*', which has precedence over '+', and parentheses ()
have the usual precedence.  In the diagrams, [] indicates a 'box' and {}
indicates a circle. An expression is legitimate if it satisfies the syntax
diagram for A.
  A                          B                         C
  ---[B]-------------+-->   ---[C]-------------+-->   ---[D]-------------+-->
        ^            |            ^            |            ^            |
        |<-[B]<-{+}<-+            |<-[C]<-{*}<-+            |<-[D]<-{^}<-+
  D
  ---------+---{1}------------+
           |---{0}------------|
           +---{(}--[A]--{)}--+------>
Write a class Parser for which objects of type Parser respond to the function
parse() by returning the value of an expression satisfying the above diagrams.
If the expression does not satisfy the diagrams, then you should simply exit
the program. The Parser class should assume that the class Token described in
question 3 exists.  Given the declaration ifstream f; the class Parser would
be used as follows:
    Parser p(f);
    int x;
    x=p.parse();//get the value of the expression in the file f
=========================================================================
class Parser
{public:
   Parser(istream &in);
   int parse();
 private:
   int A();
   int B();
   int C();
   int D();
   Token t;
   char sym;
   istream *fin;
};

Parser::Parser(istream &in):t(in)
{}

int Parser::parse()
{sym=t.next();
 if(sym!='$')
   exit(4);
 return A();
}

int Parser::A()
{int temp;
 temp=B();
 while(sym=='+')
 {sym=t.next();
  temp=temp+B();
  if(temp>=2)
   temp=1;
 }
 return temp;
}

int Parser::B()
{int temp;
 temp=C();
 while(sym=='*')
 {sym=t.next();
  temp=temp*C();
 }
 return temp;
}

int Parser::C()
{int temp;
 temp=D();
 while(sym=='^')
 {sym=t.next();
  temp=(temp+D())%2;
 }
 return temp;
}

int Parser::D()
{int temp;
 switch(sym)
 {case '0': sym=t.next(); return 0;
  case '1': sym=t.next(); return 1;
  case '(': sym=t.next(); temp=A(); if(sym!=')') exit(1);
            sym=t.next(); return temp;
  default:  exit(2);
 }
 return -1; //keep the compiler happy; we should never get here
}

5.  Given the class A, write a class B which only has the member functions
incinc() and incV() and produces the output indicated between the second
and third dashed lines when the code between the first and second dashed
dashed lines is run.  What simple change in the definition of class A
would have the same code produce the output between the third and fourth
dashed lines?
   class A
   {private:
     int v,w;
    public:
      A(int n=0,int m=0);                 A::A(int n,int m){v=n; w=m;}
      void incV(int n);                   void A::incV(int n){v+=n;}
      void inc();                         void A::inc(){w++; incV(1);}
      void show();                        void A::show()
   };                                       {cout<<"v="<<v<<", w="<<w<<endl;}
------------------------------------
B b(2,3);
b.show();
b.incinc();
b.show();
b.incV(1);
b.show();
------------------------------------
v=2, w=3
v=4, w=5
v=6, w=5
------------------------------------
v=2, w=3
v=6, w=5
v=8, w=5
------------------------------------
=================================================
 class B: public A
 {public:
    B(int n=0,int m=0);
    void incV(int n);
    void incinc();
 };

 B::B(int n,int m):A(n,m)
 {}
 void B::incV(int n)
 {A::incV(2*n);}
 void B::incinc()
 {inc(); inc();}

 To get the second 3 lines of output, declare A::incV() virtual:
  virtual void incV(int n);

6.  Below I have written the declaration for a class Table which is meant to
store a person's age at the person's name.  You must provide the definitions
(code) but MUST NOT change the declaration.  Given your definitions the
function test() below should compile and produce the output between the dashed
lines.
class Table
{public:
  Table(int n=100);
  ~Table();
  int & operator[](char *name); //Precondition: name points to a string of
                                 //characters terminated by '\0'
 private:
  int count,size;
  static void assert(bool b,char *mess); //exit on error
  char **names;
  int *age;
};
void test()
{Table t(20);
 t["Thomas"]=45;
 t["Dick"]=35;
 t["Harry"]=12;
 cout<<t["Thomas"]<<" "<<t["Harry"]<<endl;
}
-----------------------------
45 12
-----------------------------
================================================================
 Table::~Table()
 {for(int j=0;j<size;j++)
   if(names[j]!=NULL)
    delete []names[j];
  delete [] *names;
  delete [] age;
 }

 Table::Table(int n)
 {assert(n>0,"(Table(int)) Bad argument");
  age=new int[n];
  assert(age!=NULL,"Heap overflow");
  size=n;
  names=new char*[n];
  assert(names!=NULL,"Heap overflow");
  for(int j=0;j<size;j++)
   names[j]=NULL;
 }

 int & Table::operator[](char *name)
 {int loc;
  loc=0;
  while(loc<size && names[loc]!=NULL && strcmp(names[loc],name)!=0)
    loc++;
  assert(loc<size,"Table overflow");
  if(names[loc]==NULL)
   {names[loc]=new char[strlen(name)+1];
    assert(names[loc]!=NULL,"Heap overflow");
    strcpy(names[loc],name);
   }
  return age[loc];
 }

 void Table::assert(bool b,char *mess)
 {if(!b)
   {cout<<"ERROR: "<<mess<<endl;
    exit(1);
   }
 }

7. Consider the following game.  Put 3 pennies and 3 dimes in 7 boxes as
          +-------------+
follows:  |P|P|P| |D|D|D| You may slide a penny or dime into an empty box,
          +-------------+
or you may hop a penny or dime over a penny or dime into an empty box.
                                                         +-------------+
THe goal is to find moves that produce the following:    |D|D|D| |P|P|P|
                                                         +-------------+
In general one could have n pennies and n dimes in 2*n+1 boxes.  Explain
why the problem of writing a program which finds a solution to the latter
problem is a branch and bound problem.  Sketch out an algorithm which would
solve this problem.  Determine the complexity of the algorithm as a function
of n. Hint: The number of different arrangements of the n pennies and n dimes
in 2n+1 boxes is (2n+1)!/(n!n!).
=====================================================================
The problem is a branch and bound problem, because a simple solution consists
of traversing a search tree, where the nodes of the tree consist of the
configurations for the pennies and dimes in the boxes, e.g., "PP DPDD", and
where there is a branch from node A to node B if one can change A's
configuration to B's configuration in one of the four moves given above.  One
can bound the search by only allowing moves to configurations not previously
seen.  This immediately removes at least one branch from every node except
the root node, because the move back to the previous configuration is no
longer valid.
      A recursive (search) algorithm for solving the problem from a given
configuration:  If the configuration is the one sought, print the solution
else for each branch from the given configuration, if the branch leads to a
configuration not previously visited, solve the problem from that
configuration.  (This algorithm bounds the problem by avoiding backtracking.)
      With the exception of the first node which has 4 children, all nodes
in this search tree have at most 3 children.  The tree can be no deeper than
the number of configurations (2n+1)!/(n!n!).  Thus we have
 O(3^((2n+1)!/(n!n!))), where '^' indicates exponentiation.  This grows very
rapidly, but the "bounding" severly prunes the search tree and makes it much
more manageable.
8.  Write the OP2 code which corresponds to the following ASM2F program.
Recall the OP2 codes:  read(0), write(1), load immediate(2), store(3),
add(4), subtract(5), multiply(6), divide(7), jump(8), compare and jump(9).
      JMP PROG
 SUM: VAR
 MAX: CNST 200
 PROG:
      LDI MAX+2*(MAX-3)
      STO SUM
 LOOP:RD
      SUB ACCUM,MAX
      JNE LESS
      ADD ACCUM,MAX
 LESS:ADD ACCUM,SUM
       STO SUM
       JEQ QUIT
       JMP LOOP
 QUIT: HLT
 END
 8 9 90 905
======================
8004000    [1]
0          [2]  sum
200        [3]  max
2000594    [4]  prog
3002000    [5]
0          [6]  loop
5000003    [7]
9010010    [8]
4000003    [9]
4000002   [10]  less
3002000   [11]
9014014   [12]
8015000   [13]
8006000   [14]
8000000   [15]  quit
E
8 9 90 905