Suppose that P[1···n] records the daily net prot GreatStore earns from days 1 to

Question

Suppose that P[1···n] records the daily net prot GreatStore earns from days 1 to n. As with most stores, sometimes a P[i] is negative (i.e., when the store lost money that day) and sometimes it is positive (i.e., when the store made money that day). Alice, the owner of the store wants to use the information in P[1···n] to plan for her vacation next year. Since she always has to worry about the store’s earnings, Alice wants to choose an interval [i,j] so that the sum of the daily net prots during this interval is the least among all such intervals. For example, suppose

P[1,2,3,4,5] = [1000,250,100,300,500].

Then Alice will choose the interval [2,4] because the total net prot for this interval is 250+100300 = 450, which is the least among all intervals. On the other hand, if

P[1,2,3,4,5] = [35,200,50,85,600]

then Alice should choose the interval [1,1]. Given P[1···n], your job is to help Alice gure out the right interval by designing a divide-and-conquer algorithm for the problem.

a. Before you do so, suppose you apply brute force – you consider all possible intervals (including those that span only one day) and compute each one’s total net prot. You then utput the interval with the least net prot. How much time will this algorithm take?

b. Let’s also briey consider two simpler problems.

b1: Suppose Alice has decided that no matter what she wants to start her vacation on day i. She just needs to choose the day j to end her vacation so that among all possible choices for j, [i,j] has the least net prot. Describe an O(n)-time algorithm that solves this problem.

b2. Let’s ip the problem. Suppose Alice has decided that she wants to end her vacation on day j. Describe an O(n)-time algorithm that nds a day i so that among all possible choices for i, [i,j] has the least net prot.

c. Now design a divide-and-conquer algorithm that solves the original problem. What is the running time of your algorithm? (Note: I made you go through problems b1 and b2 because they should be useful in the merge part of your algorithm.)

Explanation / Answer

Solution :

a)

here is the brute force algorithm for the problem :

algorithm(A[1...n]):

min_sum = -
sum = 0;
min_start = -1
min_end = -1

for i = 1 to n :
   sum = 0;
   for j = i to n :
       sum = sum + A[j]
       if(min_sum >= sum)
           min_sum = sum
           min_start = i
           min_end = j
       if ends
   for ends
for ends
return [min_start, min_end]
------------------------------------------------------

b)

b1 :
algorithm (A[1...n], i):

min_sum = -
sum =0
min_start = i
min_end = -1;
for j = 1 to n :
   sum = sum + A[j]
   if(min_sum >= sum)
       min_sum = sum
       min_end = j
   if ends
for ends

here start index is fix, we need to find end index only using for loop.

b2:
algorithm(A[1...n], j):

min_sum = -
sum = 0
min_start = -1
min_end = j
for i = j to 1
   sum = sum + A[i]
   if(min_sum >= sum)
       min_sum = sum
       min_start = i
   if ends
for ends

here both algorithm has only one for loop and time complexity is O(n) for both solutions.
-----------------------------------------------------------------

c) Divide and conquer solution :

approach used in algorithm :

--> Divide array in two parts
--> return minimum of following three :
   1) minimum sum range of left part (using recursive call)
   2) minimum sum range of right part (using recursive call)
   3) minimum sum range that crosses the middle element

Algorithm :

- define two global variables global_start and global_end.
- call Min_range(1, n)

Min_range( start, end )
   if(start> end)
       return 0
   if(start == end)
       global_start = global_end = start
       return A[start]
   middle = (start+end)/2
  
   // find min sum and range crossing the left using b1 as end is fixed.
  
   mid_left_sum = -
   sum = 0
   for i = middle to start
       sum = sum + A[i]
       if(mid_left_sum >= sum)
           mid_left_sum = sum
           global_start = i
       if ends
   for ends

  
   // find min sum and range crossing the right using b2 as start is fixed

   mid_right_sum = -
   sum =0
   for i = middle+1 to end
       sum = sum + A[i]
       if (mid_right_sum >= sum)
           mid_right_sum = sum
           global_end = i
       if ends
   for ends

   return min(min(Min_range(start, middle) , Min_range(middle+1, end)), mid_left_sum+ mid_right_sum)

here at each step, minimum is found out by dividing in 2 parts.

here complexity of given algorithm is O(n log n).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects