Question

1.we need n-1 comparisons at most 3*n/2comparisons suffice to find both the min and max Basic Strategy: Maintain the minimum and maximum of elements seen so far. Don't compare each element to the minimum and maximum separately. Process elements in pairs. Compare the elements of a pair to each other. Then compare the larger element to the maximum so far, and compare the smaller element to the minimum so far. This leads to only 3 comparisons for every 2 elements Setting up the initial values for the min and max depends on whether n is odd or even. If n is even, compare the first two elements and assign the larger to max and the smaller to min. Then process the rest of the elements in pairs. If n is odd, set both min and max to the first element. Then process the rest of the elements in pairs. MINIMUM (A) a) Write the above description in algorithmic form A[1] for = 2 to A.length if min> min | b) Show that your algorithm need at most 3*n/2 2 A[i] A[i] 3 4 min 5 return min

Answer 1

a)

Elements(A[]) //The function Element accepts an array A[]

{

if(A.length%2==0) // if the length of Array is even

if(A[0]<A[i]) // if element in the 0th pos < element in 1st pos then,

min=A[0]  //initialize min as element in the 0th pos

max=A[1] //initialize max as element in the 1st pos

else

min= A[1] //initialize min as element in the 1st pos

max=A[0] //initialize max as element in the 0th pos

else // else if the length of Array is odd

min=A[0]  //initialize min as element in the 0th pos

max=A[0] //initialize max as element in the 0th pos

for i = 2 to A.length-1  // from i = 2 till ((Length of Array A) - 1) (because null element in pos length of array)

{

//Compare current pair to find the who is maximum and who is minimum.

if A[i]>A[i+1]   //if element at i > element at i+1

maxTemp= A[i] //maxTemp is a temporary value to store max from the current pair

minTemp= A[i+1] //minTemp is a temporary value to store min from the current pair

else    //if element at i < element at i+1

maxTemp = A[i+1]

   minTemp = A[i]

//compare the maxTemp with original max and minTemp with original min

if maxA > max //if maxTemp > original max

max = maxA //original max = maxTemp

if minA < min    //if minTemp < original min

min = minA  //original min = minTemp

i+=2   //get the next pair by incrementing the value of i 2 times

}

//now we have the maximum and minimum value in max and min variables

}

b)

Elements(A[]) //The function Element accepts an array A[]

{

if(A.length%2==0)

if(A[0]<A[i])  

min=A[0]  

max=A[1]

else

min= A[1]

max=A[0]

else   

min=A[0]

max=A[0]

//Time taken by the above if and else is constant since it is executed only once hence we ignore the time

for i = 2 to A.length-1   //The value of i increments 2 times on each loop hence the executed n/2 times

{

    // either if or else is executed on 1 comparison hence 1 execution

if A[i]>A[i+1]

maxA= A[i]

minA= A[i+1]

else

maxA= A[i+1]

   minA= A[i]

    // if is executed once hence 1 execution

if maxA > max

max = maxA

// if is executed once hence 1 execution

if minA < min

min = minA

i+=2

//adding the executions within the forloop for each if we get 1+1+1 =3

}

// 3 executions per loop and loop executes n/2 times

// Hence total execution is 3*n/2

}