1. (Intermediate) Draw the decision tree for Merge sort operating on three element; so Merge- sort(A, 1, 3) where the input is Al 3-(ai, a2, as). Use the decision tree for Insertion sort in Fig. 8.1 as a model. Note that each internal node must correspond to a comparison of two given elements from A[1...3 2. (Basic) What is a stable sort? 3. (Basic) Explain why the decision tree for any comparison based sorting algorithm must have at least n! leaves 4. (Basic) Show log2 n! (n log n) 5. (Basic) Illustrate the operation of Counting-Sort on A - (6, 0, 2,0,1,3, 4,6,1,3, 2) 6. (Advanced) Describe an algorithm that, given n integers in the range from 0 to k, prepro- cesses the input and then answers any query on how many of the n integers fall into range la in 0(1) time. Your algorithm should use O(n + k) preprocessing time 7. (Intermediate) Show how to sort n integers in the range 0 to n3- 1 in O(n) time. 8. (Intermediate) Which of the following sorting algorithms are stable: insertion sort, merge 9. (basic) Using Figure 8.4 as a model, illustrate the operation of Bucket-Sort on the array 10. (intermediate) Explain why the worst-case running time for bucket sort is (n2)? What sort, and quicksort (according to their implementations in the textbook)? A .79,.13,.16,.64,.39,.20,.89., 53.,.71,.42) simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O(n logn)? 11. (advanced) Describe a worst-case linear time algorithm that decides if a given sequence of , n). Your algorithm only needs to say integers (a, a2, , an) is a permutation of 1, 2, 3, Yes or No. (Hint: counting sort.)