3. Study quicksort. a. Apply quicksort to sort the list P, R, O, G, R, A, M. Show steps of each partition. b. Discuss the best case, worst case, and average case of quicksort. c. Is quicksort stable? Why? If not, give a counterexample. 4. Compute 2012 * 1203 by applying the divide-and-conquer algorithm outlined in the text. Show your steps briefly. 5. Ex 5.5 (Pages 197-198): #2. Draw a diagram to illustrate your proof. Chapter 6 - 6. Consider the problem of finding the smallest and largest elements in an array of n elements a. Design a presorting-based algorithm to solve this problem b. Design a divide-and-conquer algorithm to solve this problem c. Compare the efficiency of these three algorithms: the brute-force algorithm, a, and b as above. 7. Construct an AVL tree for the following list: 3, 2, 1,8, 4, 5, 6, 7, by inserting their elements successively, starting with the empty tree. Illustrate each step with proper rotations. 8. Study heapsort. a. Construct a heap for the list P, R, O, G, R, A, M by either the top-down or the bottom-up algorithm b. Apply heapsort to sort the above list. Show the intermediate heap of each step. c. Discuss the best case, worst case, and average case of heapsort d. Is heap sort stable? Why? If not give a counterexample. 9. a. Apply Honor's rule to evaluate the polynomial: b. Use the result of the above application of Honor's rule to find the quotient and remainder of the division of p(x) by x + 3. 10. Ex 6.6 (Page 248): #1 at Extra credit -- 11. Implement Algorithm EfficientClosePair(P.) on Page 194 using any programming language. 12. Ex 6.4 (Page 233): #11 Note: In this homework, you will need to draw diagrams to illustrate steps. You may use a tool like Word/Shapes or Paint to