Objectives:
-know Max-Heapify algorithm, Build-Max-Heap Algorithm
-know how to prove a correctness of algorithms using loop invariants
-know how to build decision trees
Assignment Description:
- 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.
- 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.
- 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.
- 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. //findTwoSmallest finds the smallest and the second smallest
//in a given array using FIFO (first-in-first-out) queues.
void findTwoSmallest(int array1[], int length)
{
//comparedTo keeps track of numbers compared to each number
queue comparedTo[length]; //an array of FIFO queues int smallestIndex = findIndexOfSmallest(array1, 0, length-1, comparedTo); //Searching the second smallest
//It should be one of numbers that were compared to
//the smallest number before
int secondSmall = comparedTo[smallestIndex].front(); //access the head of the queue
comparedTo[smallestIndex].pop(); //remove the head of the queue
for (int i=1; i < ceil(log2 n) ; i++) //ceil is a ceiling function
{
int comp = comparedTo[smallestIndex].front();
comparedTo[smallestIndex].pop();
if (comp < secondSmall) //comparison
secondSmall = comp;
} //printing the smallest and the second smallest
cout << “The smallest is ” << array1[smallestIndex] << endl;
cout << “The second smallest is ” << secondSmall << endl;
}
//findIndexOfSmallest function finds the index of the smallest number recursively
int findIndexOfSmallest(int elements[], int from, int to, queue comparedTo[])
{
if (from == to) //base case – if there is only one number, then that is the smallest
{
return from;
}
else
{
int mid = (from+to)/2;
int one = findIndexOfSmallest(elements, from, mid, comparedTo);
int two = findIndexOfSmallest(elements, mid+1, to, comparedTo);
//the following compares two values,
//then records the number that was compared and is larger in the queue of smaller number
if (elements[one] < elements[two]) //comparison
{
comparedTo[one].push(elements[two]);
return one;
}
else
{
comparedTo[two].push(elements[one]);
return two;
}
}}
Sample Solution
