Question

Write the recurrence for each of the following two problems. Try to
come up with the solution using your understanding.
1) Maximal subarray problem
2) Weighted interval selection problem

Answer 1

1) Maximal subarray problem
It is the problem by which finding the adjacent subarray with the largest sum,within one dimensional array.
Properties of Maximal subarray problem are:

Property 1:
If an array includes all non-negative numbers,then the problem is trivial; a maximum subarray is the entire array.
Property 2:
If an array including all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array.
Property 3:
Different sub-arrays may have the same maximum sum.


Solution of recurrence in Maximal subarray problem
The algorithmic techniques used for this problem are
a) Divide and conquer solution: Divide: Firstly dividing the problem into some sub problem.
Conquer:Then the sub problem by calling recursively until sub problem solved.
Combine: The Sub problem solved so that to will get find the problem solution
DAC(a, i, j)
{
if(small(a, i, j))
return(Solution(a, i, j))
else
m = divide(a, i, j) // f1(n)
b = DAC(a, i, mid) // T(n/2)
c = DAC(a, mid+1, j) // T(n/2)
d = combine(b, c) // f2(n)
return(d)
}
b) Brute force Solution
The algorithm consists in checking, at all positions in the text between 0 and n-m, whether an occurrence of the pattern starts
there or not.There after it shifts the pattern by exactly one position to the right.
The brute-force method is then expressed by the algorithm
c ← first(P)
while c ≠ Λ do
if valid(P,c) then
output(P, c)
c ← next(P, c)
end while
Here the first procedure should return Λ if there are no candidates at all for instance P.

Qn 2) Weighted interval selection problem
If a list of jobs are given,each job has starting and finishing time,and profit associated with it,
here in order to find maximum profit subset of non overlapping jobs.
Consider the below job with starting time,finishing time and profit.
Input: Number of Jobs n = 4
Job Details {Start Time, Finish Time, Profit}
Job 1: {1, 2, 50}
Job 2: {3, 5, 20}
Job 3: {6, 19, 100}
Job 4: {2, 100, 200}
Output: The maximum profit is 250.

Solution of Weighted interval selection problem
1. Naive Recursive Solution
It is a closed form solution,by which sort the jobs in increasing order of their finish times and
use recursion in order to solve this problem.

1) Initially sort the jobs according to finish time.
2) Apply the recursive process.

findMaximumProfit(arr[], n)
{
a) if (n == 1) return arr[0];
b) Return the maximum of following two profits.
(i) Maximum profit by excluding current job, i.e.,
findMaximumProfit(arr, n-1)
(ii) Maximum profit by including the current job
}
2. Dynamic Programming
It is used for optimization over recursion. Wherever we see a recursive solution that has repeated calls
for same inputs, we can using Dynamic Programming. The idea is to simply store the results of subproblems,
so that we do not have to re-compute them when needed later.
It mainly reduces time complexities from exponential to polynomial. For example, if we write recursive solution for Fibonacci Numbers, we get exponential time complexity and if we storing the solutions of subproblems, time complexity reduces to linear.