Question

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

Answer 1

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