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.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.
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.