We have been working very hard since 2009 to facilitate in your learning Read More. We can't keep up without your support. Donate Now.

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

# Graded Discussion Board (GDB) of CS502 Spring 2012

Dynamic Programming is always preferable over greedy approach " Support or contradict this statement with solid arguments.

Note:

A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 5-7 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered. Any request about such an acceptance will not be catered.

launched on July 9, 2012 and it will remain open till July 10, 2012.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Views: 910

### Replies to This Discussion

in GDB of cs502 our answer may be as follows:

yes, it is true.

although these both approaches are used to solve problems optimally, but in the same time there are some reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present with out thinking about future hence it can some time mislead us in such that it can not provide any solution to the problem.

for your reference there is also an example given below which will help to understand the greedy approach disadvantage.

let's suppose we want to prune (search) this given tree for getting best or maximum output or our goal is to find maximum value.

now it totally clears that using greedy approach if we start from node 7 at that point the best possible of both is 12 hence it will go towards 12 and then finally towards 6.

while if we look other side of tree the best possible we can obtain is 99.

so we can conclude that how simple greedy approach mislead us and thus we can not get our required solution.

this is example only for your understanding it is not part of our solution other wise if any one added this will get 0 marks.

so, don't copy paste write in your own words to get maximum marks....which must be 5 now after this solution.

enjoy......

bhai pic to nahi bani na

ha ha ha ha ha.

dear picture q bnani ha? wesy ye Wikipedia se li ha ap b check ker skty ho. yeh to sirf example k leye hai k ap bat smajh jeyen aur apny words me likh saken.......

akram ul haq  gud keep it up

thanks a lot

CS502GDB Solution Idea

In GDB of cs502 our answer may be asfollows:
Yes, it is true.
although these both approaches areused to solve problems optimally, but in the same time there are some reasonswhich make Dynamic programming preferable over greedy approach e.g. dynamicprogramming solves problems by breaking down in smaller sub problems and alsostores results in some form for future reference, which definitely comes alwaysin a solution and also in optimal one. while greedy approach always progress inbest possible solution at present with out thinking about future hence it cansome time mislead us in such that it can not provide any solution to theproblem.
for your reference there is also anexample given below which will help to understand the greedy approachdisadvantage.
So we can conclude that how simplegreedy approach mislead us and thus we can not get our required solution.

thanks

A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a "greedy" choice can be made of what looks best for the moment.

Consider this example.
You are standing at a place A. You are to goto B. There are intermediate places C1,C2 ...
You want to minimize distance travelled.
Greedy Method of Solving
You dont want to try all intermediate places. You goto the nearest intermediate place. Why? You feel by going to the nearest intermediate place, you will minimize the distance to B.
Dynamic Programming
You try all the places, but you store the previous result. Eg: To reach C3 in minimum distance, you reached by C1. So you store C1. So if you want to go to C5, by C3, you will goto C1 then C3 and then check if going from C3 to C5 is nearest.

Dynamic Programming is always preferable over greedy approach because reasons which make Dynamic programming preferable over greedy approach e.g. dynamicprogramming solves problems by breaking down in smaller sub problems and alsostores results in some form for future reference, which definitely comes alwaysin a solution and also in optimal one. while greedy approach always progress inbest possible solution at present with out thinking about future hence it cansome time mislead us in such that it can not provide any solution to the problem.

CSCS502 GDB

Topic:

Dynamic Programming is always preferable over greedy approach " Support or contradict this statement with solid arguments.

Note:

A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 5-7 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered. Any request about such an acceptance will not be catered.

CSCS502 GDB

Solution No.1

Dynamic programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub problems in a recursive manner. [ While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively; Bellman called this the "Principle of Optimality". Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure. If sub problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub problems.[5] In the optimization literature this relationship is called the Bellman equation.

Solution No.2

Yes, it is true. Although these both approaches are used to solve problems optimally, but in the same time there are some reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem.
for your reference there is also an example given below which will help to understand the greedy approach disadvantage.
So we can conclude that how simple greedy approach mislead us and thus we cannot get our required solution.

now it totally clears that using greedy approach if we start from node 7 at that point the best possible of both is 12 hence it will go towards 12 and then finally towards 6.
while if we look other side of tree the best possible we can obtain is 99.
so we can conclude that how simple greedy approach mislead us and thus we cannot get our required solution.
this is example only for your understanding it is not part of our solution otherwise if any one added this will get 0 marks.
so, don't copy paste write in your own words to get maximum marks....which must be 5 now after this solution.

Solution No.3

A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a "greedy" choice can be made of what looks best for the moment.

Consider this example.
You are standing at a place A. You are to goto B. There are intermediate places C1,C2 ...
You want to minimize distance travelled.
Greedy Method of Solving
You don’t want to try all intermediate places. You go to the nearest intermediate place. Why? You feel by going to the nearest intermediate place, you will minimize the distance to B.
Dynamic Programming
You try all the places, but you store the previous result. Eg: To reach C3 in minimum distance, you reached by C1. So you store C1. So if you want to go to C5, by C3, you will go to C1 then C3 and then check if going from C3 to C5 is nearest.

Solution No.4

Dynamic Programming is always preferable over greedy approach because reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem.

100% true solution

In GDB of cs502 our answer may be asfollows:
Yes, it is true.
Although these both approaches are used to solve problems optimally,

But in the same time there are some reasons which make Dynamic programming preferable over greedy approach

E.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference,

Which definitely comes always in a solution and also in optimal one?

While greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem.
for your reference there is also an example given below which will help to understand the greedy approach disadvantage.
So we can conclude that how simple greedy approach misleads us and thus we cannot get our required solution.

ZEESHAN NADEEM gud keep it up

## Latest Activity

Mani Siddiqui BS VIII posted discussions
22 minutes ago
54 minutes ago
57 minutes ago
Mani Siddiqui BS VIII posted a status
"کسی کی معصوم ہنسی کے پیچھے درد کو محسوس تو کرو سنا ہے ہنس ہنس کے لوگ خود کو سزا دیتے ہیں"
1 hour ago
jimmy zack updated their profile
1 hour ago
ARhum replied to ARhum's discussion Tu Bewafa Kahan TaK Hai,,,///
1 hour ago
ARhum replied to ARhum's discussion Poetry...!!!
1 hour ago
ARhum liked ARhum's discussion Pyaray Baba.....!!!!***
1 hour ago

1

2

3

## HELP SUPPORT

This is a member-supported website. Your contribution is greatly appreciated!