CSE 109 Final Examination   Tuesday  7 December 2004
>>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<
1.  a. Assume the balance of the balanced                20
binary tree to the right is maintained                 /    \
using the algorithms discussed in class.             15      30
Draw the tree after 28 has been                    /   \   /   \
added to the original tree.  Now                  8    16 26    40
draw the tree after 39 has                               /  \   / \
been added to the ORIGINAL                             24   27 38  45
tree (i.e., assuming 28 was
not added).

b. Assume the tree to the right is a                       4
B-tree.  Draw the tree after the numbers                 /   \
8, 9, 10, and 11 have been added to the tree            2     6
in that order                                         /  \   / \
                                                     1   3  5   7
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
(Left to right, a.i, a.ii. b.)
          26                           30
       /      \                      /    \
    20           30               20        40              4     8
  /   \        /    \           /   \       / \           /    |    \
 15   24     27      40       15      26   38  45       2      6       10
 /\            \    /  \     / \    /  \    \          / \    / \      / \
8  16          28  38  45   8  16  24  27   39        1   3   5   7   9   11
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2.  Write a template for (the definition and code for) a class called List
that allows the user to add items to the list (with the method add()), access
items in the list (with the operator []), and get the number of items stored
in the list (with the method size()). Below is code that should
compile, given your template.
  List<int> x(20);
  x.add(2).add(20);
  for(int j=0;j<x.size(); j++)
    cout<<x[j]<<endl;
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
template <class T>
class List
{public:
  List(int n=20);
  ~List();
  List& add(const T&t);
  int size()const;
  T&operator[](int k);
  T operator[](int k)const;
private:
  int count,max;
  T *data;
  static void check(bool b,char *mess);
};

template <class T>
List<T>::List(int n):count(0),max(n)
  {check(n>0,"Bad list size");
  data=new T[n];
  check(data!=NULL,"Heap overflow");
  }

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

template <class T>
List<T>& List<T>::add(const T&t)
  {check(count<max,"List overflow");
  data[count]=t;
  count++;
  return *this;
  }

template <class T>
int List<T>::size()const {return count;}

template <class T>
T & List<T>::operator[](int k)
  {check(k>=0 && k<count,"Index out of range");
  return data[k];
  }

template <class T>
T  List<T>::operator[](int k)const
  {check(k>=0 && k<count,"Index out of range");
  return data[k];
  }

template <class T>
void List<T>::check(bool b,char *mess)
  {if (!b)
    {cerr<<"ERROR: "<< mess<<endl;
    exit(1);
    }
  }
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
3.  a.  Assume a hash table of ints of size 7 and the use of a quadratic probe
to resolve collisions, and assume that the int itself serves as the hash
number.  Show where the ints 27, 84, and 48 would be stored if entered into
the table in that order.
              +---------------------------+
              |   |   |   |   |   |   |   |
              |   |   |   |   |   |   |   |
              +---------------------------+
b.  Assume a hash table of ints of size 8 and the use of a quadratic probe
to resolve collisions, and assume that the int itself serves as the hash
number.  Show in detail that the storage scheme fails when trying to store the
number 48 after the numbers 0, 1, and 4 have already been stored.
Explain why the scheme fails.
              +-------------------------------+
              | 0 | 1 |   |   | 4 |   |   |   |
              |   |   |   |   |   |   |   |   |
              +-------------------------------+
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
                0   1   2   3  4   5   6
              +---------------------------+
              | 84|   |   | 48|   |   | 27|
              |   |   |   |   |   |   |   |
              +---------------------------+
                0   1   2   3   4   5   6   7
              +-------------------------------+
              | 0 | 1 |   |   |   |   |   |   |
              |   |   |   |   |   |   |   |   |
              +-------------------------------+
The initial storage location to try is 48%12==0.  Then the quadratic probe
would try 1, 4, 9, 16%8==0, 25%8==1, 36%8==4, 49%8==1, etc., never
trying any locations other than 0, 1, 4.  The scheme fails because 8,
the table size, is not a prime number.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4.  My implementation of mcasm depends upon a number of files that have the
following relationships.
 parse.h has the declaration of class Parser. It uses the templates in btree.h
   and the constants in mach.h, and class Parser has data members of type Word.
 parse.cc has the code for class Parser
 fullparse.h has the declaration for the class FullParser, which is a subclass
    of class Parser
 fullparse.cc has the code for class FullParser
 word.h has the declaration of the class Word
 word.cc has the code for class Word
 mcasm.cc contains the main program, which has a variable of type FullParser

 Write the makefile for compiling the code files and linking them to create the
 executable file mcasm.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    OPTS= -c -Wall -Werror
    mcasm: mcasm.o parse.o fullparse.o word.o
           g++ -o mcasm mcasm.o parse.o fullparse.o word.o
    mcasm.o: mcasm.cc parse.h fullparse.h word.h btree.h mach.h
           g++ $(OPTS) mcasm.cc
    fullparse.o: fullparse.cc fullparse.h parse.h btree.h mach.h word.h
           g++ $(OPTS) fullparse.cc
    parse.o: parse.cc parse.h btree.h mach.h word.h
           g++ $(OPTS) parse.cc
    word.o: word.cc word.h
           g++ $(OPTS) word.cc
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
5.  Below the definitions of classes A and B are eight code fragments that
depend on the classes A and B.  For each fragment, state whether the code
will compile. If it will compile, state the output.
  class A
   {public:
     A(int a=0):x(a){}
     virtual void v(){x++;}
     void u(){v();}
     void r(){x--;}
     void s(){r();}
     int x;
   };
  class B:public A
   {public:
     B(int a=0):A(a){}
     void v(){A::v(); A::v();}
     void r(){A::r(); A::r();}
     void w(){x=0;}
   };

 a)  A x(2); x.v(); cout<<x.x;

 b)  cout<<A(3).x;

 c)  A x(2); x.w(); cout<<x.x;

 d)  cout<< A( A(2).x ).x;

 e)  B x(2); x.v(); cout<<x.x;

 f)  B x(2); x.r(); cout<<x.x;

 g)  B x(2); x.u(); cout<<x.x;

 h)  B x(2); x.s(); cout<<x.x;

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
a. 3
b. 3
c.  does not compile (w() undeclared in A)
d. 2
e. 4
f. 0
g. 4
h. 1
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
6.  Write a mcasm program that reads in two numbers, assumed to be positive,
and displays the first number raised to the second number, e.g., if the
two numbers are 4 and 3, then 64 is displayed, because 4 raised to the 3rd
power is 64. (Recall the instructions READ, WRITE, LOAD, STORE, ADD, SUB,
MUL, DIV, HALT, JMPE, JMP, JMPL, JMPG, JMPLE, JMPGE, JMPNE, END)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
      READ X
      READ REG0    ;the power
      LOAD REG1 1  ;the product
LOOP
      JMPLE FINISH
      LOAD REG1 REG1*X
      LOAD REG0 REG0-1
      JMP LOOP
FINISH
      WRITE REG1
      HALT
X     0
END
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
7.  Write a class Lex that acts as a lexical analyzer for the command line,
where the items in the language are "TRUE", "FALSE", "{", "}", "AND", and
"OR".  The analyzer should return one of the Lex constants T (0), F (1),
LCURLY (2), RCURLY (3), AND (4), OR (5), END (6), and JUNK (7).  Below indicates
how the class could be used.
    int main(int ct,char **arg)
    {Lex lex(ct,arg);
     int tok;
     tok=lex.next();
     while(tok!=Lex::END)
     {cout<<tok<<" ";
      tok=lex.next();
     }
    }
If the executable were stored in a.out, then the command
   a.out  TRUE true AND { FALSE } OR
would produce the output:   0 7 4 2 1 3 5
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
class Lex
{public:
  static const int T=0, F=1, LCURLY=2, RCURLY=3, AND=4, OR=5, END=6, JUNK=7;
  Lex(int ct, char **arg);
  int next();
private:
  char **tokens;
  int loc,size;
};

Lex::Lex(int ct, char **arg):tokens(arg),loc(0),size(ct){}

int Lex::next()
{char *table[]={"TRUE", "FALSE", "{", "}", "AND", "OR"};
  if(loc>=size-1)
   return END;
  loc++;
  for(int j=0;j<END; j++)
    if(strcmp(table[j],tokens[loc])==0)
      return j;
  return JUNK;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
8.  Write a class Parse that uses Lex from question 7 to determine whether
the entry on the command line obeys the syntax of the diagram for S below.
Below the diagram is code that illustrates how the class Parse would be used.
Note that in the diagram parentheses indicate circles (or ovals) and square
brackets indicate rectangles.

  S
  --------------->(FALSE)-------------------------------------+
        |     |           ^      ^                  |         |
        |     |           |      |     +--(AND)<----+         |
        |     +--->(TRUE)-+      |     |            |         |
        |                        |     v            |         |
        |                       [S]<------(OR)<-----+         |
        |                                                     v
        +---------->({)-->[S]-->(})---------------------------------->
int main(int ct, char **arg)
{Parse p(ct,arg);
 p.parse();
 cout<<"The parse was successful\n";
 retun 0;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
class Parse
{public:
  Parse(int ct, char **arg);
  void parse();
private:
  Lex lex;
  int tok;
  void S();
  static void check(bool b, char*mess);
};

Parse::Parse(int ct, char**arg):lex(ct,arg){}

void Parse::parse()
{tok=lex.next();
 S();
}

void Parse::S()
{switch(tok)
  {case Lex::T:
  case Lex::F:
    tok=lex.next();
    while(tok==Lex::AND || tok==Lex::OR)
      {tok=lex.next();
      S();
      }
    break;
  case Lex::LCURLY:
    tok=lex.next();
    S();
    check(tok==Lex::RCURLY," '}' expected");
    tok=lex.next();
    break;
  default: check(false, " 'TRUE', 'FALSE', or '{' expected");
  }
}

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