1. (20 points) Using Figure 6.4 (Textbook, Exercise 6.4-1) as a model, illustrate the operation of HEAPSORT on the array A={5, 12, 2, 25, 7, 17, 20, 8, 14} and output the numbers in a non-decreasing order. (Write your result of each step.)
2. Max-Min Problem: find the maximum and the minimum numbers of a sequence number in a divide-and-conquer manner. (Let 𝑛 be the size of the sequence. For simplicity, assume that 𝑛 = 2!.)
(1) (40 points) How to do it? Please write the pseudo-code of your algorithm.
(2) (20 points) What is time complexity of your algorithm? Please present analysis process.
3. (20 points) Give asymptotic upper bound (represented by O( )) of the recursive function T(n) = T(n-2) + n. Assume that T(n) is constant for n£2.
1
