CSE 109  Final Examination  Wednesday 9 December 2009
========================= SUGGESTED ANSWERS ============================
1. Consider the ADT for an association, which conists of an instance of one
type associated with an instance of a second type. Write the template for a
C++ class that implements this ADT and enables the code below to compile and
produce the indicated output (recall "cout<<true" displays 1 and
"cout<<false" displays 0).  You only need code sufficent to produce the
indicated output.
    Association<Word,int> x("One",3), y("One",4), z("Two",2);
    cout<<x<<"<"<<y<<"="<<(x<y)<<endl;   //   {One, 3}<{One, 4}=1
    cout << (y<x) << (x<z) << (z<x) <<endl;   //   010
==========================================================================

#include <iostream>
using namespace std;

#include "word.h"
#include "check.h"

template<class X, class Y>
class Association{
public:
  Association(const X &x,const Y&y);
  bool operator < (const Association &a)const;
  template <class U, class V>
  friend ostream & operator<<(ostream &out,const Association <U,V> &a);
private:
  X a;
  Y b;
};

int main(){
    Association<Word,int> x("One",3), y("One",4), z("Two",2);
    cout<<x<<"<"<<y<<"="<<(x<y)<<endl;   //   {One, 3}<{One, 4}=1
    cout << (y<x) << (x<z) << (z<x) <<endl;   //   010
}

template<class X, class Y>
Association<X,Y>::Association(const X &x, const Y &y):a(x),b(y){}

template<class X, class Y>
bool Association<X,Y>::operator<(const Association &as)const{
  return a<as.a || a==as.a && b<as.b;
}

template<class X, class Y>
ostream & operator<<(ostream &out,const Association <X,Y> &a){
 return out<<"{"<<a.a<<", "<<a.b<<"}";
}
==========================================================================
2. Assume that the class Node, which is below, is used to build a binary tree
of ints, where the tree has the property that the int stored at any node is
greater than the ints in the nodes in the tree whose root is the left child
and is less than the ints in the nodes in the tree whose root is the right
child. Write the functions height() and max(), where height returns the
the number of nodes in the longest path from the root to a leaf, and max()
returns the maximum int in the tree.  The code below indicates how the the
functions are called.
  class Node{
    public:
      int num;
      Node *child[2];
      static const int RIGHT=0, LEFT=1;
      Node(int k);
  };
 Node::Node(int k){
        num=k;
        child[LEFT]=NULL;
        child[RIGHT]=NULL;
 }
int main(){
   Node *x;
   buildTree(x);
   cout<<"The height of the tree is "<<height(x)<<" and the "
       <<"largest value is "<<max(x)<<endl;
}
==========================================================================
int height(Node *x){
  int h[2];
  if(x==NULL)
    return 0;
  for(int j=0;j<2;j++)
    h[j]=height(x->child[j])+1;
  if(h[0]>h[1])
    return h[0];
  return h[1];
}

int max(Node *x){
  if(x==NULL){
    cerr<<"Empty tree\n";
    exit(1);
  }
  while(x->child[x->RIGHT]!=NULL)
    x=x->child[x->RIGHT];
  return x->num;
}
==========================================================================

3. Consider the ADT for a "quadratic probe producer (QPP)" that can be used in
implementing a hash table.  One seeds the QPP with some positive number,
which represents the hash code, and a second positive number, which represents
the table size. Then each time next() is called, it returns the next place to
look in the table, using the quadratic probe.  The first time it is called it
returns the place that corresponds to the given hash code.  Your declaration
and definitions need only be sufficient for the code below to compile and
produce the output indicated.
  QPP a(23,7), b(242,80), c(23,7),d(23,7);
  cout<<a.next()<<endl;   //   2
  a.next();
  c.next();
  c.next();
  cout<< (a==c) <<","<< (a==d) << ","<<(b==d) << endl;   //   1,0,0
  cout<<(b.next()==d.next())<<endl;   // 1
==========================================================================
#include <iostream>
using namespace std;

class QPP{
private:
  int hash,quad,tableSize;
public:
  QPP(int h,int s);
  int next();
  bool operator==(const QPP &q)const;
private:
  static void check(bool b, const char *mess);
};

QPP::QPP(int h, int s):hash(h),quad(0),tableSize(s){
  check(h>=0,"Need hash number >= 0");
  check(s>=1,"Need positive table size");
}

int QPP::next(){
  int temp;
  temp=(hash+quad*quad)%tableSize;
  quad++;
  return temp;
}

bool QPP::operator==(const QPP&q)const{
  return hash==q.hash && tableSize==q.tableSize && quad==q.quad;
}

void QPP::check(bool b, const char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
==========================================================================
4. Given the class Point below, write a subclass of Point, called MyPoint,
that enables the code below class Point to compile and produce the indicated
output.
  class Point{
    protected:
      int x,y;
    public:
      Point(int a, int b);
      int getX()const;
      int getY()const;
  };
  Point::Point(int a, int b):x(a),y(b){}
  int Point::getX()const{return x;}
  int Point::getY()const{return y;}
  int main(){
     MyPoint a(2,3), b(3,4);
     a.moveBy(b).moveBy(Point(1,1));
     cout<<a<<endl;  // MyPoint(6,8)
     cout<< (a+b)<<end;   // MyPoint(9,12)
   }
==========================================================================
class MyPoint: public Point{
public:
  MyPoint(int a, int b);
  MyPoint & moveBy(const Point&p);
  friend ostream & operator<<(ostream &out,const MyPoint &mp);
  MyPoint operator +(const MyPoint &mp)const;
};

MyPoint::MyPoint(int a, int b):Point(a,b){}
MyPoint & MyPoint::moveBy(const Point &p){
  x+=p.getX();
  y+=p.getY();
  return *this;
}
ostream &operator<<(ostream &out,const MyPoint &mp){
  return out<<"MyPoint("<<mp.x<<", "<<mp.y<<")";
}

MyPoint MyPoint::operator+(const MyPoint &mp)const{
  return MyPoint(*this).moveBy(mp);
}
==========================================================================
5. Write a program that reads one line of characters from the console and
states whether the line of characters satisfies the syntax diagrams for
S below.  Notes: (1) a blank character is not a legitimate character;
(2) I use parentheses, (), to indicate circles and square brackets, [], to
indicate boxes.
                 S
                 ------(6)----+     +----(6)---+
                    |         |-----|          |------------------------>
                    +--(1)----+     +----(2)---+     ^             |
                                                     |             |
                                                     +-------[T]<--+
                 T     +---(4)-->[S]-->[S]--+
                 ------|                    |----------------->
                       +---(5)-->[T]--------+
                       |                    |
                       +---------------(9)--+

==========================================================================
#include <iostream>
using namespace std;

void getch(char &ch){
  if(ch!='\n')
    cin.get(ch);
}

void check(bool b){
  if(!b){
    cerr<<"The line is not syntactically correct\n";
    exit(1);
  }
}

void t(char&ch);

void s(char &ch){
  check(ch=='6' || ch=='1');
  getch(ch);
  check(ch=='6' || ch=='2');
  getch(ch);
  while(ch=='4' || ch=='5' || ch=='9')
    t(ch);
}

void t(char &ch){
  switch(ch){
  case '4':
    getch(ch);
    s(ch);
    s(ch);
    break;
  case '5':
    getch(ch);
    check(ch=='4' || ch=='5' || ch=='9',"'4', '5', or '9' expected");
    t(ch);
  case '9':
    getch(ch);
  }
}

int main(){
  char ch;
  getch(ch);
  s(ch);
  check(ch=='\n');
  cout<<"The line is syntactically correct\n";
}



==========================================================================
6. Write a C program (that compiles with the -xc option,) that requires the
name of a (n input) file on the command line, that assumes the file consists
solely of ints, and that displays on the screen the sum of the ints in the
file.
==========================================================================
#include <stdio.h>
#include <stdlib.h>

void check(int b,char * mess){
  if(!b){
    printf("ERROR: %s\n",mess);
    exit(1);
  }
}

int main(int ct,char *arg[]){
  FILE *f;
  int x,sum;
  check(ct==2,"Usage:  a.out <inputfile>");
  sum=0;
  f=fopen(arg[1],"r");
  check(f!=NULL,"Failure to open the input file");
  while(fscanf(f,"%d",&x)!=EOF)
    sum+=x;
  printf("%d\n",sum);
  return 1;
}
==========================================================================

7. Write a C program that (compiles with the -xc option, that) prompts the
user to enter an int, that reads the int, and that diplays the values of the
four bytes that comprise the int.  For example, if the user enters 257, the
four bytes are 1, 1, 0, and 0.
==========================================================================
#include <stdio.h>

struct B{
  unsigned b1: 8;
  unsigned b2: 8;
  unsigned b3: 8;
  unsigned b4: 8;
};

union A{
  int x;
  struct B y;
};

union C{
  int x;
  char ch[4];
};

int main(){
  /* ONE ALTERNATIVE*/
  /*
  union C n;
  printf("Enter an int- ");
  scanf(" %d",&n.x);
  printf("The bytes: %d %d %d %d \n",(int)n.ch[0], (int)n.ch[1],
	 (int)n.ch[2], (int)n.ch[3]);
  */

  /*A SECOND ALTERNATIVE */
  /*
  union A a;
  printf("Enter an int- ");
  scanf(" %d",&a.x);
  printf("The bytes: %d %d %d %d \n",a.y.b1, a.y.b2, a.y.b3, a.y.b4);
  */
  /* A THIRD ALTERNATIVE AND A FOURTH ALTERNATIVE*/
  int x;
  printf("Enter an int- ");
  scanf(" %d",&x);
  printf("The bytes: %d %d %d %d \n",x/256/256/256,x/256/256%256,
	 x/256%256,x%256);
  printf("The bytes: %d %d %d %d \n",x>>24,x>>16%256,x>>8%256,x%256);
  return 1;
}
==========================================================================
8. Assume that for each class mentioned below the declaration for the class
is in a .h file of the same name, but in lower case, and the code is in a
.cc of the same name, but in lower case.  Class B is a subclass of class A.
Class C is a subclass of class B. Class D has an instance variable of type
C and uses a templated class stored in the file x.t. The main program is
stored in the file prog.cc and has objects of type B and of type D.
(1) For each .h file and each .cc file, write the necessary "include"
statement(s).
(2) Write a makefile for compiling prog.cc, creating the executable
file "prog", and for "cleaning up."
==========================================================================
a.h:   no includes
a.cc:  #include "a.h"
b.h:   #include "a.h"
b.cc:  #include "b.h"
c.h:   #include "b.h"
c.cc   #include "c.h"
d.h:   #include "c.h"
       #include "x.t"
d.cc:  #include "d.h"
prog.cc: #include "d.h"
-----------------------------
CC= g++ -c -Wall -Werror
prog: prog.o a.o b.o c.o d.o
      g++ -o prog a.o b.o c.o d.o prog.o
prog.o: prog.cc a.h b.h c.h d.h x.t
      $(CC) prog.cc
a.o: a.cc a.h
      $(CC) a.cc
b.o: b.cc a.h b.h
      $(CC) b.cc
c.o: c.cc a.h b.h c.h
      $(CC) c.cc
d.o: d.cc a.h b.h c.h d.h x.t
      $(CC) d.cc

clean:
      rm -f *.o *~ prog
==========================================================================