Circle True or False for each of the following statements. 1) True False A greed
ID: 3912685 • Letter: C
Question
Circle True or False for each of the following statements. 1) True False A greedy algorithm always makes the choice that looks best at the 2) True False A greedy algorithm makes a globally optimal choice in the hope that this 3) True False Greedy algorithms always yield optimal solutions. 4) True False GREEDY-ACTIVITY-SELECTOR sometimes finds an optimal solution to 5) True False Two ingredients that are exhibited by most problems that lend 6) True False Greedy-choice property: a globally optimal solution can be arrived at by moment. choice will lead to a locally optimal solution. an instance of the activity-selection problem themselves to a greedy strategy: the overlapping subproblems and optimal substructure. making a locally optimal (greedy) choice. 7) True False A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. 8) True False The 0-1 knapsack problem is solvable by a greedy strategy, where fractional knapsack problem is not.Explanation / Answer
1.
A greedy algorithm always makes the choice that looks best at the moment.
True.
2.
A greedy algorithm makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.
False
3.
Greedy algorithm always yields the optimal solution.
True
4.
Greedy activity selector sometimes finds an optimal solution to an instance of the activity-solution problem.
True
5.
Two ingredients that are exhibited by most problems that lend themselves to a greedy strategy: the overlapping subproblems and optimal substructure.
False
6.
Greedy-choice property: a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
True
7.
A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
True
8.
The 0-1 knapsack problem is solvable by a greedy strategy, where fractional knapsack problem is not.
False.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.