Due Thursday, 23 April 2009


CPSC 223   Homework #N3   By the Tree, By the Tree, ...

Algorithms may be stated in any language understood by a reasonably intelligent
being with common sense but no specific knowledge of the problem (but CODE MUST
BE WELL COMMENTED).  Solutions are due IN CLASS, not in my mailbox, under my
door, ...  .

REMINDER:  (The Gilligan's Island Rule) When discussing an assignment with
 other students you may write on a board or a piece of paper, but you may not
 take any written record (electronic or otherwise) away from the meeting.
 Moreover, you must engage in a half hour of mind-numbing activity (such as
 watching an episode of Gilligan's Island) before working on the assignment
 again.  This will ensure that you can reconstruct what you learned at the
 meeting, by yourself, using your own brain.


P1. (6 points) Starting with an empty AVL tree,
    a) insert the numbers 2, 5, 1, 7, 4, and 10 in that order, one at a time;
    b) insert the numbers 6, 11, 8, and 9 in that order, one at a time;
    c) insert the numbers 3, and 12 in that order, one at a time, and then
	 delete the number 1 (deletion is not lazy).
    Show the state of the tree after each set ((a)-(c)) of insertions /
    deletions.  [You may show the state after each individual operation, but be
    sure to label each state shown with the operation(s) that lead to it.]


P2. (6 points) Starting with an empty 2-3 tree where keys are stored in every
    node,
    a) insert the letters B, D, H, A, I, and E in that order, one at a time;
    b) insert the letters F and G in that order, one at a time;
    c) delete the letters A and E in that order, one at a time.
    Show the state of the tree after each set ((a)-(c)) of insertions /
    deletions.

    Note:  You may not use lazy deletion in part (c).  You may show the state
     after each individual operation, but be sure to label each state shown
     with the operation(s) that lead to it.


P3. (6 points) Show the state of the min heap (either using the sequential
    representation or as a tree) after each of the following sets of
    operations.  [You may show the state after each individual operation, but
    be sure to label each state shown with the operation(s) that lead to it.]

    a. Starting with an empty min heap, insert the ten letters in the French
       word ALGORITHME in the order they appear in the word.  How many
       letter-vs-letter comparisons were required?

    b. Starting with the heap constructed in part (a), delete the smallest
       letter twice.  How many letter-vs-letter comparisons were required?

    c. Starting with the letters in ALGORITHME in the first ten slots of
       the sequential representation of a heap, use the linear-time heapify
       algorithm to create a heap.  How many letter-vs-letter comparisons
       were required?


P4. (6 points) Let T be a binary search tree T on N nodes.  Describe algorithms
    that

    a. check whether or not T is height-balanced (i.e., for every node in T,
       the heights of the left and right subtrees differ by at most 1).

    b. compute the number of comparisons required to search for each element in
       T exactly once.

    Each algorithm should run in O(N) time (assuming that a comparison requires
    O(1) time).  Half credit for slower algorithms.  Note: T does NOT store the
    heights in the nodes.


P5. (4 points) Consider the problem of finding the I-th smallest item in a
    binary search tree with N nodes.

    Any algorithm that runs in O(tree-height) time must use additional
    information that is stored in the nodes of the tree and updated after
    each insertion/deletion.  Moreover, these updates must be performed in
    O(tree-height) time to ensure that the algorithms for insertion/deletion
    still take O(tree-height) time.  This leads to the requirements that:
    * the extra information stored at a node can only change if that node is
	"visited" during an insertion/deletion;
    * this information can be updated in O(1) time given the corresponding
	value(s) at each node in its left and right subtrees.

    What additional information could be stored in the nodes to solve the
    problem under these constraints?  Describe an algorithm that can update the
    extra information at a node in O(1) time given the corresponding value(s)
    at each node in its left and right subtrees.  Describe an algorithm that,
    given I, uses this information to find the I-th smallest item in the tree
    in O(tree-height) time.  Explain why your algorithm works as well as how.


P6. (1 point) How much time did you spend doing the first four problems?
     
								CS-223-04/08/09