Questions a description of what a subproblem looks like can

Questions:

(a) description of what a subproblem looks like (can be as brief as 1 sentence)

(b) recurrence equation that links an optimal value for a subproblem to optimal values for smaller subproblems

(c)an explanation of why this recurrence allows to correctly find the value of an optimal segmentation

(d)a brief explanation of how to use the above to find the corresponding optimal segmentation

(e) a time and space efficiency analysis of your algorithm, with explanation

Need help, thank you.

Solution

a) a subproblems are nothing but divide-and-conquer algorithms or partition the problem into independent subproblems,
solve the subproblems recursively, and then combine their solutions to solve the original problem

b) and C)

Lets assume Example of fib series

Fib(n)
{
    if (n == 0) return M[0];
    if (n == 1) return M[1];
    if (Fib(n-2) is not already calculated) call Fib(n-2);
    if(Fib(n-1) is already calculated) call Fib(n-1);
    M[n] = M[n-1] + M[n-2]
    Return M[n];
}

the Fib series is nothing but the cur­rent num­ber is the sum of pre­vi­ous two num­ber. So whenerver we call it like

fib(5) we produce a call tree that calls the function on the same value many different times-

    fib(5)
    fib(4) + fib(3)
    (fib(3) + fib(2)) + (fib(2) + fib(1))
    ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
    (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

e)Sometimes it makes sense to be able to estimate the running time before starting a program.
The running time depends on the number n of the strings to be sorted.

Time complexity formula for fib Series will be calculated as

T(n) = T(n-1) + T(n-2) + 1 = 2n = O(2n)

recursion are space intensive because u have to keep treating each recursive call needing a block of memory.
The fibonacci example above are badly dependent on value of n , as n grows stack frames grows .
n-> infinity ur memory is blown...u will get memory overflow.
so its directly proportional to number of times the method is invoked which is here O(n)