Select all the answers below which are TRUE Select all the answers below which a

Question

Select all the answers below which are TRUE

Select all the answers below which are TRUE. 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. O A greedy algorithm is a top-down approach. 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 starting time. 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. A greedy algorithm does not always yield to an optimal solution, but for some problems it does compute an optimal solution. The running time of the GREEDY-ACTIVITY-SELECTOR (s,f) algorithm is O(nlgn) if the input

Explanation / Answer

As per Chegg policy, I am provoding solution for first 4 subparts. For remaining parts, do upload them again.

1.) False. Running time for solving the LCS using Brute Force is O(2^n).

2.) True. LCS has running time of O(mn)

3.) True. Usually Greedy Algo performs in top-down fashion.

4.) False. activities need to be in sorted order of their finishing time not starting time.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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