FUNDAMENTAL ALGORITHMS
HOMEWORK 6

DUE March 22

  1. 1.a Consider the following 2-players game. One player thinks of a number in the range [1..n]. The other attempts to find the number by asking questions of the form: Is the number bigger equal or smaller than x?" Assume no cheating. We want to minimize the no. of questions required for finding the number (worst case). Design a good strategy for achieving this goal (for the second player).

    1.b Same as 1.a but the first player can choose any positive number (i.e the range is not preset)

    1.c What is the no. of questions required in both 1.a and 1.b (worst case) as a function of n in the first case and as a function of the magnitude of the choosen number in the second case?

  2. You are given a set S cotaining n numbers and a real number x

    2.a Design an algorithm that determines whether there are 2 elements in S whose sum equals x. The complexity should be O(n*logn).

    2.b Suppose now that S is ordered. Solve the same problem as in 2.a in O(n) time.

    Hint: Find a way to eliminate one element from S in constant time and then use induction.

  3. L is a list of unordered keys. Construct a tree T as follows: R is the root of T and T1, T2 are the left and right subtrees hanging from R; Using the first round of Quicksort, split L into L1,P,L2 where P is the Pivot and L1,L2 are the sublists of the numbers smaller and bigger than P respectively; Now insert P into R and, recursively, construct T1 and T2 in the same way from L1 and L2 correspondingly. List all the properties of the resulting tree you can observe. What is the complexity of building T?

  4. Assume the Quicksort procedure applied on a list L[i], i in [1..n] , that chooses the first element of the list as Pivot.

    4.a What is the complexity of the procedure if L is already ordered?

    4.b Same question but L is ordered in reverse order?

    4.c What is the number of "swaps" in both the above cases?

    4.d How would you find the median of L by using a reduced form of Quicksort?

    4.e Find the median of the list below using (d) above. Count the no. of comparisons used.

    5,100,22,35,47,13,15,90,40,7,10