Read Algorithms 3.1, 3.5 and 3.2

Recursion Supplement (Optional, but suggested): Tracing Recursion. You do not need to hand in anything for this.

Do the following problems from the text. (Hand in.)

  3.1.10

    Give a trace of the process of inserting the keys
       E A S Y Q U E S T I O N 
    into an initially empty table using SequentialSearchST. How many
    compares (of keys) are involved?  

  3.1.11

    Give a trace of the process of inserting the keys
       E A S Y Q U E S T I O N 
    into an initially empty table using BinarySearchST. How many
    compares (of keys) are involved?

  3.2.1
  
    Draw the BST that results when you insert the keys
       E A S Y Q U E S T I O N
    in that order (associating the value i with the ith key, as per
    the convention in the text) into an initially empty tree. How many
    compares are needed to build the tree?   
   
  3.2.2 

    Inserting the keys in the order A X C S E R H into an
    initially empty BST gives a worst-case tree where every node has one
    null link, except one at the bottom, which has two null links. Give
    five other orderings of these keys that produce worst-case trees.

    You can also describe the constraints that produce this outcome
         --- Things like "insert A first, insert B before C, etc."
  
  3.2.3

    Give five orderings of the keys A X C S E R H that, when
    inserted into an initially empty BST, produce the best-case tree.
  
    You can also describe the constraints that produce this outcome
         --- Things like "insert A first, insert B before C, etc."

  3.2.4

    Suppose that a certain BST has keys that are integers between
    1 and 10, and we search for 5. Which sequence below cannot be the
    sequence of keys examined? 

    a. 10, 9, 8, 7, 6, 5
    b. 4, 10, 8, 6, 5
    c. 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
    d. 2, 7, 3, 8, 4, 5
    e. 1, 2, 10, 4, 8, 5