CS 5114 Homework 4 (Spring 2009)

Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous. Do not make any assumptions not stated in the problem. If you do make any assumptions, state them clearly, and explain why the assumption does not decrease the generality of your solution. If you use any new words or phrases, define them, especially if we have not used these words/phrases in class. Do not describe your algorithms only for a specific example you may have worked out. You must also provide a clear proof that your solution is correct (or a counter-example, where applicable). Describe an analysis of your algorithm and state its running time. You will only get partial credit if your analysis is not tight, i.e., if the bound you prove for your algorithm is not the best upper bound possible.

1. (10 points) Solve the recurrence T(n) = T(√n) + 1 . In words, the T(n) is the running time of an algorithm that creates one sub-problem of the size equal to the square root of n, solves this sub-problem recursively, and spends one more unit of time. You can assume that T(2) = 1 and that n is at least two.
2. (30 points) You are given three algorithms to solve the same problem of size n. Analyse each algorithm in big-O notation. Provide a clear proof of the analysis. Which algorithm would you choose and why? In other words, write down which algorithm is asymptotically the fastest and provide a proof why this algorithm is asymptotically the fastest of all three.
   1. Algorithm A solves the problem by dividing it into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
   2. Algorithm B solves the problem by dividing it into two subproblems of size n - 1, recursively solving each subproblem, and then combining the solutions in constant time.
   3. Algorithm C solves the problem by dividing it into three subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n²) time.
3. (25 points) Solve exercise 1 in Chapter 5 (page 246) of your textbook. Note that you cannot delete elements from the databases. The only operation you are allowed is to query the kth smallest value in one of the databases. You are likely to come up with an algorithm that somehow eliminates parts of each database and recurses on the remaining parts. Be sure to prove that whatever element you return from the recursive calls is the median element in the original set of 2n values, i.e., how can you be sure that the element returned by the recursive calls is the median of the original set of values and not some other value?
4. (35 points) Solve exercise 3 in Chapter 5 (pages 246-247) of your textbook. Let us call the equivalence class with more than n/2 cards the majority class. It is enough for your algorithm to return a card that belongs to this class, if it exists, or no card at all. Note that the problem specifies that the only operation you can perform on a pair of cards is to decide if they are equivalent. You cannot perform any other operation, e.g., compare them in order to sort them. Your proof of correctness must clearly address why your algorithm will find a set of majority class, if it exists. For instance, if you divide the cards into two sets of n/2 cards each and find the majority class in each subset, why should the majority class(es) found by the recursive calls have any relation to the majority class for all n cards?