Longest Common Subsequences Quiz

What is the goal of the longest common subsequence (LCS) problem?

• To find the shortest subsequence of two sequences

• To find a maximum-length common subsequence of two sequences

• To sort two sequences in ascending order

• To merge two sequences into one

Which of the following is a characteristic of a subsequence?

• It must be of the same length as the original sequence

• It can be formed by deleting some elements without changing the order

• It must contain all elements of the original sequence

• It must be contiguous in the original sequence

What is the time complexity of the brute-force approach to solve the LCS problem?

• O(2^m)

• O(m^2)

• O(m+n)

• O(m*n)

In the LCS problem, what does the variable 'c[i,j]' represent?

• The length of the longest common subsequence of Xi and Yj

• The index of the longest common subsequence

• The total number of subsequences

• The maximum length of any subsequence

What is the optimal substructure property in the context of LCS?

• An LCS can be formed by combining any two subsequences

• An LCS of two sequences contains within it an LCS of prefixes of the two sequences

• An LCS must be contiguous in both sequences

• An LCS can only be found by checking all subsequences

Which of the following statements is true about the space complexity of the LCS algorithm?

• It requires O(m+n) space

• It requires O(m^2) space

• It requires O(m*n) space

• It requires no additional space

What is the output of the PRINT-LCS procedure for the sequences X = (A, B, C, B, D, A, B) and Y = (B, D, C, A, B, A)?

• (B, C, A)

• (B, C, B, A)

• (A, B, C)

• (C, B, D)

What is one way to improve the LCS algorithm mentioned in the text?

• By using a single array instead of a table

• By eliminating the b table and reconstructing LCS in O(m+n) time

• By using a different programming language

• By increasing the size of the c table

What is the running time of the procedure to compute the length of an LCS?

• Θ(m+n)

• Θ(2^m)

• Θ(m*n)

• Θ(m^2)

Which of the following is NOT a learning outcome of the session?

• Compare several algorithm design methods

• Develop a new algorithm from scratch

• Apply algorithm techniques and methods

• Explain fundamental concepts of analysis algorithms