CSSE 230
Data Structures and Algorithm Analysis

Homework 5 - 52 points

To Be Turned In

Submit to the dropbox, except the last problem. You may earn or use a late day for this assignment. Like all written assignments, this is an individual assignment. You may discuss it with others, but you should write (and code) your answers yourself.

  1. (10 points) Recall that S(H) is the minimum number of nodes in a height-balanced tree of height H. Prove that S(H) = Fib(H+3) - 1 by induction. Hint: We observed in class that S(H) = S(H-1) + S(H-2) + 1. Use this observation in your proof. (If you missed this observation, you should review it, asking for help if needed, until you convince yourself this is true.) Here are a couple of supplementary online resources on induction that I like: (1) Video demo and web page (this page does a few examples, and explains more about why is works with a couple of cool examples showing what happens if you use math induction incorrectly!)
  2. (10 points) Weiss Exercise 19.2[19.2]. 5 points for drawing the trees, and 5 for the probabilities.
    Assume in each case that you are inserting the items into a Binary Search tree that is initially empty.  There are of course 4! permutations, but in many cases multiple permutations lead to the same tree.  For example, 2134 and 2314 lead to the same tree (2 is the root, 1 is 2’s left child, 3 is 2’s right child, 4 is 3’s right child. That's why different trees have different probabilities (each permutation has probability 1/24, but some trees come form multiple permutations; the total of all of the probabilities should be 1). As another example, the permutation 2413 leads to the tree (expressed in "displayable" notation) chars="2143", children="20L0". 

  3. (12 points) Fill in the following table. Be very careful to get the exact values. Most of the credit will be for the last column. Don't use the AVL approximation formula (H < 1.44log(...)). Instead, draw trees and look for the patterns, like we did on day 13 in class.

    Feel free to include explanations of your answers. correct_answer → full_credit.  wrong_answer + no_explanation → no_credit.

    1/2 point for each entry in the first two columns, and 2 points each for each entry in the last column.

    n Height of shortest binary tree with n nodes Height of tallest binary tree with n nodes Height of tallest AVL tree with n nodes
    7 2 6 3
    8      
    370      
    17000      
    50000      
  4. (20 points) More tree practice! You will write two methods for Binary Trees. Like the last homework, the trick to these is to add parameters or multiple return values (through your own custom class) to your recursive helper method. 
    1. Full tree constructor. Create a full tree of Integers whose leaves have the given depth, and where every node is labeled with its own depth. It is good experience to know how to build a whole tree by calling a single method. 
    2. getSumOfHeights. Find the sum of the heights of every node in the tree. This is an interesting problem if you want to do it efficiently, meaning in O(n) time. Just calling height() on each node will give the correct answer, but it duplicates a lot of work and leads to an O(n log n) algorithm. Could you somehow combine finding the height with finding the sum of the heights in your method? Hint: don't use a field - that has a side effect of modifying each node. Instead, use either multiple return values (which I think is clean) or mutable parameters to do the trick.     
            Commit your work to SVN as you make progress and when you finish.

Other problems for your consideration