1. Illustrate the operation of MAX-HEAPIFY(A, 2) on the array A = { 25,17,19,37,26,54,38,68,35,24,56,31 } by re-drawing the tree for every swap.

2. Illustrate the operation of BUILD-MAX-HEAP on the array A = { 19,32,18,52,43,37,29,71,63 } by re-drawing the tree for every swap.

3. In class, we showed the correctness of the insertion sort algorithm using a loop invariant, i.e., we showed that the three properties of initialization, maintenance, and termination held, and were then able to conclude that the entire array was sorted. 
Consider the following algorithm given by pseudo code. You can assume that the input array A has at least one element.

FUNCTION1 (A) //A is an array of length n

n = length[A]

c = 1

for (i=2; i<=n; i++)

    if  (A[i] >= A[1] )

         c = c + 1

return c

Using a loop invariant, prove that the algorithm is correct, i.e., it always counts and returns the number of elements that are greater than or equals to the first element in a given input array A. State your loop invariant first, and follow three steps explained in class. Make sure that your loop invariant fulfills the three necessary properties.

4.  The following algorithm finds the smallest and the second smallest elements of a given array, by performing comparisons. Build a decision tree for the algorithm, operating on four elements a1, a2, a3, and a4 (A = { a1, a2, a3, a4 }), having the top node showing the first comparison of two elements. The leaves of your decision tree should contain the smallest and the second smallest for each path. For instance, { a3, a2 } indicates that a3 was determined to be the smallest and a2 is the second smallest element. Note: please pay attention to two lines that are performing a comparison. They will determine the decision tree.

This assignment has been answered 6 times in private sessions.