Review Exercises (Set B)

  1. Show the traces for each sort requested below when applied to the array shown.

    { 'f', 'b', 'a', 'h', 'c', 'd', 'g', 'e' }
    1. Merge Sort
    2. Quick Sort (in-place, without the initial shuffle or improvements)
  2. Describe an improvement that could be made to the basic in-place quick sort algorithm that would reduce its recursive overhead.

  3. The cost function for merge sort can be written as follows. Show how to solve this recurrence relation to derive the Big O cost for merge sort. $$C(n) = 2 C(\frac{n}{2}) + n \quad ; \quad C(1) = 0$$

  4. Write the recurrence relation for the cost function that gives the number of comparisons in sorting $n$ elements using quick sort, in both best case and worst case.

  5. If the items are inserted into a binary search tree in random order, the worst-case height can be O( __ ), but the expected height is O( __ ). (Fill in the blanks)

  6. A binary search tree is a tree in which:

    • Each node contains a value, and up to two children known as left and right.
    • All nodes in the left subtree contain values strictly less than this node's value.
    • All nodes in the right subtree contain values strictly greater than this node's value.
    Suppose that a binary search tree is implemented with the following internal node class and addNode() method (note the additional reference to parent):
    public class Node {
       int x;
       Node left;
       Node right;
       Node parent;
       
       public Node(Node p, int v){
          parent = p;
          x = v;
       }
    }
    
    static void addNode(Node n, int v) {
       if (v < n.x) {
          if (n.left == null) {
             n.left = new Node(n, v);
          } 
          else {
             addNode(n.left, v);
          }
       } 
       else {
          if (n.right == null) {
             n.right = new Node(n, v);
          } 
          else {
             addNode(n.right, v);
          }
       }
    }
    

    Part I - Draw the binary search tree that the main method below would generate:

    public static void main(String[] args) {
    
       Node root = new Node(null, 8);
    
       addNode(root, 3);
       addNode(root, 2);
       addNode(root, 1);
       addNode(root, 4);
       addNode(root, 9);
    }
    

    Part II - List the node keys of the following example binary search tree in pre-order, in-order, and post-order, respectively.

    Part III - Describe an algorithm (or write down the pseudocode) for a method called findBLT which finds the biggest value strictly less than some $x$ in a binary search tree.

    If there is no value less than $x$ the method should return $−1$. The main below gives examples of using this method against the example tree in Part II, above.

    Note: x is not necessarily in the tree. Also, assume all numbers in the tree are positive. Finally, the method should run O$(\ln n)$ i.e. do not traverse the whole tree.

    public static void main(String[] args) {
    
       Node root = new Node(null, 10);
    
       //...
    
       System.out.println(findBLT(root, 20));  //prints 19
       System.out.println(findBLT(root, 6));   //prints 4
       System.out.println(findBLT(root, 4));   //prints -1
       System.out.println(findBLT(root, 16));  //prints 15
    }
    
  7. Consider the following list: Q, R, F, -, Y, B, N, - , Q, M, F, -, and an initially empty priority queue implemented with a heap (where the highest priority is given to the letter closest to "Z" in the alphabet). Working from left to right, if the element is a letter, it is inserted into the priority queue -- if it is "-", the highest priority element is removed. Show the state of the heap in array form after each insertion/removal.

  8. The keys T, F, B, S, D, I, Y, N, Q, M are inserted into an initially empty red-black tree in that order. Draw the structure of the tree after each insertion.

Solutions

    1.  
      Order before mergesort application:
      f  b  a  h  c  d  g  e  
      
      0  1  2  3  4  5  6  7  
      ------------------------
      b  f  a  h  c  d  g  e  
      a  b  f  h  c  d  g  e  
      a  b  f  h  c  d  e  g  
      a  b  c  d  e  f  g  h  
      
      Order after mergesort application:
      a  b  c  d  e  f  g  h  
      
    2.  
      Order before quicksort application:
      f  b  a  h  c  d  g  e  
      
      lo pivot hi  0  1  2  3  4  5  6  7  
      -------------------------------------
                   f  b  a  h  c  d  g  e  
                   f  b  a  h  c  d  g  e  <-- if we had shuffled things, 
                   f  b  a  e  c  d  g  h      it would have been at this point
      0    5   7   d  b  a  e  c  f  g  h  
                   d  b  a  c  e  f  g  h  
      0    3   4   c  b  a  d  e  f  g  h  
      0    2   2   a  b  c  d  e  f  g  h  
      0    0   1   a  b  c  d  e  f  g  h  
      6    6   7   a  b  c  d  e  f  g  h  
      
      Order after quicksort application:
      a  b  c  d  e  f  g  h  
      
  1. Use insertion sort when the number of elements to be sorted is small (i.e., typically, somewhere between 5 and 15)
  2. see the notes on the merge sort
  3. see the notes on the quick sort cost analysis
  4. $n$, $\ln n$
  5.  
    1.  
                   |
             +-----8--+
             |        |
          +--3--+     9
          |     |               
       +--2     4        
       |
       1
      

    2. pre-order: 10, 6, 4, 9, 14, 20, 15, 19
      in-order: 4, 6, 9, 10, 14, 15, 19, 20
      post-order: 4, 9, 6, 19, 15, 20, 14, 10

    3. While answers will vary, the essential cases one must consider are the following:

      • If $x$ has a left subtree, then the BLT is the maximum value of its left subtree.
      • If $x$ has no left subtree and is the right child of x.parent, then the BLT is x.parent.
      • If $x$ has no left subtree, and is the left child of x.parent, then we must find x's first ancestor y such that y is the right child of y.parent. The BLT is y.parent.
      • In all other cases, the BLT is null.
  6.  
    (recall, the priority queue keeps track of its size, 
    so null elements of the array at positions greater 
    than size are not shown, although the first position 
    is empty, as indicated by the "-"'s below)
    -Q
    -RQ
    -RQF
    -QF
    -YFQ
    -YFQB
    -YNQBF
    -QNFB
    -QQFBN
    -QQMBNF
    -QQMBNFF
    -QNMBFF
    
  7.  
     |          
    -T-         
    
    (no nodes are red)
    
        |             
     +--T-            
     |                
    -F-               
                      
    (F is red)
    
        |             
     +--F--+          
     |     |          
    -B-   -T-         
                      
    (no nodes are red)
    
        |                         
     +--F-----+                   
     |        |                   
    -B-    +--T-                  
           |                      
          -S-                     
                                  
    (S is red)
    
           |                      
        +--F-----+                
        |        |                
     +--D-    +--T-               
     |        |                   
    -B-      -S-                  
                                  
    (B, S are red)
    
                 |                                        
           +-----S--+                                     
           |        |                                     
        +--F--+    -T-                                    
        |     |                                           
     +--D-   -I-                                          
     |                                                    
    -B-                                                   
                                                          
    (F, B are red)
    
                 |                                        
           +-----S-----+                                  
           |           |                                  
        +--F--+     +--Y-                                 
        |     |     |                                     
     +--D-   -I-   -T-                                    
     |                                                    
    -B-                                                   
                                                          
    (T, F, B are red)
    
                    |                                     
           +--------S-----+                               
           |              |                               
        +--F-----+     +--Y-                              
        |        |     |                                  
     +--D-    +--N-   -T-                                 
     |        |                                           
    -B-      -I-                                          
                                                          
    (F, I, B, T are red)
        
                 |                                        
           +-----N-----+                                  
           |           |                                  
        +--F--+     +--S-----+                            
        |     |     |        |                            
     +--D-   -I-   -Q-    +--Y-                           
     |                    |                               
    -B-                  -T-                              
                                                                                                             
    (B, T is red)
                                                        
                    |                                     
           +--------N-----+                               
           |              |                               
        +--F-----+     +--S-----+                         
        |        |     |        |                         
     +--D-    +--M-   -Q-    +--Y-                        
     |        |              |                            
    -B-      -I-            -T-                           
    
    (B, I, T are red)