Question

Algorithms Question

Select all the correct items.
Group of answer choices
a. Dynamic programming algorithms are often more time-efficient than greedy algorithms.
b. Greedy algorithms are often more time-efficient than dynamic programming algorithms.
c. The optimal solution cannot be guaranteed by greedy algorithms, but dynamic programming guarantees an optimal solution if the optimal sub-structure applies.
d. Dynamic programming may not guarantee an optimal solution, even if the optimal sub-structure applies.

Which of the following greedy strategies results in an optimal solution for the activity selection problem? Select all that applies.

a. Earliest start time
b. Latest finish time
c. Earliest finish time
d. Latest start time

Answer 1

1. Solution : The correct answers are “options b and c”.

b. Greedy algorithms are often more time-efficient than dynamic programming algorithms.
c. The optimal solution cannot be guaranteed by greedy algorithms, but dynamic programming

Explanation :

Greedy algorithms provides a locally optimal solution which may not always give optimal final solution but requires less time to reach to a result. On the other hand, dynamic programming breaks down the problem into sub parts in order to get a optimal final solution. Greedy algorithms are less efficient than dynamic algorithms in finding a final optimal solution. However, greedy algorithms takes less time or are more time efficient than that of dynamic programming algorithms.

2. Solution : The correct answers are “options c and d”.

Earliest finish time

Latest start time

Explanation :

Earliest finish time refers to selection of those activities which have finished or completed earliest. The latest start time of an activity refers to the difference of the latest finish time and the total duration of a that activity. Both of these strategies will ensure that the activities with most probability of getting optimal solution is selected and thus will result in an optimal solution.