CSE 109 Final Examination Sunday 6 May 7-10 PM 2012

========================== SUGGESTED ANSWERS =========================
1. The lamp in my living room is always in one of four states, depending
on whether zero, one, two or three bulbs are lit. Each twist of the knob
increases the number of bulbs lit until all are lit. Then the next twist
turns all the bulbs off (although I once mistakenly rewired it so that
the order was 0,1,3,2,0,.., but forget about that). Write a class that
implements the ADT for this four way switch. Call the class FWS. Below
is code that shows how the class would be used. You need only implement
those methods and constructors that would enable the code to compile.

int main(){
  FWS x;
  x.click().click();
  cout<<"State="<<x.state()<<"  "<<x<<endl;  //State=2 FWS(2)
}
======================================================================
class FWS{
private:
  int st;
public:
  FWS();
  FWS& click();
  int state()const;
  friend ostream & operator<<(ostream &out,const FWS&f);
};

FWS::FWS():st(0){}

FWS & FWS::click(){
  st=(st+1)%4;
  return *this;
}

int FWS::state()const{return st;}

ostream & operator<<(ostream &out,const FWS&f){
  return out<<"FWS("<<f.st<<")";
}
=========================================================================
2. Assume you are using quadratic probes to resolve collisions in a hash
table and suppose you start probing at location 0.
  a. Show the sequence of locations for the first 10 probes, assuming a
     table size of 17.




  b. Show the sequence of locations for the first 10 probes, assuming a
     table size of 16.




  c. Discuss the difference in behavior of the quadratic probe in (a) versus
     the quadratic in (b).
===========================================================================
a. Hash starting at 0, n=17
    0, 1, 4, 9, 16, 8, 2, 15, 13, 13, 15
b. Hash starting at 0, n=16
    0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4 
c. The first sequence does not repeat until the 9th probe,
   while the second sequence seems to be stuck on the numbers
   0, 1, 4, 9. With the latter sequence if those four 
   positions are occupied, it appears we would probe forever
   if looking to find a free location. The first sequence 
   depends on a table of prime size. In class we showed that
   if the quadratic probe is used in a table of prime size,
   then you have to probe at least half the table before 
   probing the same place twice.
========================================================================
3.  I am developing a C program to read data from the console and put it
in a linked list, the struct for which is below. After I grade the final
examination, I will write the code for build(). Here I ask you to write the
code for nonNeg() and for inList(). The program must compile with the options
-xc -Wall -Werror (which only allows C, rather than C++, code).
#include <stdio.h>
#include <stdlib.h>
struct Link{
  int key;
  double data;
  struct Link * next;
};
int main(){
  struct Link * head;
  int k;
  double d;
  head=NULL;
  while(nonNeg(&k,&d)) //nonNeg() reads in k and d and returns false if an
                       //only if the value of k is less than zero.
    build(&head,k,d);// add a Link to the the front of the list with
                      //key == k and data == d
  printf("It is %s that the key 6 is in the list\n",
         inList(head,6)?"true":"false"); //inList returns true if and only
                                         //if the given key is in the list
  return 0;
}
==========================================================================
int nonNeg(int *k,double*d){
  scanf(" %d %lf",k,d);
  return *k>=0;
}

int inList(struct Link* h,int k){
  while(h!=NULL && h->key!=k)
    h=h->next;
  return h!=NULL;
}
===========================================================================
4. The HP calculators depend upon a very simple, but remarkably effective,
four-entry stack. Initially it consists of four (arbitrary) default values.
Any number of items can be pushed onto the stack, but it only retains up to
the last four pushed. It can be popped any number of times, returning default
values when the stack is emptied of items placed on the stack (but not pushed
off the bottom). Write a template to implement this ADT. Below is code that
demonstrates its use (where your templates would be in the file "hp.t".)
NOTE: Your class should be written so that the subclass in question (5) can
be readily implemented.
#include "hp.t"
#include "word.h"
int main(){
  HP<Word> st;
  st.push("one").push("two").push("three").push("four").push("five");
  for(int j=0;j<6;j++)
    cout<<"'"<<st.pop()<<"' ";
  cout<<endl;
}
//OUTPUT:  'five' 'four' 'three' 'two' '' ''
============================================================================
template <class S>
class HP{
protected:
  int top;
  S hp[4];
public:
  HP();
  HP & push(const S &s);
  S pop();
};


template <class S>
HP<S>::HP():top(0){
  //  for(int j=0;j<4;j++)    this loop not needed
  //  hp[j]=S();
}

template <class S>
HP<S>& HP<S>::push(const S&s){
  hp[top%4]=s;
  top++;
  return *this;
}

template <class S>
S HP<S>::pop(){
  S temp;
  top+=3;
  temp=hp[top%4];
  hp[top%4]=S();
  return temp;
}
=============================================================================
5. Create a subclass Bhp ("better HP") of class HP<Word> (see question (4)).
Bhp adds some functionality to class HP. Its use is illustrated below.
int main(){
  Bhp b;
  (b+="hello")+="there";
  cout<<b<<endl;            // OUTPUT: -->''-->''-->'hello'-->'there'
  cout<<"'"<<b.pop()<<"'\n";   // OUTPUT: 'there'
}
============================================================================
class Bhp:public HP<Word>{
public:
  Bhp();
  friend ostream & operator<<(ostream &out,const Bhp&b);
  Bhp& operator+=(const Word&w);
};

Bhp:: Bhp(){}

ostream & operator<<(ostream &out,const Bhp&b){
  for(int j=0; j<4; j++)
    out<<"-->'"<<b.hp[(b.top+j)%4]<<"'";
  return out;
}

Bhp& Bhp::operator+=(const Word&w){
  push(w);
  return *this;
}
=========================================================================
6. Somehow I lost my makefile for p7. Below, please write the makefile for
me, including a command for "cleaning up." It should compile the code for
classes separately. I do recall the files I used for p7:    word.h, word.cc,
node.t, tree.t, lex.h, lex.cc, parse.h, parse.cc, p7.cc.  The executable
file should be stored in the file p7.
=========================================================================
p7: lex.o p7.o word.o parse.o
        g++ -o p7 lex.o p7.o word.o parse.o

p7.o: p7.cc lex.h word.h parse.h tree.t node.t
	g++ -c -Wall -Werror p7.cc

parse.o: parse.cc lex.h word.h parse.h tree.t node.t
	g++ -c -Wall -Werror parser.cc

lex.o: lex.cc lex.h word.h tree.t node.t
	g++ -c -Wall -Werror lex.cc

word.o: word.cc word.h
	g++ -c -Wall -Werror word.cc

clean:
	rm -f *~ *.o p7
==========================================================================
7. Below are the syntax diagrams for the language 'a', and below the
diagrams is a partially completed program for determining whether a line of
text satisfies the diagrams for 'a'. (It uses class Lex to tokenize the
string.) Provide the functions a() and b() (and any other functions that
they may call). NOTE: [] denotes a rectangle, and () denotes an oval.
#include "lex.h"
/*     a
       -------[b]--------------------------------------+
           |       +-->(+)--+                          |--------->
           +------>|        |--+--------->-----[b]-----+
              |    +-->(-)--+  |
              +-----<<<<-------+
       b
       ----------->[NUMBER]---->
              |--->[IDENT]---->
              +--->(<)-->[a]--(*)--[a]--(>)-->
Relevant Lex tokens: IDENT, NUMBER, SPLUS, SMINUS, STIMES, LT, GT*/
void check(bool b, const char * mess,int loc){
  if(!b){
    cerr.width(loc);
    cerr<<"^^"<<mess<<endl;
    exit(1);
  }
}
int main(){
  Lex lex;
  Word w="<<67++++2*22>*22>+++-<2*xox>";
  cout<<w<<endl;
  lex.set(w);
  int tok=lex.next();
  a(lex,tok);
  check(tok==Lex::EOLN,"Junk at end of line",lex.count());
  cout<<"Successful parse\n ";
}
===========================================================================
void b(Lex&lex,int &tok);
void a(Lex&lex,int &tok){
  b(lex,tok);
  if(tok==Lex::SPLUS || tok==Lex::SMINUS){
    while(tok==Lex::SPLUS || tok==Lex::SMINUS)
      tok=lex.next();
    b(lex,tok);
  }
}
void b(Lex&lex,int &tok){
  switch(tok){
  case Lex::NUMBER:
  case Lex::IDENT: tok=lex.next(); break;
  case Lex::LT:
    tok=lex.next();
    a(lex,tok);
    check(tok==Lex::STIMES," '*' expected",lex.count());
    tok=lex.next();
    a(lex,tok);
    check(tok==Lex::GT," '>' expected",lex.count());
    tok=lex.next();
    break;
  default: check(false," '<', number, or identifier expected",lex.count());
  }
}
============================================================================
8. Write a program that takes the names of two text files from the command
line and determines whether the contents of the two files are the same after
removing all white space. If the name of the executable program is dup, and
the names of two text files are filea and fileb, then the call would be
    dup filea fileb
============================================================================
#include <iostream>
#include <fstream>
using namespace std;

void check(bool bb, const char *a, const char *b="",const char*c=""){
  if(!bb){
    cerr<<"ERROR: "<<a<<b<<c<<endl;
    exit(1);
  }
}

int main(int c, char **arg){
  ifstream af[2];
  check(c==3," Usage: ",arg[0]," <input1> <input2>\n");
  for(int j=0;j<2; j++){
    af[j].open(arg[j+1]);
    check(af[j].good(),"Failure to open '",arg[j+1],"'");
  }
  char cha,chb;
  af[0]>>cha;
  af[1]>>chb;
  while(af[0].good() && af[1].good()&&cha==chb){
    af[0]>>cha;
    af[1]>>chb;
  }
  cout<<"Ignoring white space, the files are ";
  if(!af[0].good() && ! af[1].good())
    cout<<"identical\n";
  else
    cout<<"not identical\n";
  return 0;
}