Question 1) Explain which one you should choose Memoized-Cut-Rod() or Cut-Rod(). Defend your decision by explaining the comparative advantages. In other words, where does the time saving come from ?
Question 2) What is the hidden cost when a recursive algorithm is implemented in a programming language ?
Question 3) Explain when you would consider Dynamic Programming over Divide-and-Conquer approach for a problem. What would be the nature of the problem ? Give a real-world problem where dynamic programming would be useful?
Question 4) Explain why we were able to use a) instead of b) (3 points) What is the main benefit doing so?
a) max 1≥i≥n ( p[i] + r(n-i) )
b) max 1≥i≥n ( r(i) + r(n-i) )
Feel free to use drawings