(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 4  Binary Search Tree, Etc.     Week 4: Feb 7-9  Due (on time): 2012-02-13  23:59:59  Due (late):        2012-02-17  23:59:59

Recitation 4 should be submitted following directions at: submissions with deadlines 2012-02-13  23:59:59 (that's Monday, 13 February 2012, 11:59:59 pm) for full credit. 2012-02-17  23:59:59 (that's Friday, 17 February 2012, 11:59:59 pm) for 75% credit.

1. Prove the Fibonacci matrix identity by induction:
   

   Be sure to establish the base case (n = 1), as well as proving that if the result holds for an arbitrary n, then it holds for n+1.

2. Consider two different recurrences we encountered recently:

   The Fibonacci Numbers: F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2,       n > 1

   The Leonardo Numbers: A0 = 1 A1 = 1 An = An-1 + An-2 + 1,       n > 1

   Say briefly what the Leonardo Numbers are and where we encountered them.
   Use induction to prove the following formula:

   An = 2 * Fn+1 - 1

3. Consider the following function that will calculate the product of its two input parameters. It does with this without using any "multiply", but just with addition and subtraction. The whole idea is to learn to use loop invariants on problems simple enough that you can push the proof through. What is NOT wanted here is a proof based on logic without using a loop invariant. For example, one might say:

   Note: The following kind of proof is NOT what you are to do:
   "Based on the variable y, this program will clearly iterate y times. Each time, starting with 0, we keep adding x to a running sum. In the end, we've added in x a total of y times, so x + x + ... + x (y times) is obviously x*y, which is what mult is supposed to do."

   // mult: inputs X and Y both > 0 int mult(int X, int Y) { int x = X, y = Y, p = 0; while (y > 0) { p = p + x; y = y - 1; } return p; }

   Use the "loop invariant" method to prove this program is correct by going through the following steps. (You might get help from the answers to Recitation 1, specifically Problem 4.)

   1. Figure out or guess what the loop invariant must be. (I'll give this to you on Tuesday, 14 February 2012, right after the full-credit deadline.)
   2. Carefully write out a proof following the four steps given below:
      1. Prove that loop invariant is true initially.
      2. Prove that after each execution of one iteration of the loop, the loop invariant is still true.
      3. Prove that on termination, the equation for the loop invariant shows that the correct value is being calculated.
      4. Prove that the algorithm terminates.

   3. What goes wrong in the proof if one writes p = 1; in error instead of p = 0;? (Not just "how is your answer wrong?", but in addition, how does your proof given in (ii) above fail to work?)
   4. What goes wrong in the proof if one writes y = y + 1; in error instead of y = y - 1;?

4. The worst-case time to find an element in a binary search tree depends on the maximum depth of the tree. (Your text calls this the maximum height of the tree.In either case, the word "maximum" is assumed, so I will just talk about the depth of a tree, while your text says height. See your text pp. 286-292, 1176-1179.)
   1. What is the largest that the depth of a binary search tree with n nodes can be? Give an example of such a tree. (Describe such a tree or give a specific example.)

   2. What is the smallest that the depth of a binary search tree with n nodes can be? Give an example of such a tree. (Describe such a tree or give a specific example.)

5. With this experiment we want to investigate a randomly build binary search tree with n nodes. Specifically, we want the maximum depth from the root to a leaf in such a search tree, which I'll usually just call the depth (and your book calls the height). Your text claims that the expected depth is O(log n), and in fact, they show that this expected depth is less than 3 * log₂(n). (The actual depth of a specific random tree might be greater or less than this.)

   You can use binary search tree of chars (in both Java and C) as a pattern in constructing the tree for this section, or else you can use another binary search tree program that you wrote yourself, but not one from elsewhere.

   1. Convert the tree at the above link to a binary search tree of doubles. (Alternatively, you may be working in Java with your own generic program that is already good for doubles.)

   2. Arrange to insert random doubles into a growing tree, thus creating the desired randomly built binary search tree. (Various programs in the course show random doubles being generated.)

   3. Add an extra field int depth to the struct or class representing a node in the tree.

   4. Insert an integer value into each depth field that represents the distance down from the root node to the given node. (The root node should have depth 0. One way to do this is to use an inorder traversal with an extra parameter in the function whose value is the depth of the node represented by the function call of the traversal.)

   5. Using an array of counters, tabulate (record) the number of nodes at each depth. (If int A[50] is the array of counters, and a node has depth d, then do (A[d])++.) You should also tabulate the number of leaf nodes at each depth.

   6. Below I show the results of using the given 10 "random" numbers in the array R.

      Random Nos R[0]=0.56 R[1]=0.12 R[2]=0.93 R[3]=0.53 R[4]=0.74 R[5]=0.66 R[6]=0.89 R[7]=0.05 R[8]=0.76 R[9]=0.35 Leaf Node Counts Counts L[0]=0, A[0]=1 L[1]=0, A[1]=2 L[2]=1, A[2]=3 L[3]=2, A[3]=3 L[4]=1, A[4]=1 L[5]=0, A[5]=0 L[6]=0, A[6]=0 L[7]=0, A[7]=0

      Click picture or here for full size picture.

      The depth of this tree is of course the largest index of a non-zero entry, using either the count of all nodes or of all leaf nodes. (Once an index i has A[i] = 0, we know that all entries are zero for any index j > i.) You must use this example to test your program initially, showing the results of a run. (Just patch in a curley bracket {} initialization of the array.)

   7. Carry out the experiment for as large a number of doubles as your computer can handle (within reason -- I was able to use n = 10000000.) Then compare your maximum depth with 3 * log₂(n).