CSSE 230
Data Structures and Algorithm Analysis
Written Assignment 8 - 72 points
To Be Turned In
Submit to the drop box.
-
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.
-
(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 =.
-
(15 points). Weiss Exercise 19.7. Prove it by
strong induction on the size of the tree. 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](Images/img4.gif)
-
(15 points) Problem 7.12[7.12]. This refers to
the
fib
method defined in Figure 7.6. C(N) represents the number of
calls to fib
during the calculation of FN. A recurrence relation
for C(N) is given in lines 2-4 of paragraph 3 on Page 305[263].
Using this recurrence relation, you must show by
(strong) induction that C(N) = FN+2 +
FN-1 - 1 for all N ≥ 3. As stated in the text, this is fairly easy to do.
-
(12 points) Solve the recurrence relations below. Indicate which strategy you are using and show your work.
-
T(1) = 1, T(N) = 2 T(N/4) +
N0.5
-
T(1) = 1, T(N) = T(N
- 2) + 2, assuming
N
is odd.
-
T(1) = 1, T(N) = 3 T(N/2) + 2N
-
(10 points) Use a recurrence relation to show that the running time of the
printPreorder
method in Figure 18.22 is O(N). You may assume that the tree is perfect (i.e., full, balanced, and size 2k
- 1 for some integer
k).