Algorithms Dynamic Programming & Optimization 2

Question 1

What is the difference between top-down and bottom-up dynamic programming?

Accepted Answer

Top-down uses memoized recursion; bottom-up fills a table iteratively

Answer

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?

Accepted Answer

Insertions, deletions, and substitutions

Answer

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?

Accepted Answer

Total number of scalar multiplications

Answer

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?

Accepted Answer

O(mn); optimized to O(min(m,n)) using two rows

Answer

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])?

Accepted Answer

Maximum Subarray (Kadane's Algorithm)

Answer

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.

Algorithms Practice Test

Algorithms Practice Test

Algorithms Dynamic Programming & Optimization 2