Homework 2
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.
