0) Review any questions from old exams (test1, test2, test3, or test4),
   especially anything that you may have missed/not understood....


Binary Search Trees
====================
For all questions, assume that you have a typical BSTNode (with Comparable
data, and BSTNodes for left and right), and a BST class with a root of type
BSTNode.  

 1) A reverseOrder traversal prints the elements in a BST in reverse
    order- namely, largest to smallest (whereas an inorder traversal
    prints them smallest to largest).  , write the method
   
          public void reverseOrder()
 
    in the class BST, which implements a reverseOrder traversal.

 2) Assume that you are given method 

         private Comparable yank(BSTNode curr)

    in the BST class which takes a BSTNode and deletes its left-most right
    child, and then returns the data from the node that was just deleted.
    (i.e. from curr, if you went right once, then as far left as possible,
    the data in the node you found would be returned, and the node would
    be delted.  Write the method

     public Comparable delete(Comparable toDel)

   which deletes the first item found in the tree matching toDel,
   and returns the data in the node deleted.  

 3) Write the method 

        public int countLargerThan(Comparable c)

    which returns a count of the number of items larger than c.
    Your method must make use of the BST's properties (i.e
    you should not compare every item in the tree to c in all cases).

 4) Write the method
   
       public int getHeight()
  
    which returns the height of the tree.

 5) Write the method
    
      public boolean isFull()
 
    which returns true if the tree is full, false if it is not.
    Remember that a full tree is a tree in which each node 
    has either exactly 0 or exactly 2 children.
    The empty tree is considered to be full.
   
Heaps
=====
For all coding questions, you may assume that the Heap has a Vector, which
holds Comparables called "data".  You may also assume that the constructor
initalizes the 0 element of the Vector to contain null, and that the Heap
is a min heap.

  6)  Given the following min-heap:

                         23
                       /    \
                    45      56
                  /   \    /
                 53   48  112

      a) show the heap in an array representation.
      b) add 11 to the heap, show all steps
      c) remove min, show all steps

  7) Write the method
       public void add(Comparable c)
     which adds the item to the heap.

  8) Write the method
       public Comparable peek()
     which returns the smallest element in the Heap, without affecting
     the contents of the Heap.
 
  9) Write the method 
      private void heapify(int index)
     which performs the heapify operation in the standard manner
     starting at the given index.

  10) Write the method
       public Comparable removeSmallest()
      which removes the smallest item, and then returns it.

Sorting
=======

   11) Implement the following sorting methods based on the algorithm
       corresponding to the method name:
          a) public Comparable[] bubbleSort(Comparable[] data)
          b) public Comparable[] insertionSort(Comparable[] data)
          c) What is the running time ("Big-Oh") of these two
             algorithms?

   12) You need to write a program that will sort massive ammounts of
       data (say 50 million elements at a time).  The sorting must
       be accomplished quickly, and due to memory constraints,
       you must sort in place [i.e. you may not allocate other arrays].
         a) Which sorting algorithm do you choose?
         b) What is the "Big-Oh" of this algorithm?
         c) Name another algorithm with this same "Big-Oh"
         d) Explain why your choice of algorithm is better than
            the other one with the same running time.

   13) Given the following code:
public class Sort1 {
  public static void printArray(int[] data){
    System.out.print("[");
    for(int i=0;i<data.length;i++)
      System.out.print(" "+data[i]);
    System.out.println(" ]");
  }
  public static void swap(int[] data, int a, int b) {
    int temp=data[a];
    data[a]=data[b];
    data[b]=temp;
  }
  public static void mysterySort(int[] data) {
    mysterySort(data,0,data.length);
  }//mysterySort
  public static void mysterySort(int[] data, int l, int h) {
    int a=l+1;
    int b=h-1;
    int spot;
    printArray(data);
    if(h<=l)
      return;
    while(a<b) {
      while(data[a]<data[l] && a<b) {
        a++;
      }//while(data[a]<data[l] && a<b)
      while(data[b]>data[l] && a<b) {
        b--;
      }//while(data[b]>data[l] && a<b) 
      if(a<b) {
        swap(data,a,b);
      } 
    }//while(a<b)
    if(a<data.length&&data[a]<data[l])
      {
        spot=a;
      }
    else
      {
        spot=a-1;
      }
    swap(data,spot,l);
    mysterySort(data,l,spot);
    mysterySort(data,spot+1,h);
  }//mysterySort
  public static void main(String[] args){
    int[] data={4,3,5,9,1};
    mysterySort(data);
    printArray(data);
  }//main
}//Sort1

**********END CODE*************
    a) Name the sorting algorithm implemented
    b) State the output when the main method is run 
      [hint, you should use your knowledge of how the sort 
       proceeds to help you with this part]

14) Given the following code:
public class Sort2 {
  public static void printArray(int[] data) { 
    System.out.print("[");
    for(int i=0;i<data.length;i++)
      System.out.print(" "+data[i]);
    System.out.println(" ]");
  }
  public static int[] firstHalf(int[] data) {
    int[] ans=new int[data.length/2];
    for(int i=0;i<ans.length;i++) 
      ans[i]=data[i];
    return ans;
  }
  public static int[] secondHalf(int[] data) {
    int[] ans=new int[data.length-data.length/2];
    for(int i=0;i<ans.length;i++) 
      ans[i]=data[i+data.length/2];
    return ans;
  }
  public static int[] mysterySort(int[] data) {
    if(data.length<=1)   
      return data;
    int[] ans=mysteryHelper(mysterySort(firstHalf(data)),
                            mysterySort(secondHalf(data)));
    printArray(ans);
    return ans;
  }
  public static int[] mysteryHelper(int[] t1,int [] t2) {
    int[] ans=new int[t1.length+t2.length];
    int i=0;    int j=0;    int x=0;
    while(i<t1.length&&j<t2.length) {
      if(t1[i]<t2[j]) { 
        ans[x]=t1[i];
        i++;
      } else {
        ans[x]=t2[j];
        j++;
      }
      x++;
    } while(i<t1.length) {
      ans[x]=t1[i];
      x++; i++;
    } while(j<t2.length) {
      ans[x] = t2[j];
      x++; j++;
    } return ans;
  } 
  public static void main(String[] args) {
    int[] data={4,2,6,5,3,9};
    mysterySort(data);
  }//main
}//Sort2

**********END CODE*************
    a) Name the sorting algorithm implemented
    b) State the output when the main method is run 
      [hint, you should use your knowledge of how the sort 
       proceeds to help you with this part]


GUIS
====
            
  15) Write a class MyGUI which uses composition to create a GUI that
      resembles the following:


       +-------------------------------------------+
       | My GUI Program                      _ [] X|
       +-------------------------------------------+
       |                      |                    |
       |                      |                    |
       |a label               |     a button       |
       |                      |                    |
       |----------------------+--------------------|
       |                      |                    |
       |                      |                    |
       |another label         |    another button  |
       |                      |                    |
       +-------------------------------------------+

       where the upper and lower left contain JLabels with the appropriate
       text, and the upper and lower right contain JButtons with the
       appropriate text.

    16) Explain what happens if you do not call setSize and setVisible(true)
        on the JFrame of the GUI program.


    17) Given the following code
        import java.util.*;
        import javax.swing.*;

        public MyClassThatFiresChangeEvents{
             private Vector listeners=new Vector();
             
             public void addChangeListener(ChangeListener cl){
               //YOUR CODE GOES HERE
             }
             public void fireChangeEvent(){
              //YOUR CODE GOES HERE
             }
        }
     
        a) Implement the method addChangeListener for the above class
        b) Implement the method fireChangeEvent for the above class

Definitions
===========

     18) Define the following words:

         o Balanced Tree
         o Full Tree
         o Complete Tree
         o Heap
         o heapify
         o Priority Queue 
         o GUI
         o Component
         o Container
         o Layout Manager
         o JFrame
         o JPanel
         o JLabel
         o JButton
         o JTextField
         o JMenu
         o Event
         o Event Listener
         o Event Registration
         o Semantic Event
         o Low-level Event
         o MVC
         o UI Delegate