Select all the answers below which are TRUE The running time of the GREEDY-ACTIV

Question

Select all the answers below which are TRUE The running time of the GREEDY-ACTIVITY-SELECTOR (s,f) algorithm is O(n) if the input activities are not sorted. A greedy algorithm is a top-down approach. Let Z be an LCS of two sequences X and Y. Then the length of Z is at most min (length X, length Y) All greedy choices lead to optimal solutions. To use the greedy algorithm discussed in class for solving the activity selection problem, all the activities have to be sorted in monotonically increasing order of their duration. To show that a greedy algorithm is an optimal solution, we need to prove the subproblem overlapping property and the greedy choice property The running time for solving the Longest Common Subsequence using Brute Force is exponential.

Explanation / Answer

1. True -  GREED-ACTIVITY-SELECTOR runs in O(n).
2. False -

Top Down refers to machine learning algorithms that look at the entire dataset rather than subsets, as distinct from, say, agglomerative techniques.

Greedy means that you only look one stage ahead, you don’t try to globally optimize.

3. True

4. False.
Choosing the activity of least duration will not always produce an optimal solution. For example, we have a set of activities {(3, 5), (6, 8), (1, 4), (4, 7), (7, 10)}. Here, either (3, 5) or (6, 8) will be picked first, which will be picked first, which will prevent the optimal solution of {(1, 4), (4, 7), (7, 10)} from being found.

5. True
Requires Sorting the input activities by increasing finishing time.

6.False. This two property are needed to prove
I. Greedy choice property.
II. Optimal substructure property

7. True

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.