CSSE 230
Data Structures and Algorithm Analysis
Homework 5 - 40 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.
- (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!)
- (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".
- (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.
- 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.
- 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?
Commit
your work to SVN as you make progress and when you finish.
Other problems for your consideration