The following divide-and-conquer java algorithm is proposed for finding the simu

Question

The following divide-and-conquer java algorithm is proposed for finding the simultaneous maximum and minimum: If there is one item, it is the maximum and minimum, and if there are two items, then compare them and in one comparison you can find the maximum and minimum. Otherwise, split the input into two halves, divided as evenly as possibly (if N is odd, one of the two halves will have one more element than the other). Recursively find the maximum and minimum of each half, and then in two additional comparisons produce the maximum and minimum for the entire problem.

a. Suppose N is a power of 2. What is the exact number of comparisons used by this algorithm?

b.Suppose N is of the form 3 · 2k. What is the exact number of comparisons used by this algorithm?

c. Modify the algorithm as follows: When N is even, but not divisible by four, split the input into sizes of N/2 ? 1 and N/2 + 1. What is the exact number of comparisons used by this algorithm?

Explanation / Answer

public class MaxMin {
    static MaxMin m=new MaxMin();
    static int maximum,minimum;
  
    public static void main(String ar[])
    {
        int a[]={1,22,10,9,45,31,81};
        MaxMin.maximum=MaxMin.minimum=a[0];
        int[] getMaxMin=m.MaxMin(a, 0, a.length-1, a[0], a[0]);
        System.out.println("Maximum : "+getMaxMin[0]+" Minimum : "+getMaxMin[1]);
    }
  
    public int[] MaxMin(int[] a,int i,int j,int maximum,int minimum)
    {
        int mid,maximum1,minimum1;
        int result[]=new int[2];
        //Small(P)
        if (i==j) { maximum = minimum = a[i]; }
     else if (i==j-1) // Another case of Small(P)
          {
                if (a[i] < a[j]) { this.maximum = getMax(this.maximum,a[j]); this.minimum = getMin(this.minimum,a[i]); }
                else { this.maximum = getMax(this.maximum,a[i]); this.minimum = getMin(this.minimum,a[j]); }
          }
     else
     {
           // divide into subparts
           // to find the split parts.
           mid = ( i + j )/2;
           // Solve the sub-parts
           maximum1=minimum1=a[mid+1];
           MaxMin( a, i, mid, maximum, minimum );  
           MaxMin( a, mid+1, j, maximum1, minimum1 );
           // Combine the solutions.
           if (this.maximum < maximum1) this.maximum = maximum1;
           if (this.minimum > minimum1) this.minimum = minimum1;
     }
        result[0]=this.maximum; result[1]=this.minimum;
        return result;
    }
  
    public static int getMax(int i,int j)
    {
        if(i>j) return i;
        else return j;
    }
  
    public static int getMin(int i,int j)
    {
        if(i>j) return j;
        else return i;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.