0 votes
89 views
in Analysis of Algorithm by (98.9k points)
edited
Write the difference between greedy method and dynamic programming

1 Answer

0 votes
by (98.9k points)
selected by
 
Best answer
Greedy method Dynamic programming
Does not guarantee an optimal solution Guarantees an optimal solution
Assumes sub-problems do not overlap Assumes sub-problems overlap
Does little work Does more work
Only considers current choices Considers future choices
Constructs the solution from a set of feasible choices There is no specialized set of feasible choices
Selects a locally optimum choice Selects globally optimum choices
No concept of memorization Employs memorization
Examples: Knapsack, Job scheduling with deadlines, Kruskal, Prim’s Examples: All pair shortest path, 0/1 Knapsack, Travelling salesman problem, LCS

Related questions

0 votes
1 answer 93 views
0 votes
0 answers 28 views
0 votes
0 answers 37 views
0 votes
0 answers 39 views
0 votes
0 answers 36 views

Doubtly is an online community for engineering students, offering:

  • Free viva questions PDFs
  • Previous year question papers (PYQs)
  • Academic doubt solutions
  • Expert-guided solutions

Get the pro version for free by logging in!

5.7k questions

5.1k answers

108 comments

504 users

...