Select all the answers below which are TRUE. To use the greedy algorithm discuss

Question

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

Explanation / Answer

1) We can select first activity based on the finishing time, not by starting time.

Ans : False

2) If we apply bruteforce LCS algo. It has an exponential complexity

Ans : False

3) The memoization algorithm would compute the LCS in time O(m*n). where |X| = m, |Y| = n

Ans : True

4) Let x = abcd , y = xyza

here LCS is = 1 < |X| /2 or |Y|/2

Ans : False

5) If input not sorted activity selection algo takes O(NlogN)

Ans : True

7) In greedy algo we always select an optimal solution at a paticular point of time. It doesn't give optimal solution for some problems.But it can give for some Problems.

Ans : true

1) We can select first activity based on the finishing time, not by starting time.

Ans : False

2) If we apply bruteforce LCS algo. It has an exponential complexity

Ans : False

3) The memoization algorithm would compute the LCS in time O(m*n). where |X| = m, |Y| = n

Ans : True

4) Let x = abcd , y = xyza

here LCS is = 1 < |X| /2 or |Y|/2

Ans : False

5) If input not sorted activity selection algo takes O(NlogN)

Ans : True

6) Ture

7) In greedy algo we always select an optimal solution at a paticular point of time. It doesn't give optimal solution for some problems.But it can give for some Problems.

Ans : true

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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