CSE 17 Final Examination    Wednesday  20 December 2006
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<SUGGESTED ANSWERS>>>>>>>>>>>>>>>>>>>>>>
1.  For each of the questions below, assume the following data are processed
in the given order:    11, 26, 64, 63, 76, 50.
   (a) Assume the data are entered into a binary tree, where balance is
       maintained using the algorithm discussed in class. Draw the tree after
       each number is added to the tree.
   (b) Assume the data are entered into a B-tree of order 1, where the tree
       is maintained as a B-tree using the algorithm discussed in class. Draw
       the tree after each number is added to the tree.
   (c) Assume the data are stored in an array of length 13 using the hash
       techniques discussed in class, where collisions are handled using a
       quadratic probe.  Assume the number itself is the hash number. Show
       the status of the array after each number is added to the array.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
(a)    11
             11
               \
               26
                   11                26
                     \    ----->    /  \
                      26           11  64
                        \
                        64
         26
        /  \
      11   64
          /
         63

         26
        /  \
      11   64
          /  \
         63  76

         26                      63
        /  \                    /   \
      11   64       ------->   26    64
          /  \                /  \     \
         63  76              11  50     76
        /
       50
(b)   11
            11, 26
                    11,26,64 --->   26
                                   /  \
                                 11   64
        26
       /  \
     11  63,64
                   26       --->     26   64
                  /  \              /   |   \
                11  63,64,76       11  63    76
      26   64
     /   |   \
   11  50,63  76
(c)
        0   1   2   3   4   5   6   7   8   9  10  11  12
       --------------------------------------------------
       26  50  63                  76              11  64
       --------------------------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2.  Suppose you have the problem of determining whether any two entries in an
array are the same. Describe an algorithm for solving this problem and give
the details of how to determine its complexity (how quickly the solution grows
a function of the number of entries).
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Easy algorithm:  boolean dup=false;
                 int outer,inner;
                 outer=0;
                 while(!dup && outer<array.length-1)
                   {inner=outer+1;
                    while(!dup && inner<array.length)
                      {dup=array[inner]==array[ouuter];
                       innner++;
                       }
                    outer++;
                   }
      The most frequent operation is !dup. In the worst case, there are
      no duplicates.  Let n=array.length.  On the first pass of outer loop
      we repeat the inner loop n-1 times, the second pass n-2 times, ...
      Thus we have (n-1) + (n-2) + ... 1 =n(n-1)/2 repetitions.  Thus we
      have O(n*n).
Harder algorithm:  Mergesort the array.  Then apply
                  boolean dup=false;
                  int k=0;
                  while(!dup && k<array,length-1)
                   {dup = array[k]==array[k+1];
                    k++;
                   }
  The most frequent operation is !dup, which occurs at most n times.
  The mergesort is O(n log(n))===> the complete algorithm is O(n log(n) )
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3. (a) Describe in detail two different ways to implement a stack.  Discuss
       the advantages and disadvantages of each implementation.
   (b) Assume you are to develop a class for each of the problems below.
       State what underlying data structure should be use for each class
       (e.g., a stack) and explain how it would be used.
       (i)  model the waiting line at a bank
       (ii) model the waiting line at a grocery store that has three
            kinds of registers, those for customers with 10 items or less,
            those for customers with 20 items or less, and those for any
            customer.
       (iii) organize the student records at Lehigh so that the students
            can be listed in order according to student ID number.
       (iv) organize the student records at Lehigh so that any given record
            can be very quickly retrieved, using the student ID number.
       (v)  write the software that controls the "up arrow" key in Dr. Java
            when you are in the "interactions" pane.  Recall that the "up
            arrow" key cycles back through the preveious commands written
            in the interactions pane in the reverse of the order in which
            they were written.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
(a)  (i)  Have an array of "frames" and an int stackPtr;  The stackPtr always
          has the index of the top frame in the stack and starts at -1, when
          the stack is empty. The push consists of incrementing stackPtr and
          storing the new frame.  The pop consists of decrementing the
          stackPtr.  Crash when you pop an empty stack or when you push a
          full stack.
     (ii) Maintain the stack as a linked list, with the stackPtr pointing to
          the top link in the stack.  Each link has a pointer to the next
          link of the stack. Push onto the stack by putting a new link at the
          front of the stack and having the stackPtr point to the new link.
          Pop the stack by moving the stackPtr forward a link.
    The array implementation is more efficient and easier to maintain than the
    linked list, but the linked list can be used in situations when you do not
    know the size of the stack ahead of time. (You could use the array
    implementation in this situation, but you would have the problem of
    growing the array, which involves quite a bit of maintenance)
(b)   (i)   queue:  Have a queue of customers.  Each teller, when free, would
                    remove the next customer from the queue.
      (ii)  queue:  Maintain a queue for each register, where the register
                    serves each customer in the queue in order.
      (iii) Binary tree, or sorted list with binary search for an entry.
                    Use the student ID to order the list.
      (iv)  hash table:  Make an array at least twice as big as the number of
                        students and of prime size.  Use the ID as the hash
                        number. Use a quadratic probe to enter students in
                        the hash table.
      (v)   stack  (or, better, a doubly linked list with back and forward
            pointers):  Maintain a stack of strings, one for each command
                        entered.  Push them on the stack in the order made.
                        For each stroke of the up-arrow, pop off the top of
                        the stack and display it.  (Append a string for each
                        command entered. Keep a pointer to the front.  When
                        the up-arrow is stroked go back one command, but don't
                        go off the bottom of the list.  When the down arrow
                        is stroked go forward one command, but don't go past
                        the top of the list.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4.  Consider the abstract data type of a record for storing grades. The
record should include the name of the item being graded (e.g., "Test 1")
and the grade, on a scale of 0 to 100.  Write the Java code for this class,
calling it "Grade."  Then write a subclass of this class, WeightedGrade,
that stores the weight of the grade's contribution to the overall grade,
on a scale of 0.0 to 1.0.  Your implementation need only enable the following
code to compile and produce the indicated output.
   Grade g=new Grade("Test 1",23);
   System.out.println("The score on "+g.getLabel()+" = "+g.getScore());
     //The score on Test 1 = 23
   g.setScore(42);
   System.out.println(g);   //[Test 1, 42]
   WeightedGrade h=new WeightedGrade("Test 2",76,0.3);
   System.out.println("The weight is "+h.getWeight()); //The weight is 0.3
   System.out.println(h); // {[Test 2, 76], 0.3}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 class Grade{
   protected String label;
   protected int score;
   public Grade(String s,int g){
     label=s;
     check(label!=null,"Null label");
     score=g;
     check(g>=0 && g<=100,"Grade out of range");
   }
   public void setScore(int g){
     score=g;
     check(g>=0 && g<=100,"Grade out of range");
   }
   public String getLabel(){return label;}
   public int getScore(){return score;}
   public String toString(){
     return "["+label+", "+score+"]";
   }
   protected static void check(boolean b,String mess){
     if(!b){
       System.err.println("ERROR: "+mess);
       System.exit(1);
     }
   }
 }

 class WeightedGrade extends Grade{
   private double weight;
   public WeightedGrade(String s, int g, double d){
     super(s,g);
     weight=d;
     super.check(d>=0.0 && d<=1.0,"Weight out of range");
   }
   public double getWeight(){return weight;}
   public String toString(){
     return "{"+super.toString()+", "+weight+"}";
   }
 }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
5.  Write a method sort() that assumes that all entries of an array of ints
    are defined and sorts the entries in ascending order. Given int x[];,
    the call to sort would be sort(x).
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
I choose the bubble sort
    public static void sort(int x[]){
      boolean sorted;
      do{
        sorted=true;
        for(int j=0;j<x.length-1;j++)
          if(x[j]>x[j+1]){
            int temp=x[j];
            x[j]=x[j+1];
            x[j+1]=temp;
            sorted=false;
        }
      }while(!sorted);
    }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6.  Assume we have the class Node and the variable root as declared below.
Write an efficient method show() that assumes root is the root of a binary
tree, where a left  in-order traversal of the tree would list the entries
in the tree in ascending order and that displays to the screen all the
entries in the tree that lie between two given doubles.  For example, the
call show(root, 17.3, 198.4) would display on the screen all entries between
17.3 and 198.4, inclusive. Note that the data and keys are the same.
                            class Node{
                                public double key;
                                public Node left, right;
                            }
                            Node root;
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
     public static void show(Node rt,double low,double high){
       if(rt!=null && rt.key>=low && rt.key<=high){
         show(rt.left,low,high);
         System.out.print(" "+rt.key);
         show(rt.right,low,high);
       }
     }
 }

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7.  Write a method sortAFile() that reads data from the file "input", sorts
    them (by calling the method sort from question 5), and lists the data in
    ascending order in the file "output."  The data in "input" are supposed
    to (but are not guaranteed to) be all ints and are supposed to (but are
    not guaranteed to) consist of exactly 100 entries.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
import java.io.*;
import java.util.Scanner;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
  public static void sortAFile(){
    Scanner inp=null;
    int x[]=new int[100];
    try{
      inp=new Scanner(new FileInputStream("input"));
    }catch(FileNotFoundException e){
      System.err.println("Could not find the file 'input'");
      System.exit(1);
    }
    try{
       PrintWriter out=new PrintWriter(new FileOutputStream("output"));
       for(int j=0;j<100;j++)
         x[j]=inp.nextInt();
       sort(x);
       for(int j=0;j<100;j++)
         out.print(x[j]+" ");
       out.close();
    }catch(FileNotFoundException e){
      System.err.println("Could not find the file 'output'");
      System.exit(2);
    }catch(InputMismatchException e){
      System.err.println("Non-integer encountered");
      System.exit(3);
    }catch(NoSuchElementException e){
      System.err.println("EOF encountered");
      System.exit(4);
    }

  }

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8.  Write a generic class Prettify whose only purpose is to display objects
    surrounded by strings that make the output prettier.   The class should
    enable the following code to compile and produce the indicated output
    (the class Grade below is from question 5).
      Prettify <Integer> x=new Prettify<Integer>("int(",6,")");
      System.out.println(x);  //int(6)
      Prettify <Grade> y=new
          Prettify<Grade>( "-->",new Grade("Final",42),"<--");
      System.out.println(y); //-->[Final, 42]<--
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class Prettify<X>{
  private X obj;
  private String left,right;
  public Prettify(String a,X x,String b){
    left=a;
    obj=x;
    right=b;
  }
  public String toString(){
    return left+obj+right;
  }
}

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>