Algorithms Dynamic Programming & Optimization 2 — Questions and Answers
Question 1: What is the difference between top-down and bottom-up dynamic programming?
- Top-down uses iteration; bottom-up uses recursion
- Top-down uses memoized recursion; bottom-up fills a table iteratively (Correct answer)
- Top-down is faster; bottom-up uses more memory
- They are identical in approach
Correct answer: Top-down uses memoized recursion; bottom-up fills a table iteratively
Top-down DP uses recursive calls with memoization, while bottom-up DP iteratively fills a table from smallest subproblems to the full problem.
Question 2: The Edit Distance (Levenshtein) DP algorithm computes the minimum number of which operations to transform one string to another?
- Insertions and deletions only
- Insertions, deletions, and substitutions (Correct answer)
- Transpositions and reversals
- Character swaps only
Correct answer: Insertions, deletions, and substitutions
Edit Distance counts the minimum insertions, deletions, and substitutions required to transform one string into another, computed in O(mn) by DP.
Question 3: Matrix Chain Multiplication DP minimizes what?
- Number of matrices multiplied
- Total number of scalar multiplications (Correct answer)
- Memory used during multiplication
- Number of matrix additions
Correct answer: Total number of scalar multiplications
Matrix Chain Multiplication finds the optimal parenthesization that minimizes the total number of scalar multiplications when multiplying a chain of matrices.
Question 4: What is the space complexity of the standard LCS DP solution, and how can it be optimized?
- O(mn); optimized to O(min(m,n)) using two rows (Correct answer)
- O(m+n); no optimization possible
- O(1); already optimal
- O(mn²); optimized to O(mn)
Correct answer: O(mn); optimized to O(min(m,n)) using two rows
Standard LCS uses an O(mn) table, but since each row only depends on the previous row, it can be reduced to O(min(m,n)) space.
Question 5: Which problem is solved by the DP recurrence: dp[i] = max(dp[i-1] + arr[i], arr[i])?
- Longest Increasing Subsequence
- Maximum Subarray (Kadane's Algorithm) (Correct answer)
- 0/1 Knapsack
- Coin Change
Correct answer: Maximum Subarray (Kadane's Algorithm)
Kadane's Algorithm uses this recurrence to find the maximum subarray sum, deciding at each position whether to extend the previous subarray or start fresh.
Question 6: In the Longest Increasing Subsequence (LIS) problem, what is the time complexity of the DP approach?
- O(n)
- O(n log n)
- O(n²) (Correct answer)
- O(2ⁿ)
Correct answer: O(n²)
The standard DP approach for LIS checks all previous elements for each position, giving O(n²) time; a binary search optimization achieves O(n log n).
Algorithms Dynamic Programming & Optimization 2
What is the difference between top-down and bottom-up dynamic programming?