. Answer the following questions about developing a dynamic programming algorith
ID: 3910437 • Letter: #
Question
. Answer the following questions about developing a dynamic programming algorithm to com recursive function M(x, y), where M(z,y) satisfies the recurrence CO M(z, y) = ? M(z-i, y-i)(M(z, y-i) + M(x-i, y)), with base cases of 1 if y- 0, r if y , and 0 if y > . (a) [5 points) Give pseudocode for a naive recursive algorithm to compute M(r,y). (b) [10 points] What implementation would you recommend for a dynamic programming data struc- ture to compute M(x, y)? Justify your answer. Be sure to describe the size of your data structure. 10 points Give pseudocode or a memo zed dynamic programming algorithm to compute Mru (?Explanation / Answer
Hello Student!
(a) PseudoCode
M(x,y)
if y == 0
return 1;
if y == x
return x;
if y > x
return 0;
int sum = 0;
for int i = 1 ; i <= y ; i++
sum += M(x-i, y-i)*(M(x,y-i)+M(x-i, y));
end
return sum;
(b) We will make a 2D table. In which we will store the value of x and y. So, how will we proceed. We will firstly utilise the base conditions.
for i = 0 to x
for j = 0 to y
if j == 0
M[i][j] = 1;
else if i == j
M[i][j] = i;
else if j > i
M[i][j] = 0;
end
end
end
And, then we will apply the method stated in the questions.
The data structures which is used is arrays. The time complexity of the algorithm is O(n^3).
(c) Pseudo code -
M(x,y)
// Base condition.
for i = 0 to x
for j = 0 to y
if j == 0
M[i][j] = 1;
else if i == j
M[i][j] = i;
else if j > i
M[i][j] = 0;
end
end
end
// First loop to iterate through the row
for i = 1 to x
// Second loop to iterate through the column
for j = 1 to y
sum = 0
// The sum created at every point of index
for k = 1 to j
// simple equation utilised in the question.
sum = sum + M[x-k][y-k]*(M[x][y-k]+M[x-k][y]);
end
// We will add sum at that location
M[i][j] = sum;
end
end
return M[x][y];
Thank you. Feel free to ask anything. Please upvote, if you like the answer. Thank you again.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.