Non-Programming Exercises:

1. Number of Nodes in a Minimal AVL Tree. The height of a binary tree is the maximum number of edges you must go down from the root to get to leaves. An AVL tree is a binary tree that is height balanced, that is, for each node x, the heights of the left and right subtrees of x differ by at most 1. A minimal AVL tree has as few nodes as possible. This problem asks you to prove a formula for the number of nodes in a minimal AVL tree of height h, call it H(h). Prove your formula by induction.

   H(0) = 1 because there is only one tree with height 0, namely a tree with a root node, no children, and no subtrees.

   H(1) = 2, H(2) = 4, H(3) = 7, as illustrated below. (For h > 1 there are many different minimal AVL trees.)

   
          O               O               O
         /	              /	\             /	\
        /	             /	 \           /	 \
       O               O	  O         O	  O
                        \             / \     \
                         \           /   \     \
                          O         O     O     O
                                     \
                                      \
                                       O
   

   1. Give an example of a minimal AVL tree of height 4.
   2. Prove by induction that H(n) = F(n + 3) - 1, where F(n) is the nth Fibonacci number.

2. Consider the matrix

   
          |  0   1  | 
   A =    |         |
          |  1   1  |
       

   1. By hand, calculate A².
   2. Again by hand, calculate A² * A² = A⁴.
   3. Again by hand, calculate A⁴ * A⁴ = A⁸.
   4. Again by hand, calculate A⁸ * A⁸ = A¹⁶. (The final answer should have entries in the first row equal to 610 and 987.)

3. (Note: earlier misprints has several h's below where there should have been n's.)
   Consider growth functions t(n) and g(n), along with the ratio t(n)/g(n), taken as n tends to infinity, as in the text, page 57.
   1. Let t(n) = 2^(n/2) and g(n) = p^n, where ^ means "raise to the power", and p is the golden mean, (1 + sqrt(5))/2 = 1.618 ...). Try to determine the ratio t(n)/g(n) as n tends to infinity. [Hint: take the logarithm of both functions and see what happens to the ratio of the logarithms.] This hint is wrong and taking logarithms doesn't work. These limits can be solved directly.`
   2. Do the same as the previous part with t(n) unchanged and with g(n) = (sqrt(2))^n.

4. Consider the following recurrence relation:
   T(n) = 1, if n = 2
   T(n) = 2*T(n/2) + 2, if n > 2, n = 2^k, k > 1.

   Prove by induction that T(n) = (3/2)*n - 2, for all n > 2, n = 2^k, k > 1.. [Hint: You are used to assuming a formula true for n and then proving it true for n + 1. In this case, though, you need to go from n to 2*n. Don't forget the basis.]

5. This exercise has to do with the "RightLeftBinaryExponentiation algorithm in the text (page 230).
   1. Implement this algorithm, almost exactly as it is (except translated into Java/C/C++), using the same variable names: a, B, term, product, and i. Test this program with inputs a = 2 and b[0] = 0; b[1] = 1; b[2] = 0; b[3] = 1; b[4] = 1;, giving the binary bits of b = 26 = 11010₂ in reverse order.
   2. Modify this algorithm minimally so that you can use an int parameter b instead of an array, generating the bits as you go along. Add extra print statements to print the values of i, term, and product at the end of each iteration of the loop. Use inputs a = 2 and b = 26, essentially the same as in the problem above.

6. Implement the selection sort or bubble sort from the text (pages 99-100), and count the number of times your program does a comparison. Use a random number generator to create a random array of ints or doubles for sorting. Use n, the size of the array as an input parameter, and let the number of comparisons be the output. Try this for  n = 10, 100, 1000, 10000, ... (until it takes too much time on your computer). Let c(n) be the number of comparisons. In each case, print the numbers n, c(n), c(n)/n² (as a double).