1. Consider a comparison based sorting algorithm for sorting an input of n numbers x1x2 : : : xn where n is even. Suppose that the sorting algorithm is also given the following additional information: x1; x3; : : : ; xn−1 will be in the first half of the sorted order and x2; x4; : : : ; xn will be in the second half of the sorted order. Show that any comparison based sorting algorithm still requires Ω(n log n) time ot sort x1x2 : : : xn even if it is given this additional information. 2. Recall the LinearSelect algorithm we learnt in the class. Suppose that we modify the algorithm to use groups of size 3 instead of 7. Show that the modified algorithm does not run in O(n) time. 3. Starting with an empty tree, construct an AVL tree by inserting the following keys in the order given: 2; 3; 5; 6; 9; 8; 7; 4; 1. If an insertion causes the tree to become unbalanced, then perform the necessary rotations to maintain the balance. State where the rotations were done. 4. Consider an AVL tree T on n nodes. Consider a leaf that is closest to the root of T . Suppose that this leaf is at level k. Then show that the height of the tree T is at most 2k − 1.
