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) = n2. Then f(n) + g(n) = n + n2= , and min(f(n), g(n)) = n.