What is the time complexity of the following implementations of the rod cutting problem? Explain and...

Transcribed Image Text:

What is the time complexity of the following implementations of the rod cutting problem? Explain and identify how many recursions or iterations occurred when n = 4 on the following three algorithms. 1) CUT-ROD(p.n) 1 if n == 0 39=-00 4 for i=1 to n 2) 5 6 return q return 0 1 2 MEMOIZED-CUT-ROD-AUX(p.n.r) if r[n] 20 return r[n] q= max(q. p[i] + CUT-ROD(p.n-i)) 3 if n == 0 3) 4 5 6 7 8 r[n] = q 9 return q 6 7 8 q=0 else q = -00 for i=1 to n q=max(q. p[i] + MEMOIZED-CUT-ROD-AUX(p.n-i,r)) BOTTOM-UP-CUT-ROD (p.n) 1 let r[0..n] be a new array 2 r[0] = 0 3 for j = 1 to n 4 5 9=18 for i = 1 to j q=max(q. p[i] + r[j-i]) r[j] = q return r[n] What is the time complexity of the following implementations of the rod cutting problem? Explain and identify how many recursions or iterations occurred when n = 4 on the following three algorithms. 1) CUT-ROD(p.n) 1 if n == 0 39=-00 4 for i=1 to n 2) 5 6 return q return 0 1 2 MEMOIZED-CUT-ROD-AUX(p.n.r) if r[n] 20 return r[n] q= max(q. p[i] + CUT-ROD(p.n-i)) 3 if n == 0 3) 4 5 6 7 8 r[n] = q 9 return q 6 7 8 q=0 else q = -00 for i=1 to n q=max(q. p[i] + MEMOIZED-CUT-ROD-AUX(p.n-i,r)) BOTTOM-UP-CUT-ROD (p.n) 1 let r[0..n] be a new array 2 r[0] = 0 3 for j = 1 to n 4 5 9=18 for i = 1 to j q=max(q. p[i] + r[j-i]) r[j] = q return r[n]

Answer rating: 100% (QA)

The given implementations are related to solving the rod cutting problem using different approaches ... View the full answer