4. Use induction to prove that the number of leaves in a binary tree of
height H is at most 2^H.
Base Case: H = 0. A binary tree of height 0 is just a single node with
no children, and therefore has 1 leaf. 1 = 2^0, so the base case
satisfies the induction hypothesis (see below).
Induction Hypothesis: Spose that for some k >= 0, all binary trees of
height <= k have at most 2^k leaves.
Induction Step: Let T be a binary tree of height k+1. Then T's left and
right subtrees are each binary trees of height <= k, and thus by the I.H.
have at most 2^k leaves. The number of leaves in T is equal to the sum of
the number of leaves in T's subtrees, which must be less than or equal to
2^k + 2^k = 2^(k+1). Hence the hypothesis holds for k+1, and so the
theorem is proved.
5. Use #4 to prove that a binary tree of height H has at most 2^(H+1) - 1
nodes.
Proof by induction (although other methods were accepted for this
problem):
Base Case: H = 0. As above, a tree of height 0 has exactly one node, and
2^(0+1) - 1 = 2^1 - 1 = 2 - 1 = 1, so the base case satisfies the I.H.
Induction Hypothesis: Spose that the result holds for some k >= 0; i.e.,
a binary search tree of height k has at most 2^(k+1) - 1 nodes.
Induction Step: Let T be a binary tree of height k+1. By definition of
leaf, all the nodes at depth k+1 are leaf nodes. By problem 4, we know
there are at most 2^(k+1) leaves. If we remove all the leaves, we are
left with a tree of height k. Thus the total number of nodes in T is at
most 2^(k+1) [for the leaves] + 2^(k+1) - 1 [for the remaining tree
of height k, by the I.H.] = 2*(2^(k+1)) - 1 = 2^(k+1+1) - 1. Hence the
hypothesis holds for k+1, and so the theorem is proved.
7. For this problem, (a) and (d) were worth 6 points each, and (b) and (c)
were worth 4 points each. It was necessary to both describe an efficient
algorithm and also to give an accurate time analysis to get full credit.
I knocked off a point or two if you didn't give the most efficient
algorithm.
(a) GetCount() -- Add an extra integer variable "count" to the hash table
and initialize it to zero. Each time an item is Inserted, increment
count, and each time an item is Deleted, decrement count (both take just
constant time). GetCount() just returns the value of count, which takes
O(1) time.
(b) NOTE: for this part we shall assume that the hash table items are
comparable (otherwise there can be no maximum), and also that no
duplicates are allowed in the table.
GetMax() -- Add an extra variable "max" to the hash table and initialize
it to negative infinity (or whatever is the equivalent for the data type
we're hashing). Each time an item is Inserted, compare it to max. If the
value is greater, replace max with the new value (constant time). Each
time an item is Deleted, check to see if it is the max. If so, we must
search through the entire table to find the new maximum (this takes
O(table size) time). GetMax() just returns the value of max, which takes
O(1) time. Note that even though the bookkeeping required for this
algorithm is O(table size), the average complexity is only O(1) because
the chance of Deleting the maximum element is small.
(c) GetMin() -- same as GetMax(), but replace max with min.
(d) FindInRange(x,y) -- [also assumes that items are comparable] If y - x
< table size, perform repeated Finds on all values in the range x to y.
If an item exists in the table that is within this range, this method is
guaranteed to find it. This will take O(y-x) time. On the other hand, if
y - x >= table size, just do a linear seach through the table, checking
each item one by one to see if it is within the specified range. This
will take O(table size) time. So the total running time of this algorithm
is O(min(y-x, table size)). Note that if we always perform repeated Finds
on all values in the range x to y, this could actually take longer than
O(table size) if y - x > table size. This is because--without actually
calculating the hash function--we have no way of knowing whether Find(a)
and Find(b) will hash to the same location, and so we will end up looking
at some table entries multiple times.