Consider two sequences X = ⟨0, 1, 2, 1, 3, 0, 1⟩ and Y = ⟨1, 3, 2, 0, 1, 0⟩. The length of the longest common subsequence of X and Y is
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 4
Explanation
⟨1, 3, 0, 1⟩ is common to both. Length 5 is impossible: in X, 3 comes after every 2, so a subsequence cannot contain both 3, 2 in Y's order with extra elements. LCS = 4.
More Data Structures and Algorithms questions
- Consider the postfix expression with single-digit operands: 6 2 3 * / 4 2 * + 6 8 * −. The top two elements of the stack after the second *…
- A binary search tree is constructed by inserting the following numbers in order : 60,25,72,15,30,68,101,13,18,47,70,34 The number of nodes…
- In a ternary tree, the number of internal nodes of degree 1,2 , and 3 is 4,3 , and 3 respectively. The number of leaf nodes in the ternary…
- Match List I with List II and choose the correct answer from the code given below. Where V and E are the number of vertices and edges in th…
- A K-colouring of an undirected graph G = (V, E) is a function c : V → {0, 1, …, K − 1} such that c(u) ≠ c(v) for every edge (u, v) ∈ E. For…
- Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this nod…