Week 2 Flashcards
(28 cards)
What is dynamic programming?
A method for solving optimization problems by breaking them into subproblems and building solutions using optimal substructure and overlapping subproblems.
What does ‘programming’ refer to in dynamic programming?
In this context, ‘programming’ means scheduling or decision-making, not coding.
What are key applications of dynamic programming?
Shortest path algorithms, computational biology, resource allocation problems.
What is optimal substructure?
A problem has optimal substructure if the optimal solution can be constructed from optimal solutions of its subproblems.
What are the three parts of optimal substructure?
- Sequence of decisions. 2. Subproblem is an instance of the original. 3. Final solution combines decision + subproblem solution.
What is the rod cutting problem?
Given a rod of length L and a price table for rod pieces, determine how to cut the rod to maximize revenue.
What are the inputs of the rod cutting problem?
Rod length L and a price table of rod lengths and prices.
What is the goal of the rod cutting problem?
Maximize total revenue by optimally cutting the rod into pieces based on price table.
What is the recurrence formula for max revenue in rod cutting?
maxRevenue(L) = max(0, p1 + maxRevenue(L - l1), …, pn + maxRevenue(L - ln))
What are the base cases in the rod cutting recurrence?
maxRevenue(0) = 0; maxRevenue(L < 0) = -∞ (invalid length)
Why is naive recursion inefficient in dynamic programming?
Because it leads to repeated computation of the same subproblems (overlapping subproblems).
What are two techniques to avoid redundant computation in DP?
Memoization (top-down with cache) and bottom-up dynamic programming.
What is memoization?
Caching results of subproblems to avoid recomputation in recursive dynamic programming.
What is bottom-up dynamic programming?
An iterative approach that solves smaller subproblems first and builds up to the full problem.
What are signs a problem is suitable for dynamic programming?
It has optimal substructure, overlapping subproblems, and a recurrence relation.
What does the rod cutting DP recurrence represent?
The maximum revenue for a rod of length L by trying all valid cuts and combining them with subproblem solutions.
What are the four steps of dynamic programming?
- Identify optimal substructure
- Write the recurrence (value function)
- Memoize the results
- Recover the solution
What is the value function in dynamic programming?
A recurrence relation that expresses the optimal value of a problem in terms of its subproblems.
Why is memoization important in dynamic programming?
It avoids redundant computation by storing and reusing results of overlapping subproblems.
What base case is used for rod cutting problems when length < 0?
Assign -∞ to indicate invalid cuts (e.g., cutting more than the rod length).
What is the recurrence relation for the rod cutting problem?
MaxRevenue(L) = max(0, MaxRevenue(L - l₁) + p₁, …, MaxRevenue(L - lₙ) + pₙ)
What is the time complexity of the memoized rod cutting algorithm?
O(nL), where n is the number of cut options and L is the rod length.
What is stored in the memoization table T[i]?
The maximum revenue achievable for a rod of length i.
How is the S[i] table used in dynamic programming?
It stores the best decision (cut size) that leads to the optimal value at T[i].
