Answer the following questions about the unusual algorithm below for com- puting
ID: 3781720 • Letter: A
Question
Answer the following questions about the unusual algorithm below for com-
puting the maximum value of an array. Note that the input array must have
a size that is a power of 2. (The algorithm can be modi ed to accommodate
non-powers-of-two, but this complicates the proofs somewhat.)
Explanation / Answer
This algorithm uses recursion to find the largest element in an array . It at each step finds the max value of a pair of consecutive numbers in the array , thus reducing the total number of values by half in each iteration and when the size is reduced to one , it returns that value and it is the maximum value .
1. As the size of the array reduces by half at each step . Lets take the value n= 8 or 23
In iteration 1 : The number of times the loop runs is n/2 = 4 or 22 .
winnow[i] = max{data [2*i-1],data[2*i]}
As n =8 , i = 1 to 4
winnow[1] = max{data [2*1-1],data[2*1]} = max{data [1],data[2]}
winnow[2] = max{data [2*2-1],data[2*2]} = max{data [3],data[4]}
winnow[3] = max{data [2*3-1],data[2*3]} = max{data [5],data[6]}
winnow[4] = max{data [2*4-1],data[2*4]} = max{data [7],data[8]}
For next iteration winnow[1..4] becomes data[1..4]
In iteration 2 : The number of times the loop runs is 4/2 = 2 or 21
As n =4 , i = 1 to 2
winnow[1] = max{data [2*1-1],data[2*1]} = max{data [1],data[2]}
winnow[2] = max{data [2*2-1],data[2*2]} = max{data [3],data[4]}
For next iteration winnow[1..2] becomes data[1..2]
In iteration 3 : The number of times the loop runs is 2/2 = 1 or 20
As n =2 , i = 1
winnow[1] = max{data [2*1-1],data[2*1]} = max{data [1],data[2]}
winnow[1] is the single element left with the highest value .
After this the result is returned .
2. Using the method of induction
As seen above the algorithm holds true for size n=2 or 21
Assuming the algorithm holds true for n = 2(K) elements for all values of K from 1 to K viz.. 2(K-1),2(K-2),.....,2(3-1),2(2-1)
We need to prove it is true for n = 2(K+1)
So , 2(K+1) = 2 * 2(K) = 2(K) + 2(K)
As the algorithm holds true for 2k from the assumption above , it holds true for the two subsets of 2k size after the first iteration as the swap operations on each subset is not overlapping .
This produces a data array with the size 2k for the next iteration .Which is true as per the assumption .
Hence WinnowMax is true for every array of size, power of two .