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.