CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 8  - 51 points

To Be Turned In

Submit to the ANGEL drop box.

  1. Don’t forget: You should be keeping an individual log about your team project work so that you can write a performance evaluation for each of your teammates. You do not need to turn in this log, but I wanted to remind you while I had your attention.
  2. ( 6 points) Weiss Exercise 8.10 [8.10].
  3. (10 points) Weiss Exercise 21.8[21.8]. You should provide explanations for your formulas.
    Notes:  Suppose we decide to use the same "pointerless" representation that we used for complete trees to represent ANY tree by an array (for example, to find the parent of a node in a[i], we look in a[i/2]). If the tree is not complete, there will be some "gaps" in the array, so extra space must be used.  If the n-element tree is complete, the size of the array is n+1.  The question is asking how large the array must be if the n elements are arranged into various trees of different shapes. For each part, you should give the answer for the worst case, i.e. when the nodes at the extra levels are as far right in the tree as they can be. Answers to the questions should be formulas (functions of n).
  4. (20 points) Do Weiss problem 18.8. (15 points for the induction proof, and 5 for the second part).   In your proof by strong induction, use our standard recursive definition of a binary tree (either empty or a root and two subtrees) as the basis for your induction.   Notice that the formula involves the depths of the nodes, not their heights. For example, in the tree ion Figure 18.33, the depth of node J is 3, while the depth of C is 1.As always, be sure to clearly state the induction hypothesis and indicate which step(s) use that hypothesis.
    For the second part of the problem, I am looking for a (brief) general description of the set of binary trees for which we can replace the ≤ in the given formula by=.
  5. (15 points).  Weiss Exercise 19.7.  Prove it by induction on the size of the tree.  Preferred method (for this problem and the previous problem):  Use strong induction.  The induction assumption applies to the left and right subtrees.
    This exercise is based on the discussion from pages 644-647 (beginning of section 19.3) and Exercise 19. I restate it in terms of Extended Binary Trees (EBTs), because the definition is a bit more precise than the one in the middle of page 647. An EBT T either consists of one external node, or it consists of an internal node (the root) and two subtrees, TL and T, each of which is an EBT. See the in-class PowerPoint slides from day 13 for more details. If T is an EBT, then its internal path length, IPL(T) is the sum of the depths of all of the internal nodes of T. Similarly, its external path length, EPL(T) is the sum of the depths of all of the external nodes of T.

    For example, if T is the EBT shown below, then IPL(T) = 0+1+1+2+3 = 7, EPL(T) = 2+2+2+3+4+4 = 17. Note that, since N=5 in this example, the formula is indeed true. Your job is to show that it is true for all extended binary trees.
    Based on this definition of EBTs, use strong induction to show that for any non-negative integer N and any EBT T that contains N internal nodes, EPL(T) = IPL( T) + 2*N. Be sure that you explain what you are doing. You may introduce any new notation that may be helpful.

    EBT picture