CSc 17 Final Examination   Tuesday  19 December 2000
   >>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<
   1.  Write the declaration for a class FlipFlop and then write the
   definition of its member functions and operators.  Instances of class
   FlipFlop store either the value of 0 or 1.  If two instances of FlipFlop
   are added the result is a FlipFlop which has the value 0 if both the
   instances being added are storing the number 0; otherwise the resulting
   FlipFlop has the value 1.  You need only declare and implement enough
   functions and operators so that the following code would compile.
       FlipFlop  a,b(0);
       a.set(1);
       cout<<"The FlipFlop has the value "<<a.get()<<endl;
       cout<<a<<" + "<<b<<" = "<<(a+b)<<endl;

       class FlipFlop{
        public:
          FlipFlop();
          FlipFlop(int n);
          void set(int n);
          int get();
          FlipFlop operator+(const FlipFlop&a);
          friend ostream & operator<<(ostream &out, const FlipFlop & a);
        private:
          int value;
      };

      FlipFlop::FlipFlop(){ value=0;}
      FlipFlop::FlipFlop(int n) {set(n);}
      void FlipFlop::set(int n){if(n<0 || n>1)
                                   n=0;
                                value=n;
                          }
      int FlipFlop::get(){ return value;}
      FlipFlop FlipFlop::operator+(const FlipFlop&a){
            if(value==0 && a.value==0)
              return FlipFlop(0);
            return FlipFlop(1);
      }
      ostream & operator<<(ostream &out,const FlipFlop &a){
        out<<"FlipFlop("<<a.value<<")";
        return out;
      }


   2.  Write a recursive function MATCH. It is used to determine whether
   entries in two arrays of ints are identical.  Given int a[20],b[30];
   the call MATCH(a,b,2,10) returns true if and only if the entries
   a[2] through a[10] are identical to and in the same order as the
   entries b[2] through b[10].  You MUST use the following recursive
   algorithm.  If the two sets of entries to compare have indices between
   n and m inclusive, the arrays match if the mth entries are the same and
   the rest of the two arrays match.
     bool MATCH(int a[],int b[], int low, int high){
       if(high<low)
         return true;
       return a[high]==b[high] && MATCH(a,b,low,high-1);
     }

   3.  Assume you have the Link class below.  Write a function LOOP which
   turns a linked list into a "ring."  The function LOOP assumes that the
   variable HEAD, of type *Link, points to a "properly formed" link list
   (that is, it has no loops in it, or more precisely no Link has more than
   one Link pointing to it).  If HEAD is of type *Link, after the call
   LOOP(HEAD) the Link that used to be last in the list now points to HEAD.
     class Link{
      public:
       int key;
       Link *next;
     };

    void LOOP(Link * root){
      //pre-condition: root!=NULL and points to a proper linked list
      Link *temp;
      temp=root;
      while(root->next!=NULL)
        root=root->next;
      root->next=temp;
    }

   4.  Assume the class BiNode below is used to construct a binary tree.
   Write a function INTREE which returns true if and only if a given entry
   or its negative is in the tree.  If ROOT is of type *BiNode and N is of
   type int the call INTREE(ROOT, N) would return true if and only if the
   value N or -N is in the tree.
     class BiNode{
       public:
         int key;
         BiNode *child[2];
     };

     bool INTREE(BiNode *rt,int n){
       if(rt==NULL)
         return false;
       return rt->key==n || rt->key==-n ||
        INTREE(rt->child[0],n) || INTREE(rt->child[1],n);
     }

   5.  This is a non-recursive variation of question 2.  Write a single
   (template) function MATCH which determines whether two arrays match in the
   way described in question 2. If we have int a[20],b[20];
   double x[30], y[50]; and Link u[10],v[30]; then each of the calls
   MATCH(a,b,2,10), MATCH(x,y,4,12), and MATCH(u,v,5 13) should return true
   if and only if the corresponding arrays have the same entries in the
   same locations.  DO NOT USE RECURSION FOR THIS QUESTION.

    template <class T>
    bool MATCH(T a[], T b[],int low, int high){
      bool temp;
      temp=true;
      while(temp && low<=high){
        temp=temp && a[low]==b[low];
        low++;
      }
      return temp;
    }

   6.  The selection sort takes the largest entry in an array and puts it
   in the first location. Then it takes the largest of the remaining entries
   and puts it in the second location, etc.  Use this algorithm to write
   the function SORT.  If we have double x[300]; and int n; then the entries
   x[0]...x[n-1] should be in descending order after the call SORT(x,n).

     void SORT(double x[],int n){
       int maxLoc,temp;
       for(int i=0; i<n-1;i++){
         maxLoc=i;
         for(int loc=i+1; loc<n; loc++)
           if(x[loc]>x[maxLoc])
            maxLoc=loc;
         temp=x[maxLoc];
         x[maxLoc]=x[i];
         x[i]=temp;
      }
    }

   7.  (a) Write a function DUPLICATE which returns true if and only if any
   two entries in an array are the same.  If we have x and n declared as in
   question 6, then the call to DUPLICATE would be DUPLICATE(x,n). It would
   return true if any two of the entries x[0]...x[n-1] are the same.
      bool DUPLICATE(double x[],int n){
        int outer, inner;
        bool temp;
        temp=false;
        outer=0;
        while(outer<n-1 && !temp){
          inner=outer+1;
          while(inner<n && !temp){
            temp=x[inner]==x[outer];
            inner++;
          }
          outer++;
        }
        return temp;
     }

       (b) Determine the complexity of DUPLICATE, i.e., determine how the
   time to execute DUPLICATE changes as a function of n.
        To simplify, assume there are no duplicates.  Then, if there are
        n items, for outer==0 inner goes from 1 to n-1, for outer==1
        inner goes from 2 to n-1, etc.  Thus, the number of repetitions
        is  n-1 + n-2 + ... + 1 = n(n-1)/2 which is O(n*n).

   8.  Assume that classes STACK and QUEUE implement the usual stack and
   queue operations for storing ints.  Write function LIST which reads
   ints from a file and uses an instance of STACK and an instance of QUEUE to
   help list the entries in the file in two columns.  The first column lists
   the entries in the order in which they appear in the file and the second
   column lists the entries in reverse order.  If we have ifstream fin; the
   call to LIST would be LIST(fin).  The output would appear on the screen.
   Your function should NOT use any arrays. It can assume there are less than
   100 entries in the file.
      void LIST(istream & fin){
        STACK  st(100);
        QUEUE q(100);
        int temp;
        fin>>temp;
        while(fin.good()){
          st.push(temp);
          q.enqueue(temp);
          fin>>temp;
        }
        while(!q.empty())
         cout<<q.dequeue()<<"   "<<st.pop()<<endl;
      }

   9.  A certain text file is supposed to contain a list of lines, each line
   consisting of a Lehigh student's intials.  Write a function LEHIGHID which
   echoes the file to the screen.  Any line which does not start with proper
   initials should have an asterisk (*) appended to it.  Proper initials
   should start at the beginning of the line and must consist of three
   uppercase letters, followed by the end of line. If fin is declared as in
   question 8, the call to LEHIGHID would be LEHIGHID(fin).

       void getch(istream &fin,char &ch){
         if(!fin.eof())
           fin.get(ch);
         if(fin.eof())
           ch='\n';
         if(ch!='\n')
           cout<<ch;
       }
      void LEHIGHID(istream &fin){
       char ch;
       bool ok;
       int j;
       getch(fin,ch);
       while(!fin.eof()){
          ok=true;
          j=0;
          while(ok && j<3){
           ok=ch>='A' && ch<='Z';
           getch(fin,ch);
           j++;
          }
          ok=ok && ch=='\n';
          while(ch!='\n')
           getch(fin,ch);
          if(!ok)
           cout<<'*';
          cout<<endl;
          getch(fin,ch);
       }
      }


   10. (a)  Suppose we have the following tree maintained as a heap:
                         40
                       /    \
                      38    30
                    /   \  /  \
                   18  16  28  26
        (i) Using the algorithms discussed in class for maintaining a
        heap, show the heap above after the number 60 is added to it.
                         40                     60
                       /    \                 /     \
                      38    30       ==>   40       30
                    /   \  /  \          /    \    /  \
                   18  16  28  26      38     16  28  26
                  /                   /
                 60                 18
        (ii) Using the algirthms discussed in class for maintaining a
        heap, show the heap above after the number 40 has been removed it.

                                                38
                       /    \                 /    \
                      38    30       ==>   18       30
                    /   \  /  \          /    \    /  \
                   18  16  28  26             16  28  26

                         38                     38
                       /    \                 /    \
          ==>         18    30       ==>   26       30
                    /   \  /             /    \    /
                   26  16  28          18     16  28
       (b)  Suppose we have the following tree in which the numbers are
       entered so that balance is maintained and so that an in-order
       traversal of the tree lists the entries in ascending order.
                       15
                    /      \
                  7         17
               /    \      /  \
              5     10    16  18
            /  \   /  \
           4    6  9  11
        (i) Using the algorithms discussed in class for maintaining balance,
        show the  tree above after the number 3 is added to it.
                       15                          7
                    /      \                    /     \
                  7         17                5       15
               /    \      /  \     ==>    /   \     /   \
              5     10    16  18         4      6   10     17
            /  \   /  \                 /          /  \   /  \
           4    6  9  11               3          9   11 16  18
          /
         3
        (ii) Using the algorithms discussed in class for maintaining balance,
        show the  tree above after the number 12 is added to it.

                       15                         10
                    /      \                    /     \
                  7         17                7        15
               /    \      /  \     ==>    /   \     /   \
              5     10    16  18         5      9  11      17
            /  \   /  \                 / \          \    /  \
           4    6  9  11               4   6         12  16  18
                        \
                        12