Design an algorithm for the following problem using the divi

Design an algorithm for the following problem using the divide and conquer paradigm: Suppose you want to fly from Des Moines to San Diego. You would like to find a less expensive flight with a short travel time. When you search 011 a travel web site, you will be given a lot of itineraries. We will view each itinerary as a tuple . Suppose A_1 = and A_2 = are two itineraries. We say that A_1 dominates A_2, if c_1

Solution

Lets, make the algorithm. for this we will use a simple 1d array, but for the above problem we will require a data structure such as arraylist.For now lets consider a 1d array. Here we find out the min value or say lets expensive one from the given array using the divide and conquer algorithm.

Here is the funtion which returns array with single value or we can just return an int value.But understand the working of the algorithm first over here.

Working:

arr=[8,4,5,1] here i=0 and j=3, if i=j then there is only one element in the array which is desirable

else lets split the array,

find mid,which will be mid=(0+3)/2=1 so mid=1 and i=0;
Using recurssion,lets decompose them further, now mid=(1+0)/2 so mid=0 i=0, next we have i=j so arr[0]=8 ,so now result1[0]=8 and next we result into result2=4
Solving next part,(arr,middle+1,j) here values will be, arr,mid=2,j=3,next mid=(2+3)/2=2 i=2, so result1=6 and result2=7
Combine all this we will find the answer as 1.

Here is the code for the same.

public int[] divideConqur(int arr[],int i,int j) {
int desirable;
int middle,min1,min2;
  
int[] final = new int[1];

//If there us only one element then it is desirable
if (i==j) {
desirable = arr[i];
}
else {
  
//This is the Divide and conqur algorithm
// Step 1
//if it is not small enought,lets divide Problem into sub-problems using recurssion
// lets take the middle position to splitb the array.
middle = (i + j) / 2;
  
//Step2
// Solve the sub-problems.
int[] result1 = maxMin( arr, i, middle);
int[] result2 = maxMin( arr, middle+1, j);
min1 = result1[0];
min2=result2[0];
  
//Step 3
// Combine the solutions.
  
if (min1 < min2)
desirable = min1;
else
desirable = min2;
}

  
final[0] = desirable;
return final;
}

Now lets try to do the same with the arraylist.Declare Arraylist<Integer,Integer>. This code not final,since i have time constraint, i have made some changes to above block.I have to tweak it to make it work.

int i=0;
int j=arr.size();

public ArrayList<Integer,Integer> divideConqur(ArrayList<Integer,Integer> arr,int i,int j) {
int desirable;
int middle,min1,min2;
  
ArrayList<Integer,Integer> arrlist = new ArrayList<Integer,Integer>();

//If there us only one element then it is desirable
if (i==j) {
arrlist = arrlist.get(i);
}
else {
  
//This is the Divide and conqur algorithm
// Step 1
//if it is not small enought,lets divide Problem into sub-problems using recurssion
// lets take the middle position to splitb the array.
middle = (i + j) / 2;
  
//Step2
// Solve the sub-problems.
ArrayList<Integer,Integer> result1 = maxMin( arr, i, middle);
ArrayList<Integer,Integer> result2 = maxMin( arr, middle+1, j);
min1 = result1.get(0);
min2=result2.get(0);
  
//Step 3
// Combine the solutions.
  
if (min1 < min2)
arrlist = min1;
else
arrlist = min2;
}

  
return arrlist;
}

Hope you the understanding of the algorithm.