LCS Quiz

Which of the following methods can be used to solve the longest common subsequence problem?

• Recursion

• Dynamic programming

• Both recursion and dynamic programming

• Greedy algorithm

Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

• 9

• 8

• 7

• 6

What is the time complexity of the brute force algorithm used to find the longest common subsequence?

• O(n)

• O(n^2)

• O(n^3)

• O(2^n)

Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?

• hgmq

• cfnq

• bfmq

• fgmna