Design And analysis algorithm course Remarks In all the algo

Design And analysis algorithm course

Remarks: In all the algorithms, always explain their correctness and analyze their com- plexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit

Question 3: Given a gas station with two pumps, and a collection of cars 1, 2, n with filling time si for item i (on both pumps). Find a schedule that assigns cars to the two pumps, so that if the first pump is a ssigned a sum of ti and the second a sum of t2, max ti,t2 is minimum. Note that you only have to decide which car is assigned to pump 1 and which to pump 2, because the order will not change the sum. Remark: This will minimize the maximum time that any of the two pumps are \"busy\", hence it is of benefit for the gas station

Solution

Here, we will first sort the the cars in increasing order of their filling time.

After that, we will assign cars alternately to each pump.

//sorting

bubble_sort(s[],n)
{
   for all elements of the s
       if s[i]>s[i+1]
           swap(s[i],s[i+1])
   return
}

//now that we have sorted the cars in increasing order of their filling time, we can assign them alternatively to each pump

assign(s[],n)
{
   for all element in s
       if(i%2==0)
           assign this car pump 1
       else
           assign this car pump 2
}

Sorting will take worst case time of O(n^2)

Assigning will take O(n) time