CSE 109 Final Examination  Thursday   11 December 2003  7-10 PM
>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1.  Write an LSAsm program that reads in three integers and then displays
a 1 if the sum of the squares of the first two numbers is the square of the
third number. Otherwise it displays a 0.  Recall some of the BNF for LSAsm
programs:  <arith>::= { ADD | SUB | MULT | DIV } <reg>,<reg>,<reg>
           <if>::= [IF {LT | LE | EQ | NEQ | GT | GE } ] GOTO <label>
           <motion>::= { {LOAD | STORE | READ} { <label> | <reg> } }
                       | WRITE <exp> | MOV <exp>, <label>
           <exp>::= <term> [ {+|-} <term> ]*
           <term>::= <factor> [ {*|/} <factor> ]*
           <factor>::= ( <exp> ) | <label> | <reg>
>>>>>>>>>>>>>>>>>>>>>>>>>>
  READ R2
  READ R3
  READ R4
  MOV R2*R2+R3*R3-R4*R4,X
  LOAD X
  IF EQ GOTO EQUAL
  WRITE R0-R0
  HALT
EQUAL
  WRITE ONE
  HALT
  X 0
  ONE 1
END
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2. Given the classes and program below, state the output of the program when
it is executed.
  #include <fstream.h>
  class A {public:  A(){x=0;}
                    int one(){return two() + three();}
                    virtual int two(){return x+42;}
                    int three(){return x+17;}
                    int x;
  };
  class B:public A { public: B(){x=5;}
                             int two(){return x+109;}
                             int three(){return x+111;}
  };
  int main()
   { A a;
     B b;
     cout<<a.one()<<" "<<a.two()<<" "<<a.three()<<endl;
     cout<<b.one()<<" "<<b.two()<<" "<<b.three()<<endl;
     cout<<b.A::two()<<" "<<b.A::three()<<endl;
   }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
59 42 17
136 114 116
47 22
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
3.  Assume that class Lex has a single public method called next(), that Lex
is a lexical analyzer that uses cin for input, and that on each call to next()
one of the integer constants A, B, C, D, E, EOLN, or JUNK is returned.
Assume that only the default constructor, Lex(), is defined for Lex and that
EOLN is returned when the end of the line is encountered.  Write a class
Parser that has a method parse() which returns true if and only if the
contents of the current line of text in cin obeys the syntax of <one> defined
by the BNF statements:
  <one>::=  <two> [ {A|B|C} <two> ]* | D<one>
  <two>::= E <one> | A | B
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream.h>
#include "lex.h"

class Parser
{public:
  Parser();
  bool parse();
 private:
  bool one();
  bool two();
  Lex lex;
  int tok;
};

Parser::Parser(){}

bool Parser::parse()
{ tok=lex.next();
  return one() && tok==Lex::EOLN;
}

bool Parser::one()
{bool temp;
 if(tok==Lex::D)
  {tok=lex.next();
   return one();
  }
 temp=two();
 while(temp && (tok==Lex::A || tok==Lex::B || tok==Lex::C))
   {tok=lex.next();
    temp=temp&&two();
   }
 return temp;
}

bool Parser::two()
{switch(tok)
  {case Lex::A:
   case Lex::B: tok=lex.next(); return true;
   case Lex::E: tok=lex.next(); return one();
  }
 return false;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4. (a) Given the functions f(x)=x*x + 3 x -1 and g(x)=log(x), determine
    whether   (i) f is O(g)
             (ii) g is O(f)

   (b) Determine the complexity of the following sloppy implementation of
    the bubble sort.
      void sort(double x[],int total)
      {for(int j=0; j<total; j++)
         for(int k=0; k<total-1;k++)
           if(x[k]>x[k+1])
             swap(x[k],x[k+1]);
      }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  a.i.  f is not O(g) because
    lim (x*x+3x-1)/log(x) = inf/inf
   x->inf
                          = lim (2x+3)/(1/x) = inf (by l'hopital's rule)
                           x->inf
  a.i.  g is O(f) because
    lim log(x)/(x*x+3x-1) = inf/inf
   x->inf
                          = lim (1/x)/(2x+3) = 0  (by l'hopital's rule)
  b.  The most frequent operation in the sort is '<'.  This operations
      occurs total*(total-1) times ==> the sort is omega(n*n).
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
5.  Write the template for a class RayDisplay whose only purpose is to
display the contents of an array.  The following code should compile and
list the contents of each array, one entry per line.
int main()
{ int x[]={1,2,3};
  double y[]={2.3, 2.4, 2.5, 2.8, 2.9};
  RayDisplay <int> a(x,3);
  RayDisplay <double> b(y,5);
  cout<<a<<b;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream.h>
#include <stdlib.h>
template <class X>
class RayDisplay
 {public:
   RayDisplay(X x[],int n);
   ~RayDisplay();
  template <class Y>
   friend ostream & operator << (ostream &out,const RayDisplay<Y> & r);
  private:
   X *y;
   int size;
 };

template <class X>
RayDisplay<X>::RayDisplay(X x[],int n)
{bool good;
 if(n<=0)
  good=false;
 else y=new X[n];
 good=good && y!=NULL;
 if(!good)
  {cerr<<" Bad n or heap overflow\n";
   exit(1);
  }
 size=n;
 for(int j=0; j<size; j++)
  y[j]=x[j];
}

template <class Y>
  RayDisplay<Y>:: ~RayDisplay(){delete []y;}

template <class Y>
ostream & operator<<(ostream &out,const RayDisplay<Y> & r)
{for(int j=0; j<r.size; j++)
  out<<r.y[j]<<endl;
 return out;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
6.  Assume a quadratic probe was used when constructing the following
11-entry hash table, which currently has 4 items stored.  The table stores
ints, uses the int itself for the hash number, and uses the algorithms
discussed in class for finding the location for storing the number.
       0    1   2   3   4   5   6   7   8   9   10
      ---------------------------------------------
      | 99|110|   |   | 48|   |   |   |   | 33|   |
      ---------------------------------------------
   (a) If 1 was stored next, where would it be stored?
   (b) If (instead of 1) 0 was stored next, where would it be stored?
   (c) Explain how you can tell that 33 was the last (fourth) item to be
       put in the table.
   (d) If I knew that I was going to store at most 5 items, why did I choose
       a table size of 11?
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    a.  Try to store at 1, fail, try to store at 1+1=2 and succeed
        ==> store at 2
    b.  Try to store at 0, fail, try to store at 0+1=1, fail, try to store at
        0+4=4, fail, try to store at 0+9=9, fail, try to store at (0+16)%11=5
        and succeed ==> store at 5.
    c.  In storing 33, you would first try 33%11=0, but it must have been
        occupied; then you would try (33+1)%11=1, but it must have been
        occupied; then you would try (33+4)%11=4, but it must have been
        occupied; then you would try (33+9)%11=9.  Thus 99, 110, and 48 were
        stored before 33 was stored.
    d.  The quadratic probe depends on the table size being prime. Efficient
        hashing depends on the table being at least twice the size of the
        number of entries.  Thus 11 is the smallest prime larger than 2*5.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
7.  I decided we should add the SQUARE operation to LSAsm.  Thus, I modified
the BNF for <line> to be:
   <line>::= <arith> | <if> | <motion> | HALT | <square>
   <square>::= SQUARE <label>
The operation SQUARE X has the effect of replacing the contents of X with the
square of X.  Below is the code to parse such statements.  Modify the function
to include the code generation.  Assume the codefile is accessed by data member
 *ostream code;  and that data member  Table<Word,int> tab; stores the
addresses of the labels.

  void FullParser::square()
  {tok=lex.next();
   declare(tok==Lex::IDENT," (square()) IDENT expected");
   declare(pass==1 || tab.inTable(lex.getStr()),"(square()) undefined label");
   ....
   ....
   PC+= ?????  //the only place where PC is incremented, but how much??
   tok=lex.next();
  }

Recall:  LOAD(0), STORE (1), ADD(2), SUB(3), MULT(4), DIV(5), LT(6), GE(7),
         IO(8)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
void FullParser::square()
{tok=lex.next();
 declare(tok==Lex::IDENT," (square()) IDENT expected"," ");
 declare(passCt==1 || tab.inTable(lex.getStr()),
               "(square()) undefined label"," ");
 if(passCt==2)
  {*fcode<<tab[lex.getStr()]<<endl
         <<4000<<endl
         <<(1000+tab[lex.getStr()])<<endl;
  }
  PC+=3;
  tok=lex.next();
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
8.  Given the class D below create a subclass E of D so that the code in
the program compiles and produces the output indicated.  Give both the
declaration of E and the definition (code).

class D
 {public:
   D(int a=0){x=a;}
  protected:
   int x;
 };
 int main()
 {E u(2),v(3);
  cout<<u<<" + "<<v<<" = "<<(u+v)<<endl;  // [2] + [3] = [5]
 }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream.h>

class E:public D
{public:
  E(int a=0);
  E operator+(const E & e)const;
  friend ostream & operator<<(ostream &out,const E& e);
};

  E::E(int a):D(a){}

  E E::operator+(const E & e)const
  {return E(x+e.x);}

  ostream & operator<<(ostream &out,const E& e)
  {out<<'['<<e.x<<']';
   return out;
  }
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<