nucch nuinber Fn Using a bottom-up (iterative) dynamic programming approach. You
ID: 3712781 • Letter: N
Question
nucch nuinber Fn Using a bottom-up (iterative) dynamic programming approach. You can use either Java or The Mergesort algorithm generates and solves subproblems according to the within Mergesort? Would it improve the running time? Explain your answer. pseudocode. c divide and conquer strategy. Could a dynamic programming approach be used Using either Java or pseudocode, write a recursive procedure Pow(x, N) to compute xN, where N is a positive integer. Use a divide and conquer strategy. Hint: d i for even N for odd N. XN -X(N-1)/2 x x(N-1) /2 x Write recurrence expressions for the running time T(N) of your Pow procedure in the following cases: ii) T(N) = T(N) for even N for odd N. The four parts carry, respectively, 20%, 45%, 15%, and 20% of the marks.Explanation / Answer
_________________________________________C_________________________________________________The key words here are "overlapping subproblems" and "optimal substructure". When you execute mergesort, you are recursively breaking down your array into smaller pieces that do not overlap. You never operate over the same elements of the original array twice during any given level of the recursion. This means there is no opportunity to re-use previous calculations. On the other hand, many problems DO involve performing the same calculations over overlapping subsets, and have the useful characteristic that an optimal solution to a subproblem can be re-used when computing the optimal solution to a larger problem.
So that is why, merge sort can not be performed usig Dynamic Programming.
d=
int pow(int x,int n)
{
if (n == 1)
return x;
if(n % 2 == 0)
{
return (pow(x, n/2)*pow(x, n/2));
}
else
{
return (x *pow(x, (n-1)/2)*pow(x, (n-1)/2));
}
}
//T(1) = 1
//T(n) = 2T(n/2) n is even
//T(n) = 2T(n-1 / 2) + 1 n is odd
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.