Which of the following is a valid base case in the recursive solution for the Longest Common Subsequence (LCS) problem?
If the last characters of both strings match.
If one or both of the input strings are empty.
If both input strings are non-empty.
If the lengths of the input strings are equal.
In a recursive solution for the LIS problem, what is the overlapping subproblem?
Determining the LIS for the same sub-sequence starting at different indices.
Finding the maximum element in a subarray.
Calculating the sum of elements in a given range.
Sorting the given sequence in ascending order.
In the memoized solution to the Coin Change problem, what parameters are typically used to memoize the results?
The total number of coins used and the current amount formed.
The maximum coin denomination and the target amount.
The current index of the coin denomination and the remaining amount to be formed.
The minimum number of coins used so far and the remaining coin denominations.
What is a key advantage of using dynamic programming (memoization or tabulation) over a purely recursive approach for the Coin Change problem?
Dynamic programming avoids redundant calculations, improving efficiency.
Dynamic programming reduces the space complexity of the solution.
Dynamic programming makes the solution easier to understand.
Dynamic programming always finds a solution, while recursion might not.
The Longest Common Subsequence problem exhibits which of the following properties that make it suitable for Dynamic Programming?
Divide and Conquer
Optimal Substructure and Overlapping Subproblems
Backtracking
Greedy Choice Property
In the context of the 0/1 Knapsack problem, what does the '0/1' signify?
You can only pick a maximum of one item from the available set.
An item can either be fully included or excluded from the knapsack.
The weight of each item can be either 0 or 1.
The value of each item can be either 0 or 1.
In the dynamic programming table for Levenshtein distance, what does the cell at index (i, j) typically represent?
The edit distance between the first i characters of the first string and the first j characters of the second string.
The number of deletions required to transform the first string into the second string.
Whether the first i characters of the first string are identical to the first j characters of the second string.
The number of insertions required to transform the first string into the second string.
How does memoization improve the efficiency of the recursive solution for LIS?
It stores the results of overlapping subproblems to avoid recomputation.
It sorts the input sequence to reduce the search space.
It converts the recursive solution into a dynamic programming solution.
It eliminates tail recursion, making the solution iterative.
In the context of edit distance, what does a diagonal transition in the dynamic programming table represent?
Insertion of a character
Deletion of a character
Substitution of a character
Matching of two characters
What is the base case in the recursive approach for calculating Levenshtein distance?
When both strings have the same length.
When one or both strings are empty.
When the edit distance is zero.
When both strings are identical.