No Title

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) = $\left\{ \begin{array}{ll} 1 & {\rm if} \; i = 1 \\ 2T(n/2) \;+\; O(1) & {\rm otherwise} \end{array} \right.$

Master Method: This is case 1 of the Master Theorem, so T(n) = $\Theta(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 $2^iT(\frac{n}{2^i}$ ), and ith expanded term is O(1). The recursion ends when $\frac{n}{2^i} \;=\; 1$ , or $i \;=\; lg n$ . Thus $T(n) \;=\; (\Sigma{i=0}^{lgn - 1} O(1)) \;+\; 2^{lg n} T(1)$ = O(n).

2.

(6 points.) Is the following statement true or false? $f(n) \;+\; g(n) \;=\; \Theta(min(f(n), g(n))).$ Explain your answer.

False. Choose f(n) = n and g(n) = n². Then f(n) + g(n) = n + n²= $\Theta(n^2)$ , and min(f(n), g(n)) = n.