Question

In activity selection problem, of all the allowed activities we always picked the activity that ends first. Is picking the allowed activity that starts last a good greedy choice? When is it appropriate to use the dynamic programming approach - describe and explain the prerequisites. What is the difference compared to greedy approach? What is optimal substructure? Explain with an example. For problems that exhibit greedy-choice property, why is greedy approach preferable to dynamic programming approach?

Answer 1

13) Picking the activity that ends first will always helps in completing the activities that takes smaller time and going on to the activities that takes more time. Picking an activity depends on what you want to achieve.

For example if there is list of numbers as [1,2,3,4,5,6,7,8,9,10] and if you want to see an optimal solution to find the number of values that it takes to get a number 30 . In this case it would be better to take the last element 10. the optimal solution with repetitions will be selecting 3 - 10s

If you start from the first element you may get the solution but it wont be optimal solution.

14) The dynamic programming is applicable when the given problem consists of 'Optimal Substructure' and 'Overlapping subproblems'.

Optimal Substructure : if one can break a problem into smaller versions of it, and then combine the solutions of smaller problems, it solved the problem at hand.

Overlapping subproblems: While solving the smaller problem that leads to the same repetitive calculation steps, we term these as overlapping sub problems.

Hence instead of solving for the same calculation steps over and over, we can store solutions to previous calculated steps it into a memory such as hash map or an array.

The major difference between greedy and dynamic programming is that greedy algorithm never reconsiders its choices and the choices are made by using the past activities and you won't be ale to get the optimal solution all the time. On the other hand with dynamic programming is guaranteed to find a solution. dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.

15) Optimal Substructure : if one can break a problem into smaller versions of it, and then combine the solutions of smaller problems, it solved the problem at hand.

The shortest path problem: If a node P lies in the shortest path from a source node Q to destination node R then the shortest path from Q to R is combination of shortest path from Q to P and shortest path from P to R.

The Longest path problem: It doesn't have the optimal substructure. The combination of multiple longest paths will not lead to the optimal solution that we can get. i.e the longest path between two nodes doesn't have to be the longest path between the in between nodes.

16) The greedy- choice property always keeps a local solution after each and every step in the hope of finding a global solution.

In greedy approach you dont have to find or work with all the sub problems, if you feel by going to a certain intermediate stage will get you an optimal solution you can go to it and find the solution. The distance for reaching that node will be reduced. On the other hand in dynamic programming you need to solve all the sub problems and at the end you will get an optimal solution.