CSC 109  Final Examination  Monday    4 May 2009     4-7 PM
===========================SUGGESTED ANSWERS=============================
1. Consider the ADT for an account in a bank. It may have a variety of sub-
classes (see question two) and only has functionality for adding to the
account, subtracting from the account, and retrieving the current balance.
Write the declaration and definitions for this ADT, calling the class Acct.
It should have sufficient functionaliy for the code below to compile and
produce the indicated output.  You may assume that you have the function
check(bool b,char*mess) available.
  Acct x(20);
  x+=42;
  x-=23.2;
  x+=4;
  cout<<"The balance is $"<<x.balance()<<endl; //The balance is $32.8
==========================================================================
#include <iostream>
using namespace std;

class Acct{
protected:
  double bal;
public:
  Acct(double z=0);
  Acct & operator +=(double g);
  Acct & operator -=(double g);
  double balance()const;
};

Acct::  Acct(double z):bal(z){check(z>=0,"(Acct::Acct()) negative balance");}
Acct & Acct::operator +=(double g){
  check(g>=0,"(Acct::+=) must have positive deposit");
  bal+=g;
  return *this;
}

Acct & Acct::operator -=(double g){
  check(g>=0,"(Acct::-=) must have positive deposit");
  check(g<=bal,"(Acct::-=) cannot have overdrawn account");
  bal-=g;
  return *this;
}

double Acct::balance()const{return bal;}
==========================================================================
2. Consider the ADT for a savings account. It has the same functionality as
the ADT in question 1, plus the ability to set an interest rate and to
periodically pay interest on the account.  Write the declaration and
definitions for the class Savings, which is a subclass of Acct.
It should have sufficient functionaliy for the code below to compile and
produce the indicated output.  You may assume that you have the function
check(bool b,char*mess) available.
  Savings x(100,0.10); //initial deposit of 100, interest rate 10%/year
  x+=100;  //balance now 200
  x.update();
  cout<<"The balance is $"<<x.balance()<<endl; //The balance is $220
  x-=20;   //balance is 200
  x.setRate(0.05); //change rate to 5%
  x.update();
  cout<<x<<endl;  // Savings(210,0.05)
==========================================================================

class Savings:public Acct{
private:
  double rate;
public:
  Savings(double b=0,double r=0);
  void setRate(double r);
  void update();
  friend ostream & operator<<(ostream &out,const Savings & s);
};

Savings::Savings(double b,double r):Acct(b),rate(r){
  check(r>=0,"(Savings::Savings()) cannot have negative rate");
}

void Savings::setRate(double r){
  rate=r;
  check(r>=0,"(Savings::setRate()) cannot have negative rate");
}

void Savings::update(){
  bal+=rate*bal;
}

ostream & operator<<(ostream &out,const Savings & s){
  out<<"Savings("<<s.bal<<", "<<s.rate<<")";
  return out;
}
==========================================================================
3. Consider the ADT for a list.  You can add items to the end of the list,
you can access (but not change) entries in the list, and you can list the
contents of the list.  Write a template for this class so that the code
below would compile and produce the indicated output when run. You can
assume that check(bool b,char*mess) is available.
 List<double> x(100); //maximum of 100 entries
 List<char>  y(20);  //maximum of 20 entries
 x.add(40).add(30).add(10);
 cout<<x[0]<<" "<<x[2]<<endl; // 40 10
 y.add('P').add('i').add('z').add('z').add('a');
 cout<<y<<endl; // List: Pizza
==========================================================================

template <class X>
class List{
 private:
  X *data;
  int total,max;
 public:
  List(int n=100);
  List & add(const X &x);
  ~List();
  const X & operator[](int n)const;
  template <class Y>
  friend ostream & operator<<(ostream &out,const List<Y> & s);
};

template <class X>
List<X>::List(int n):total(0),max(n){
  check(n>0,"(List<>::List()) bad list size");
  data=new X[max];
  check(data!=NULL,"(List<>::List()) heap overflow");
}

template <class X>
List<X> & List<X>::add(const X &x){
  check(total<max,"(List<>::add()) list overflow");
  data[total]=x;
  total++;
  return *this;
}

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

template <class X>
const X & List<X>::operator[](int n)const{
  check(n>=0 && n<total,"(List<>::[]) range error");
  return data[n];
}

template <class Y>
ostream & operator<<(ostream &out,const List<Y> & s){
  out<<"List: ";
  for(int j=0;j<s.total;j++)
    out<<s[j];
  return out;
}
==========================================================================
4. Below is a program that calls a function to check the syntax of a
line of text. The line should consist of a string of characters that ends
in a new line character ('\n') and satisfies the syntax for S, given by the
diagrams below.  Write the functions needed to perform a correct parse of
a line entered by the user. Note that blanks and tabs are not allowed
between characters.
int main(){
char ch;
cin.get(ch);
S(ch);
check(ch=='\n'," junk at end of line");
cout<<"Parse succeeds\n";
}
In these diagrams I indicate circles with parentheses, (), and rectangles
with square brackets, [].

S                                     A
------>(6)--[A]--(7)---+              ----(4)-------------------(6)---->
  |                    |                         |            |
  +--->(9)--[B]--(4)---+--->                     +<---[B]<----+
  |                    |             B
  +-----[C]------------+             --------(7)----------------------->
                                                  |                  |
C                                                 +<----[C]<---(8)<--+
--------(0)-----------+
   |                  |
   +----(1)-----------+---->
   |                  |
   +----(8)--[S]--(8)-+
==========================================================================
void next(char &ch,char expect){
  if(ch!=expect){
    cerr<<"ERROR: '"<<expect<<"' expected\n";
    exit(1);
  }
  cin.get(ch);
}

void a(char &ch);
void b(char&ch);
void c(char &ch);
void S(char &ch){
  switch(ch){
  case '6':
    cin.get(ch);
    a(ch);
    next(ch,'7');
    break;
  case '9':
    cin.get(ch);
    b(ch);
    next(ch,'4');
    break;
  default: c(ch);
  };
}

void a(char &ch){
  next(ch,'4');
  while(ch=='7')
      b(ch);
  next(ch,'6');
}

void b(char &ch){
  next(ch,'7');
  while(ch=='8'){
    cin.get(ch);
    c(ch);
  }
}

void c(char &ch){
  switch(ch){
  case '0':
  case '1': cin.get(ch); break;
  case '8':
    cin.get(ch);
    S(ch);
    next(ch,'8');
    break;
  default:
    check(false,"'0','1', or '8' expected");
  }
}
==========================================================================
5. Write a well modularized C (as opposed to a C++) program that compiles
using the command g++ -xc and that (1) reads in an int that gives the number
of ints to be read; (2) reads in that many ints; (3) sorts the ints, using
any algorithm you choose; (4) displays the ints (not including the first
int that provides a count of the number of ints) in sorted order.  Your
program can assume that the user does, indeed, enter the correct number of
numbers and then enters only ints.

==========================================================================
#include <stdio.h>
#include <stdlib.h>

void load(int **list,int *tot);
void sort(int *list,int total);
void display(int *list,int total);

int main(){
  int *list, total;
  load(&list,&total);
  sort(list,total);
  display(list,total);
}

void load(int **list,int *tot){
  int j,*temp;
  scanf(" %i",tot);
  temp=malloc(*tot*sizeof(int));
  if(temp==NULL){
    printf("Heap overlow\n");
    exit(1);
  }
  for(j=0;j<*tot;j++){
    printf("loading %i\n",j);
    scanf(" %i",&temp[j]);
  }
  *list=temp;
}

void sort(int *list,int total){
  int j,done,temp;
  done=0;
  while(done==0){
    done=1;
    for(j=0;j<total-1;j++)
      if(list[j]>list[j+1]){
        temp=list[j];
        list[j]=list[j+1];
        list[j+1]=temp;
        done=0;
      }
  }
}

void display(int *list,int total){
  int j;
  for(j=0;j<total;j++)
    printf(" %i",list[j]);
}
==========================================================================
6. Write the C (as opposed to C++) code for two functions used to manage
an unordered linked list used for storing ints. The first, addFirst(),
should a link at the beginning of the list, and display() should display
the contents of the list. The code for the two functions should be such
that the following code would compile and produce the indicated output.
You can assume you have check(int b,char*mess) available.
 struct A{
    int dat;
    struct A *next;
 };

   struct A *head;
   head=NULL;
   head=addFirst(head,6);
   head=addFirst(head,5);
   display(head); // [5]->[6]->NULL
==========================================================================
struct A * addFirst(struct A *hd,int j){
  struct A *temp;
  temp=malloc(sizeof(struct A));
  if(temp==NULL){
    printf("ERROR: heap failure\n");
    exit(1);
  }
  temp->next=hd;
  temp->dat=j;
  return temp;
}

void display(struct A *hd){
  while(hd!=NULL){
    printf("[%i]-->",hd->dat);
    hd=hd->next;
  }
  printf("NULL\n");
}
==========================================================================
7. a. Assume you are using a hash table to store ints, where the int itself
provides the hash number.  Assume that a quadratic probe is used to handle
collisions. For the table below, give the indices of the locations visited,
in order, when 227 is stored in the table.  (By some strange coincidence
all previous items stored had values that matched the indices)
        0  1  2  3  4  5  6  7  8  9 10
      ----------------------------------
      | 0|  |  |  |  | 5|  | 7| 8|  |10|
      ----------------------------------
b.  Now write a C++ function, present(), that determines whether a given
non-negative int is in the hash table. It should assume that empty locations
in the table are represented by -1. The call to present() would look like

   int table[11],n;
   ....
   ....
   if(present(table,n))
     cout<<n<<" is in the table\n";
==========================================================================
Start looking for free space (or 227 already being stored) at 227%11=7,
then (7+1*1)%11=8, then (7+2*2)%11=0, then (7+3*3)%11==5, then (7+4*4)%11=1,
where we finally find a free space to store 227.

bool present(int table[],int n){
  int rep;
  rep=0;
  while(rep<=6 && table[(n+rep*rep)%11]>=0
            && table[(n+rep*rep)%11]!=n){
    //    cout<<"Probing "<<(n+rep*rep)%11<<endl;
    rep++;
  }
  return table[(n+rep*rep)%11]==n;
}
==========================================================================
8. Recall that StCalc had the following methods that operated on the
stack: push(), pop(), add(), sub(), mul(), and div(). Also, recall that
the Calc method  "Calc & enter(double d).  Assume that you implement a
method in FullCalc for evaluating expressions of the form
  push 2*(3+4*5)
by doing all the calculations with StCalc and Calc instructions.  Give a
sequence of StCalc and Calc instructions that the FullCall method would
generate for evaluating the expression below.  Thus, I am asking for an
answer that looks like
   enter(3)
   push()
   ....

   push 2*(34.4-6*(9-3-4)/18)+42
========================================================================
    enter(2)
    push()
    enter(34.4)
    push()
    enter(6)
    push()
    enter(9)
    push()
    enter(3)
    push()
    sub()
    enter(4)
    push()
    sub()
    mul()
    enter(18)
    push()
    div()
    sub()
    mul()
    enter(42)
    push()
    add()
==========================================================================