Virtual Labs

Longest Common Subsequence (LCS) Visualizer

Why do we add +1 in LCS DP when characters match?

a: To count both characters Explanation

Explanation

b: To extend an existing optimal subsequence Explanation

Explanation

c: To move diagonally Explanation

Explanation

d: To increase table size Explanation

Explanation

When characters don't match in LCS, why take max(dp[i-1][j], dp[i][j-1])?

a: To skip one character from either string Explanation

Explanation

b: To ensure lexicographical order Explanation

Explanation

c: To reduce space Explanation

Explanation

d: To force recursion Explanation

Explanation

What is the time complexity of the standard Dynamic Programming approach for LCS of two strings of lengths n and m?

a: O(n + m) Explanation

Explanation

b: O(n log m) Explanation

Explanation

c: O(n * m) Explanation

Explanation

d: O(max(n, m)) Explanation

Explanation

What does a tie in the DP table (e.g., dp[i-1][j] == dp[i][j-1]) imply?

a: The algorithm has an error Explanation

Explanation

b: Multiple optimal subsequences exist Explanation

Explanation

c: The strings are identical Explanation

Explanation

d: The LCS length is 0 Explanation

Explanation

If two strings X and Y are identical (X = Y), what is the LCS?

a: The empty string Explanation

Explanation

b: The first character only Explanation

Explanation

c: The string itself Explanation

Explanation

d: Half of the string Explanation

Explanation

For very large inputs, what is the biggest limitation in standard O(n*m) DP?

a: CPU Clock speed Explanation

Explanation

b: Floating point errors Explanation

Explanation

c: Memory usage (RAM) Explanation

Explanation

d: Internet bandwidth Explanation

Explanation

What is the main trade-off of the Rolling Array optimization for LCS?

a: Faster execution but incorrect results Explanation

Explanation

b: Less memory usage but cannot directly reconstruct the LCS string Explanation

Explanation

c: More memory usage but simpler code Explanation

Explanation

d: Lower time complexity but higher space complexity Explanation

Explanation

Which statement is true for X='ABCBDAB', Y='BDCABA'?

a: LCS length is 3 Explanation

Explanation

b: LCS length is 4 Explanation

Explanation

c: LCS length is 5 Explanation

Explanation

d: No common subsequence exists Explanation

Explanation

Can the LCS length be greater than the length of the shorter string?

a: Yes Explanation

Explanation

b: No Explanation

Explanation

c: Only if strings match Explanation

Explanation

d: Only for numeric strings Explanation

Explanation

What is the space complexity of Rod Cutting with DP (Bottom-Up)?

a: O(1) Explanation

Explanation

b: O(n) Explanation

Explanation

c: O(n²) Explanation

Explanation

d: O(2ⁿ) Explanation

Explanation