1. Draw the decision tree for Merge sort operating on three element; so Merge sort (A, 1, 3) where the input is A[1...3] = (a1, a2, a3). 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]. What is a stable sort? 2. 3. 4. 5. 6. 7. 8. 9. Using Figure 8.4 as a model, illustrate the operation of Bucket-Sort on the array A = (.79, .13, .16, .64, .39, .20, .89., 53., .71, .42). 10. Explain why the decision tree for any comparison based sorting algorithm must have at least n! leaves. Show log n! = (n logn). Illustrate the operation of Counting-Sort on A = (6,0,2,0, 1, 3, 4, 6, 1, 3, 2). 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 [a...b] in O(1) time. Your algorithm should use O(n + k) preprocessing time. Show how to sort n integers in the range 0 to n-1 in O(n) time. Which of the following sorting algorithms are stable: insertion sort, merge sort, and quicksort (according to their implementations in the textbook)? 11. Explain why the worst-case running time for bucket sort is (n)? What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O(n log n)? Describe a worst-case linear time algorithm that decides if a given sequence of integers (a1, a2, ..., an) is a permutation of (1, 2, 3,..., n). Your algorithm only needs to say Yes or No. (Hint: counting sort.)