Qualifer Practice Exam: Foundations

Question 5 (9 Points): Below are three recursive java methods. In each case, the

“problem size” n is given by r − l + 1 – the number of elements in the subarray being

processed. For each method do the following:

(1) Derive and explain a recurrence relation for the runtime T(n) of the recursive method.

(2) Give and explain a tight Big- bound on the T(N).

Ugh. Coming back to this problem some other time. (Ugly code.)

Question 6 (5 Points): Suppose the following values are inserted into a “generic” (i.e.,

not self-balancing) binary search tree:

10, 2, 8, 11, 14, 3, 42

(They will not necessarily be inserted in the given order).

Devise an insertion order which will result in the tree having minimum height.

10, 3, 14, 2, 8, 11, 42 (Creates a balanced tree, w/ h=2)

Question 7 (6 Points): Draw a minimum sized AVL tree of height 4 (an AVL tree

with 1 node has height 0). (In other words, among all AVL trees of height 4, draw one with

a minimum number of nodes). How many nodes does your tree have?

Recall that a Binary Search Tree T is an AVL tree if and only if the following holds: for

all nodes v in T, the height of v’s subtrees differ by at most 1. Sometimes this is called

“height-balanced-1”.

x

/ \

x x

/ \ / \

x x x x

/ \ / \ / \ / \

x x x x x x x x

/

x

It has 16 nodes. (Not sure if this needed to have values, but it would not be difficult to come up with values.

Question 8 (7 Points): Below is (part of) a simple java class for a Binary Tree node.

The method isBST is supposed to determine if the given tree is a valid Binary Search Tree.

(E.g., the developer might use it as a sanity checker).

Is the algorithm correct?

If your answer is YES give a concise argument of correctness.

If your answer is NO give and explain a counterexample.

public class BTNode {

private int key;

private BTNode left;

private BTNode right;

// Returns true iff binary tree rooted at

// t is a valid Binary Search Tree with

// respect to the stored keys.

public static boolean isBST(BTNode t) {

if(t == null) return true;

if(t.left != null && t.key <>

else if(t.right != null && t.key > t.right.key) return false;

else return isBST(t.left) && isBST(t.right);

}

}

This is a correct method for determining if a BST is correct. If each sub-tree is correct, than the entire BST is correct. This could be proven via induction. It may not be as pretty as an AVL tree, but it will be correct.