Given two sequences X and Y: X = Y = The longest common subsequence of X and Y is:
| A. | <b, c, a> |
| B. | <c, a, b> |
| C. | <b, c, a, a> |
| D. | <b, c, b, a> |
|
Option: D Explanation :
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
A sequence G is said to be a common subsequence of X and Y, if Z is a subsequence of both X and Y.
Here X = <a, b, c, b, d, a, >, the sequences <b,c,a>, <c,a,b>, <b,c,b,a> are subsequences of X.
Given a second sequence of symbols Y = <b, d, c, a, b, a>, then <b,c,a>, <c,a,b>, <b,c,b,a> are common subsequences to both X and Y.
However, the longest common subsequence of X and Y is <b,c,b,a>
Click on Discuss to view users comments. |
In Activity-Selection problem, each activity i has a start time si and a finish time fi where s i ≤f i . Activities i and j are compatible if:
| A. | si ≥fj |
| B. | sj ≥fi |
| C. | si ≥fj or sj ≥fi |
| D. | si ≥fj and sj ≥fi |
|
Option: C Explanation : Click on Discuss to view users comments. |
If there are n integers to sort, each integer has d digits and each digit is in the set {1,2, ..., k}, radix sort can sort the numbers in:
| A. | O(d n k) |
| B. | O(d nk ) |
| C. | O((d+n)k) |
| D. | O(d(n+k)) |
|
Option: D Explanation : Click on Discuss to view users comments. |
Floyd-Warshall algorithm utilizes ............... to solve the all-pairs shortest paths problem on a directed graph in ................ time.
| A. | Greedy algorithm, θ(V3) |
| B. | Greedy algorithm, θ(V2lgn) |
| C. | Dynamic programming, θ(V3) |
| D. | Dynamic programming, θ(V2lgn) |
|
Option: C Explanation : Click on Discuss to view users comments. |
