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: at 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