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.

2.

(6 points.) Is the following statement true or false? Explain your answer.