Select all the answers below which are TRUE ? To use the greedy a gorithm discus

Question

Select all the answers below which are TRUE ? To use the greedy a gorithm discussed in class or solving the activ y selection problem, all the act ities ave to e sorted n monotonically creasing ode o t er starting me. ? The running time for solving the Longest Common Subsequence using Brute Force is O(n). LCS-Length(X.Y) algorithm has the running time RT-O(mn), where n is the length of X and m is the length of Y ? Let Z be an LCS of two sequences X and Y. Then the length of Z is at least half of the length of X ? The running time of the GREEDY-ACTIVITY-SELECTOR (sf) algorithm is O(nlgn) if the input activities are not sorted. O A greedy algorithm is a top-down approach. ? A greedy algorithm does not always yield to an optimal solution, but for some problems it does compute an optimal solution.

Explanation / Answer

1. FALSE ( All the activities are sorted in increasing order of their finishing time).

2. FALSE ( Running time is O(2n) )

3. TRUE

4. TRUE

5. TRUE

6.TRUE

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.