CSE 5311 Fall 1999

**Quiz #1**

- 1.
- (14 points.)
Apply the divide-and-conquer principle discussed in class to searching.
To search for a key in a set of n keys, the algorithm divides the set into
two subsets of n/2 keys and searches each subset recursively.
- (a)
- Provide pseudocode for the algorithm and perform a line-by-line analysis of the algorithm.
- (b)
- Generate a recurrence relation for the run time and solve it using any of the methods described in class.

To search for a key

*k*in an array A of n elements, call BinarySearch(A, 1, n, key). This is one possible design of BinarySearch.BinarySearch(A, k, p, r) cost times 1 if (p = r) c1 1 2 if (A[p] = k) c2 t1 3 return TRUE c3 t1*t2 4 else return FALSE c4 t1(1-t2) 5 else q = (p + r) / 2 c5 (1-t1) 6 if (BinarySearch(A, k, p, q) = TRUE) T(n/2) (1-t1) 7 return TRUE c7 (1-t1)t3 8 else return BinarySearch(A, k, q+1, r) T(n/2) (1-t1)(1-t3) t1 = 1 if p = r, 0 otherwise t2 = 1 if A[p] = k, 0 otherwise t3 = 1 if BinarySearch(A,k,p,q) = TRUE, 0 otherwise

The recurrence is T(n) =

Master Method: This is case 1 of the Master Theorem, so T(n) = .

Iteration Method: T(n) = 2T(n/2) + O(1) = 2[2T(n/4) + O(1)] + O(1) = 4T(n/4) + O(1) + O(1)

The ith unexpanded term is ), and ith expanded term is O(1). The recursion ends when , or . Thus = O(n). - 2.
- (6 points.) Is the following statement true or false?
Explain your answer.
False. Choose f(n) = n and g(n) =

*n*^{2}. Then f(n) + g(n) = n +*n*^{2}= , and min(f(n), g(n)) = n.