(60 points)

1. (12pts) Exercise 2.a in Chapter 11.

2. (12 pts) Exercise 19.c, 19.d, and 19.f in Chapter 11.  Part f returns a reference to that specific item, and null if not found.  Your solution to each problem is a recursive definition that includes two parts: base case(s) and the recursion. You are NOT required to implement your recursive definitions.

3. (4 pts) Define the recurrence relation and initial conditions for the following questions. Give equations, not pseudocode or code.

MNBBT(h), the minimum number of nodes of a balanced binary tree of height h.  (For example, MNBBT(3) = 4 as the minimum number of nodes of a balanced binary tree of height 3 is 4.)

4. (8 pts) Exercise 6 in Chapter 11.

5. (8 pts) Exercise 7 in Chapter 11.  For 7.b, you are required to show two trees - one right after 50 is deleted and then the other after both 50 and 20 is deleted.

6. (8 pts) Exercise 15 in Chapter 10.  You only need to consider the comparisons used to compare two items. You are required to figure out the exact number of comparisons, not the Big-O notation.

7. (8 pts) We want to insert all the integers in an unsorted array of size m into a sorted array of integers of size n.  The value of m is much smaller than the value of n.  Different approaches could be taken as described as follows.

a) Insert the items in the smaller array into the right place in the larger array one by one.

b) Sort the smaller array and merge the two arrays. 

What is the time required in Big-O notation for each of the two approaches?  Which approach is more efficient? Why? (Your answer should contain both m and n initially in your analysis and later you might reduce it to the simplest Big-O notation where appropriate.)