Virtual Labs

Longest Common Subsequence (LCS) Visualizer

What is a subsequence of a string?

a: A contiguous block of characters Explanation

Explanation

b: Characters chosen in order, not necessarily contiguous Explanation

Explanation

c: Any permutation of characters Explanation

Explanation

d: A prefix of the string Explanation

Explanation

If characters are removed from a string without changing order, the result is a:

a: Substring Explanation

Explanation

b: Subsequence Explanation

Explanation

c: Permutation Explanation

Explanation

d: Prefix Explanation

Explanation

Why is the first row and first column of the LCS DP table initialized to 0?

a: Because the algorithm starts counting from 1 Explanation

Explanation

b: Because comparing any string with an empty string yields an LCS of length 0 Explanation

Explanation

c: Because the table needs placeholder values Explanation

Explanation

d: Because 0 is the smallest positive integer Explanation

Explanation

Which property is common to both LCS and Rod Cutting problems?

a: Greedy choice property Explanation

Explanation

b: Optimal substructure Explanation

Explanation

c: Divide-and-conquer only Explanation

Explanation

d: Sorting-based solution Explanation

Explanation

Why use Dynamic Programming (DP) instead of a Greedy Algorithm (GA)?

a: GA is slow. Explanation

Explanation

b: DP uses constant auxiliary space. Explanation

Explanation

c: DP reuses the solved subproblems to avoid redundant work. Explanation

Explanation

d: DP always solves a problem in linear time. Explanation

Explanation

What happens if two strings share no common characters?

a: LCS is undefined Explanation

Explanation

b: LCS length is −1 Explanation

Explanation

c: LCS length is 0 Explanation

Explanation

d: LCS length equals string length Explanation

Explanation

In LCS, what does a diagonal arrow (↖) in the DP table indicate?

a: The characters at that position do not match Explanation

Explanation

b: The current cell value came from the cell above Explanation

Explanation

c: The characters at that position match and are part of the LCS Explanation

Explanation

d: The algorithm has reached a dead end Explanation

Explanation

What makes both problems computationally hard without DP?

a: Large input size only Explanation

Explanation

b: Overlapping subproblems Explanation

Explanation

c: Need for sorting Explanation

Explanation

d: Exponential number of possible solutions Explanation

Explanation

What is the time complexity of the naive recursive solution for LCS?

a: O(n) Explanation

Explanation

b: O(n²) Explanation

Explanation

c: O(2ⁿ) Explanation

Explanation

d: O(n log n) Explanation

Explanation

In the LCS DP table, dp[i][j] represents:

a: The number of matching characters in both strings Explanation

Explanation

b: The length of the LCS of the first i characters of X and the first j characters of Y Explanation

Explanation

c: The edit distance between X[1..i] and Y[1..j] Explanation

Explanation

d: The total number of subsequences of X[1..i] Explanation

Explanation