Reference no: EM132139365

Questions: 1. For the set of {1, 4, 5, 16, 17, 21} of keys, draw binary search trees of heights 2, 3, 4, 5, and 6.

2. Use the Binary Search Tree class to Write the TREE-PREDECESSOR procedure.

3. Show that there are at most [n/2^h+1] nodes of height h in any n-element heap.

4. Use the Principle of Mathematical Induction to verify that, for n any positive integer, 6^n-1 is divisible by 5

5. Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

(a) f(n) + g(n) = Θ(min(f(n), g(n)).

(b) f(n) + O(f(n)) = Θ(f(n)).

6. Use the following tree to answer the questions:

(a) Write the a pseudocode to find key 36 successor.

(b) Write the pseudocode to find the minimum key in the previous tree.

Information related to above question is enclosed below:

Attachment:- DS.rar