UNIT 3
Dynamic Programming
Dynamic Programming, particularly when discussed as "Unit 3" in a Design and
Analysis of Algorithms (DAA) course, typically covers the core concepts and
applications of this algorithmic paradigm.
Key Concepts:
Definition and Principle:
Dynamic Programming (DP) is a technique for solving complex problems by
breaking them down into simpler, overlapping subproblems. It stores the results
of these subproblems to avoid redundant computations, often using a table or
memoization. The "Principle of Optimality" is crucial, stating that an optimal
solution to a problem contains optimal solutions to its subproblems.
Properties for DP Applicability:
Overlapping Subproblems: The same subproblems are encountered
and solved multiple times. DP addresses this by storing and reusing
their solutions.
Optimal Substructure: An optimal solution to the overall problem can
be constructed from optimal solutions to its subproblems.
Comparison with Divide and Conquer:
While both break down problems, DP is a "bottom-up" approach, solving smaller
subproblems first and building up to the main solution, whereas Divide and
Conquer is "top-down." DP is used when subproblems overlap, while Divide and
Conquer is typically for independent subproblems.
Difference from Greedy Method:
The greedy method makes locally optimal choices hoping to find a global
optimum. DP explores multiple decision sequences to guarantee an optimal
solution.
Common Algorithms and Applications in Unit 3:
Computing Binomial Coefficients: Calculating "n choose k" using DP to
avoid recomputing factorials.
All-Pairs Shortest Path (Floyd-Warshall Algorithm): Finding the shortest
paths between all pairs of vertices in a graph, even with negative edge
weights (but no negative cycles).
Multistage Graphs: Finding the shortest path in a graph where nodes are
organized into stages.
Knapsack Problem: Selecting items with weights and values to maximize
total value within a capacity constraint.
Optimal Binary Search Trees (OBST): Constructing a binary search tree that
minimizes the expected search cost, considering key access probabilities.
Longest Common Subsequence (LCS): Finding the longest subsequence
common to two sequences.
General Approach to Solving DP Problems:
Define Subproblems:
Identify a class of subproblems that can be solved recursively.
Formulate Recurrence Relation:
Establish a recursive relationship between the solution to a subproblem and
solutions to smaller subproblems.
Compute Recurrence (Algorithm):
Develop an iterative or memorized recursive algorithm to compute the solutions
to subproblems, typically storing them in a table.
Construct Optimal Solution (Optional):
If needed, reconstruct the actual optimal solution by backtracking through the
stored results.
Matrix Chain Multiplication
Given the dimension of a sequence of matrices in an array arr[], where the
dimension of the ith matrix is (arr[i-1] * arr[i]), the task is to find the most
efficient way to multiply these matrices together such that the total number of
element multiplications is minimum. When two matrices of
size m*n and n*p when multiplied, they generate a matrix of size m*p and the
number of multiplications performed is m*n*p.
Examples:
Input: arr[] = [2, 1, 3, 4]
Output: 20
Explanation: There are 3 matrices of dimensions 2x1, 1x3, and 3x4,
Let the input 3 matrices be M1, M2, and M3. There are two ways to multiply ((M1
x M2) x M3) and (M1 x (M2 x M3)),
Please note that the result of M1 x M2 is a 2 x 3 matrix and result of (M2 x M3) is
a 1 x 4 matrix.
((M1 x M2) x M3) requires (2 x 1 x 3) + (2 x 3 x 4) = 30
(M1 x (M2 x M3)) requires (1 x 3 x 4) + (2 x 1 x 4) = 20
The minimum of these two is 20.
Input: arr[] = [1, 2, 3, 4, 3]
Output: 30
Explanation: There are 4 matrices of dimensions 1×2, 2×3, 3×4, 4×3. Let the input
4 matrices be M1, M2, M3 and M4. The minimum number of multiplications are
obtained by ((M1M2)M3)M4. The minimum number is 1*2*3 + 1*3*4 + 1*4*3 =
30
Input: arr[] = [3, 4]
Output: 0
Explanation: As there is only one matrix so, there is no cost of multiplication.
The time complexity of solving the matrix chain multiplication problem using dynamic
programming is O(n³), where n is the number of matrices in the chain.