Suppose that P[1 · · · n] records the daily net profit 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 profits 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 profit for this interval is −250 + 100 − 300 = −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 figure 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 profit. You then output the interval with the least net profit. How much time will this algorithm take? Let’s also briefly 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 profit. Describe an O(n)-time algorithm that solves this problem.
b2. Let’s flip the problem. Suppose Alice has decided that she wants to end her vacation on day j*. Describe an O(n)-time algorithm that finds a day iso that among all possible choices for i, [i, j*] has the least net profit.
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.)
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).
Suppose that P[1 · · · n] records the daily net profit GreatStore earns from days...
Suppose we are given two sorted arrays (nondecreasing from index 1 to index n) X[1] · · · X[n] and Y [1] · · · Y [n] of integers. For simplicity, assume that n is a power of 2. Problem is to design an algorithm that determines if there is a number p in X and a number q in Y such that p + q is zero. If such numbers exist, the algorithm returns true; otherwise, it returns false....
Suppose you have an array S indexed from 1 to n which contains n numbers, not in any particular order, and you wish to count how many times a given number x occurs in S. Consider the recursive algorithm below for this which finds the number of occurrences of x in the index range i...j in S. Of course, solving the problem would involve an initial call to the algorithm for the range 1.n: int CountOccur (int i,j) { int...
32. (6 points) Trace the Text Search Algorithm for the input t"0101001' and p "001 Input: p( indexed from 1 to m),m, t (indexed from 1 to n),n Output: i text search(p,m,t,n) f For i= 1 to n-m+1( while (ti+/-1-= pj){ jj+1 If (j> m) Return i return 0 32. (6 points) Trace the Text Search Algorithm for the input t"0101001' and p "001 Input: p( indexed from 1 to m),m, t (indexed from 1 to n),n Output: i text...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1], A[2], , Aln]. You'd like to output a two-dimensional n-by-n array B in which B[i, j] (for i <j) contains the sum of array entries Ali] through Aj]-that is, the sum A[i] Ai 1]+ .. +Alj]. (The value of array entry B[i. Λ is left unspecified whenever i >j, so it doesn't matter what is output for these values.) Here's a simple algorithm to...
Suppose there are n type of coupons. Each new coupon collected is of type i with probability Pi, independently of any other collected coupon. Here, D=1 Pi = 1. Suppose k coupons are collected. Let A be the event that there is at least one coupon of type i among the k collected. For i #j, (1) Compute P(A|AU A;) (2) Compute P(A|Aj)
Suppose n activities apply for using a common resource. Activity ai (1 ≤ i ≤ n) has a starting time S[i] and a finish time F[i] such that 0 < S[i] < F[i]. Two activities ai and aj (1 ≤ i, j ≤ n) are compatible if intervals [S[i], F[i]) and [S[j], F[j]) do not overlap. We assume the activities have been sorted such that S [1] ≤ S [2] ≤ …≤ S[n]. (a) Design an O(n2) dynamic programming algorithm...
QUESTION 3 (10 Marks) Suppose you are given an array A[0..n 1 of integers, each of which may be positive, negative, or zero. A contiguous subarray A|i..j] which includes all the items starting at array index i and ending at array index j is called a positive interval if the sum of its entries is at least zero. For example let A-{-1, 3,-5, 2, 0,-4, 3,-6,-2). Ten A[3, 6) is a positive interval since its sum is 2+0+(-4)+3-1, but Al4,7isnot...
Problem 1 (5+15 points) Consider the set P of n points and suppose we are given the points of P one point at a time. After receiving each point, we compute the convex hull of the points seen so far. (a) As a naive approach, we could run Graham’s scan once for each point, with a total running time of O(n2 log n). Write down the pesuedocode for this algorithm. (b) Develop an O(n2) algorithm to solve the problem. Write...
Haloo , i have java program , Java Program , dynamic program Given a knapsack with capacity B∈N and -n- objects with profits p0, ..., p n-1 and weights w0, ..., wn-1. It is also necessary to find a subset I ⊆ {0, ..., n-1} such that the profit of the selected objects is maximized without exceeding the capacity. However, we have another limitation: the number of objects must not exceed a given k ∈ N Example: For the items...
3. [10 marks] Suppose we would like to buy n items from SuperCheapStore (SCS); all items are currently priced at 1 CAD. Unfortunately there is no delivery and we have to deliver them home. The bad news are: we can fit only 1 item in our truck: it takes one day to drive home and back. There is even worse news -SCS charges us for the storage of undelivered items and the charge for storage of te i growth exponentially...