Algorithm Patterns. Give concise and to-the-point answers to the following. i. I

Question

Algorithm Patterns. Give concise and to-the-point answers to the following. i. Is the algorithm design pattern of Greedy Approach always performs worse (in terms of the quality of the solution found) than Dynamic Programming and Divide and Conquer? Explain your answer. Give example and/or justification for your answer. ii. What are the key elements of Dynamic Programming (DP); what properties of a problem would make you think a DP solution is possible? iii. What is the similar and different points of DP and Divide and Conquer methodologies?

Explanation / Answer

i.

No it is not so. It depends on implementation.

Gredy as the name suggests greedily looks for the solution and this is helpful in cases where actually it is greedily required. Lets take an example ..Let there are 4 weights 10, 15, 30, 35.. and you are asked to find min weight to reach a given total 'W'.

Dynamic would not be optimal in this case as it would find optimalityand sub optimal structure loaeding to optimal. Same is the case with divide and Conquer. However if you apply greedy over here, thge solution is esay to implement and optimal.

2.

See, DP is basically finding sub optimal solutions and storingf them so that they aren't re calculated.

Overlapping subproblems and optimal substructure are its key elements.

3.

See DP is not recursion while Divide and Conquer is.

DP is all about remembering solutions to sub optimal solutions so that they arent re calculated while Div and Conq has recursion and it will re calculate..

Both works for optimality.

While subproblems are independent of each other in Divide and Conquer while in DP its is not the case.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.