What is the time complexity of a tabulated (bottom-up) Dynamic Programming solution for the Fibonacci sequence?
O(n log n)
O(n^2)
O(n)
O(2^n)
What is the primary goal of finding the Longest Increasing Subsequence (LIS) in a given sequence of numbers?
Finding the subsequence with the maximum sum of elements.
Calculating the total number of increasing subsequences within the given sequence.
Identifying the shortest subsequence that includes all distinct elements of the original sequence.
Determining the longest subsequence where each element is greater than the previous one.
In the context of the Longest Common Subsequence (LCS) problem, what does a cell (i, j) in the tabulation table represent?
The length of the LCS of the prefixes of the two strings up to indices i and j
The maximum length of a subsequence ending at indices i and j
The number of characters that are common between the two prefixes
Whether the characters at indices i and j in the two strings are equal
How does the tabulated solution for Matrix Chain Multiplication systematically fill the table to arrive at the optimal solution?
It fills the table randomly, hoping to find a good solution quickly.
It performs a depth-first search through the table, exploring all possible parenthesizations.
It uses a greedy approach, always making the locally optimal choice.
It fills the table diagonally, starting from the main diagonal and moving towards the top-right corner.
What is a key advantage of using dynamic programming (memoization or tabulation) over a purely recursive approach for the Coin Change problem?
Dynamic programming reduces the space complexity of the solution.
Dynamic programming always finds a solution, while recursion might not.
Dynamic programming makes the solution easier to understand.
Dynamic programming avoids redundant calculations, improving efficiency.
What is the base case in the recursive approach for calculating Levenshtein distance?
When both strings have the same length.
When both strings are identical.
When the edit distance is zero.
When one or both strings are empty.
If two sequences have a Longest Common Subsequence of length 'L', is it possible for them to have a common subsequence of length greater than 'L'?
It depends on the characters present in the input sequences.
Yes
No
It depends on the length of the input sequences.
What does 'LCS' stand for in the context of Dynamic Programming?
Largest Common Subset
Longest Common String
Linear Computational Sequence
Longest Common Subsequence
In the memoized solution for the Fibonacci sequence, what data structure is typically used to store previously computed values?
Graph
Array
Stack
Queue
What is the primary purpose of using dynamic programming to calculate the Levenshtein distance?
To sort a list of strings in lexicographical order.
To find all possible edit operations between two strings.
To reduce the time complexity by storing and reusing previously computed distances.
To determine if two strings are anagrams of each other.