COP 3530
   Section U03
   Spring 2016



                             FINAL EXAM ANSWERS
                             ==================



   QUESTIONS
   ---------

   Question 1. (35 points)

    public static <T extends Comparable<? super T>>
        BinaryNode<T> buildTheBinarySearchTree(T[] arr)
    {
        // check for null or empty array
        if (arr == null || arr.length == 0)
            return null;
        if (arr.length == 1)
            return new BinaryNode<>(arr[0], null, null);
        // find the height of the tree
        int h = height(arr.length);
        // form a tree from the array slice arr[0:arr.length - 1]
        return buildTheBinarySearchTree( arr, 0, arr.length -1, h);
    }

    // generate a complete tree from an array slice arr[low:high]
    // height is the height of the tree
    private static <T extends Comparable<? super T>>
        BinaryNode<T> buildTheBinarySearchTree(T[] arr, int low, int high,
                int height)
    {

        // check for null array
        if (low > high)
            return null;
        if (low == high)
            return new BinaryNode<>(arr[low], null, null);
        int size = high - low + 1;
        // find the number of items in each subtree when the height
        // of the right subtree is height-2
        int nodesOnTheRight = (int) (Math.pow(2.0, height -1)  - 1);
        int nodesOnTheLeft = size - nodesOnTheRight - 1;
        int rootPosition = low + nodesOnTheLeft;

        // check if the height of the right subtree is height - 1
        if ( (double) size >= Math.pow(2.0,height) + Math.pow(2.0,height-1) -1 )
        {
            nodesOnTheLeft = (int) (Math.pow(2.0, height) - 1 );
            nodesOnTheRight = size - nodesOnTheLeft -1 ;
            rootPosition = low + nodesOnTheLeft;
            return new BinaryNode<>(arr[rootPosition],
               buildTheBinarySearchTree(arr, low, rootPosition -1, height -1),
               buildTheBinarySearchTree(arr, rootPosition+1, high, height - 1));
        }
        return new BinaryNode<>(arr[rootPosition],
               buildTheBinarySearchTree(arr, low, rootPosition -1, height -1),
               buildTheBinarySearchTree(arr, rootPosition+1, high, height -2));
    }

    // return the height of the complete tree with size items
    // assume size > 1
    private static int height(int size)
    {
        int h = 0; // the height
        int prod = 1; // holds 2**(h-1)
        while ( prod <= size )
        {
            // increase h and prod
            h++;
            prod = prod * 2;
        }
        return h - 1;
    }




   Grading Criteria:
   -----------------

   1. Finding the root location : -18 points

   2. Syntax errorrs: -1.5 points for each

   3. Using arrays instead of array slices: -2 points

   4. Not using System.arraycopy: -2 points

   5. Not forming the root node: -3 points

   6. Up to 6 points for trying

   7. Logical errors: at least -3 points

   Question 2. (28 points)

    1. O(nlog n)
    2. O( log n)
    3. O( log n)
    4. O( n)
    5. O( log n)
    6. O(1)
    7. O(n*n)
    8. O( log n)
    9. O(n)
   10. O(1)
   11. 22
   12. O( log n)
   13. O(n)
   14. O(nlog n)

   Grading Criteria:
   -----------------
   2 points for each correct answer


   Question 3. (30 points)

    The first program uses an array as a counter.

    // return the ith item of the tree with root this, 
    // in the postorder traversal
    // throw a NoSuchElementException if this is not possible
    public BinaryNode<T> postorderGet(int i)
    {
        if (i < 0 )
            throw new NoSuchElementException();
        // arr[0] is a count. 
        // It shows how many items we have traversed in postorder
        int[] arr = {-1}; 
        // postorderGet returns the ith node in postorder, or null
        // if i is too high
        BinaryNode<T> out = postorderGet(arr,i);
        if (out == null)
            throw new NoSuchElementException();
        return out;
    }        
    
    // returns the ith node in postorder or null if i is too high
    // arr[0] shows how many items we have processed so far
    private BinaryNode<T> postorderGet(int[] arr, int i)
    {
        // process the root
        BinaryNode<T> out = null; // initially out is null
        if (left != null) // search the left subtree
            out = left.postorderGet(arr,i);
        if (out != null)
            return out; // i is the left subtree
        if (right != null)
            out = right.postorderGet(arr,i);
        if ( out != null)
            return out;
        // process the root
        arr[0] += 1; // inxcrease the count
        if ( arr[0] == i)
            out = this;
        return out;
    }
    
    The second program stores all the nodes along the way.

    // return the ith item of the tree with root this, 
    // in the postorder traversal
    // throw a NoSuchElementException if this is not possible
    public BinaryNode<T> postorderGet(int i)
    {
        if (i < 0 )
            throw new NoSuchElementException();
        ArrayList<BinaryNode<T>> nodes = new ArrayList<>();
        postorderGet(i, nodes);
        if (nodes.size() <= i)
            throw new NoSuchElementException();
        return nodes.get(i);
    }        
    
    // postorderGet(i,list) creates a list with the first i nodes
    // listed in postorder
    private void postorderGet(int i, ArrayList<BinaryNode<T>> nodes)
    {
        if (left != null)
            left.postorderGet(i,nodes);
        if ( i + 1 == nodes.size())
            return; // i is the left subtree
        if (right != null)
            right.postorderGet(i, nodes);
        if ( i + 1 == nodes.size())
            return;
        // process the root
        nodes.add(this);  
    }
    
    
    Grading Criteria:
    -----------------

    1. If you chose the second method you loose 10 points for wasting
       memory. If you  use size you also loose 10 points for inefficiency.
 
    2. -3 points for each design error.

 

   Question 4. (20 points)

   run:
   TESTING PRIORITY QUEUES
   =======================



   We form a priority queue of names.
   We add the names Tomato, Papa Bill, Turtleman, Tornado, Poco Pelo,
   Baby Trevor, The Pastor, Little Girl, Guru, Papa Smurf, Shrek.
   The heap of friends:
   null
   Baby Trevor
   Guru
   Papa Bill
   Little Girl
   Papa Smurf
   Poco Pelo
   Papa Bill
   The Pastor
   Turtleman
   Tornado
   Tomato
   Shrek
   BUILD SUCCESSFUL (total time: 0 seconds)

   Grading Criteria:
   -----------------
   1. -1 point for each name that is out of place.
   2. -2 points if you don't print the null

   Question 5. (15 points)

   

      Index           Linear Probing      Quadratic Probing
    --------------------------------------------------------
        0
    --------------------------------------------------------
        1                    21                   21
    --------------------------------------------------------
        2
    --------------------------------------------------------
        3                                         34
    --------------------------------------------------------
        4                    54                   54
    --------------------------------------------------------
        5                    64                   64
    --------------------------------------------------------
        6                    34                   25
    --------------------------------------------------------
        7                    25
    --------------------------------------------------------
        8                    78                   78
    --------------------------------------------------------
        9
    --------------------------------------------------------


      Grading Criteria:
      -----------------
      For each number that is in the wrong box you loose 1 point.