Dynamic Programming – GATE CSE AlgorithmsPractice Questions & PYQs

To determine the correctness of the algorithms, we analyze the dependencies of the recurrence relation: $T[i][j] = 2T[i-1][j] + 3T[i][j-1]$. Computing $T[i][j]$ requires the values of $T[i-1][j]$ and $T[i][j-1]$.

1. Algorithm $B_1$: This algorithm iterates through rows $i$ then columns $j$. When computing $T[i][j]$, both $T[i-1][j]$ (computed in the previous row) and $T[i][j-1]$ (computed in the current row previously) are already updated, satisfying the dependency requirements. Thus, $B_1$ is correct.
2. Algorithm $B_2$: This algorithm iterates by the diagonal sum $s = i + j$. For a cell $(i, j)$ where $i + j = s$, the dependencies are $T[i-1][j]$ and $T[i][j-1]$, both of which have a sum of $s-1$. Since $B_2$ processes sums in increasing order $s = 2, 3, \ldots, 2n$, the required values from sum $s-1$ are always computed before the values for sum $s$. Thus, $B_2$ is also correct.

Since both algorithms satisfy the dependency order required by the recursive formulation, both are correct.

The multiplication cost for matrices $M_1(w \times x)$ and $M_2(x \times y)$ is $wxy$, and subsequently multiplying the result by $M_3(y \times z)$ costs $wyz$. Thus, the total cost for $(M_1 M_2)M_3$ is $C_1 = wxy + wyz = wy(x+z)$.
The cost for $M_2(x \times y)$ and $M_3(y \times z)$ is $xyz$, and multiplying $M_1(w \times x)$ by the result costs $wxz$. Thus, the total cost for $M_1(M_2 M_3)$ is $C_2 = xyz + wxz = xz(y+w)$.
To minimize computation time, we require $C_1 < C_2$:
$wy(x + z) < xz(w + y)$
Dividing both sides by $wxyz$ gives:
$\frac{wy(x + z)}{wxyz} < \frac{xz(w + y)}{wxyz} \implies \frac{x+z}{xz} < \frac{w+y}{wy} \implies \frac{1}{z} + \frac{1}{x} < \frac{1}{y} + \frac{1}{w}$
Rearranging results in the condition $\left(\frac{1}{x} + \frac{1}{z}\right) < \left(\frac{1}{w} + \frac{1}{y}\right)$.

This is a matrix chain multiplication problem. The goal is to find the parenthesization that minimizes the number of scalar multiplications. The dimensions are F1(2x25), F2(25x3), F3(3x16), F4(16x1), and F5(1x1000).

Let's analyze the parenthesization (F1(F2(F3F4)))F5:

1. Cost of (F3F4): Dimensions are (3x16) and (16x1). Cost = $3 \times 16 \times 1 = 48$. Result is a 3x1 matrix.
2. Cost of F2(F3F4): Dimensions are (25x3) and (3x1). Cost = $25 \times 3 \times 1 = 75$. Result is a 25x1 matrix.
3. Cost of F1(F2(F3F4)): Dimensions are (2x25) and (25x1). Cost = $2 \times 25 \times 1 = 50$. Result is a 2x1 matrix.
4. Cost of (F1(F2(F3F4)))F5: Dimensions are (2x1) and (1x1000). Cost = $2 \times 1 \times 1000 = 2000$.

Total cost = $48 + 75 + 50 + 2000 = 2173$. This is the optimal arrangement. An "explicitly computed pair" is defined as two original adjacent matrices being multiplied. In this optimal order, only F3 and F4 are multiplied directly.

The all-pairs shortest path problem requires finding the shortest distance between every pair of vertices $(u, v)$ in a graph. Prim's algorithm determines the Minimum Spanning Tree, while Dijkstra's and Bellman-Ford algorithms are designed to solve the single-source shortest path problem from a specific starting node. In contrast, the Floyd-Warshall algorithm uses dynamic programming to compute the shortest paths between all pairs of vertices. It iteratively updates the distance matrix using the recurrence relation $D_{ij} = \min(D_{ij}, D_{ik} + D_{kj})$, where $k$ represents an intermediate vertex. Thus, it is the specific algorithm among the choices that addresses the all-pairs requirement.

This is a matrix chain multiplication problem. We need to find the parenthesization that minimizes the number of scalar multiplications. The dimensions are $A_1: 10 \times 5$, $A_2: 5 \times 20$, $A_3: 20 \times 10$, $A_4: 10 \times 5$.

Let's evaluate the cost of the parenthesization $A_1((A_2A_3)A_4)$:

1. Cost of $(A_2A_3)$: Dimensions are $(5 \times 20)$ and $(20 \times 10)$. Multiplications = $5 \times 20 \times 10 = 1000$. The resulting matrix, let's call it $M_1$, has dimensions $5 \times 10$.
2. Cost of $(M_1A_4)$: Dimensions are $(5 \times 10)$ and $(10 \times 5)$. Multiplications = $5 \times 10 \times 5 = 250$. The resulting matrix, $M_2$, has dimensions $5 \times 5$.
3. Cost of $A_1(M_2)$: Dimensions are $(10 \times 5)$ and $(5 \times 5)$. Multiplications = $10 \times 5 \times 5 = 250$.

Total multiplications = $1000 + 250 + 250 = 1500$. This is the minimum possible cost among all parenthesizations.

The Floyd-Warshall algorithm is a classic example of the dynamic programming paradigm. It solves the all-pairs shortest path problem by building up a solution iteratively. It computes the shortest paths by considering all possible intermediate vertices for each pair of source and destination vertices. The solution for a problem with $k$ intermediate vertices is built upon the solution for $k-1$ vertices, which is the fundamental characteristic of dynamic programming.

To remove an element from a Young tableau while maintaining its properties, the empty spot is filled by the minimum of its right and bottom neighbors. This process is repeated until an element is replaced by $\infty$.

1. Remove 1. Replace with min(2, 3) = 2.
2. The now-empty spot of 2 is replaced by min(4, 5) = 4.
3. The now-empty spot of 4 is replaced by min(6, 12) = 6.
4. The now-empty spot of 6 is replaced by min(18, 23) = 18.
5. The now-empty spot of 18 is replaced by min(25, $\infty$) = 25.
   The elements that were shifted are 2, 4, 6, 18, and 25. This is a total of 5 entries.

To find the length of the longest common subsequence (LCS), we can use dynamic programming. Let $A = \text{"qpqrr"}$ and $B = \text{"pqprqrp"}$.

1. Calculate x (length of LCS): We can build an LCS table for strings A and B. The LCS is "qpqr" or "pqrr" or "qprr". The length of any of these is 4. Thus, $x = 4$.
2. Calculate y (number of LCSs): We need to identify all distinct longest common subsequences.
   • For "qpqr": (q at A[0], p at A[1], q at A[2], r at A[3]) maps to (q at B[0], p at B[1], q at B[3], r at B[4])
   • For "pqrr": (p at A[1], q at A[2], r at A[3], r at A[4]) maps to (p at B[1], q at B[3], r at B[4], r at B[6])
   • For "qprr": (q at A[0], p at A[1], r at A[3], r at A[4]) maps to (q at B[0], p at B[1], r at B[4], r at B[6])
     There are 3 distinct longest common subsequences: "qpqr", "pqrr", and "qprr". So, $y = 3$.
3. Calculate x + 10y: Substitute the values of x and y into the expression:
   $x + 10y = 4 + 10 \times 3 = 4 + 30 = 34$.

The final value is 34.

[CORRECT_OPTION: Not provided, numerical answer expected.]

To find the minimum number of scalar multiplications for multiplying four matrices $M_1, M_2, M_3, M_4$ with given dimensions $p \times q, q \times r, r \times s, s \times t$, we use the dynamic programming approach for matrix chain multiplication.
Given dimensions: $p=10, q=100, r=20, s=5, t=80$.
The possible parenthesizations are:

1. $((M_1 \times M_2) \times M_3) \times M_4$:

   • $(M_1 \times M_2)$ costs $pqr = 10 \times 100 \times 20 = 20000$. Resulting matrix is $10 \times 20$.
   • $((M_1 \times M_2) \times M_3)$ costs $(pqr) + (prs) = 20000 + (10 \times 20 \times 5) = 20000 + 1000 = 21000$. Resulting matrix is $10 \times 5$.
   • $(((M_1 \times M_2) \times M_3) \times M_4)$ costs $(pqr+prs) + (pst) = 21000 + (10 \times 5 \times 80) = 21000 + 4000 = 25000$.

2. $(M_1 \times (M_2 \times M_3)) \times M_4$:

   • $(M_2 \times M_3)$ costs $qrs = 100 \times 20 \times 5 = 10000$. Resulting matrix is $100 \times 5$.
   • $(M_1 \times (M_2 \times M_3))$ costs $(qrs) + (pqs) = 10000 + (10 \times 100 \times 5) = 10000 + 5000 = 15000$. Resulting matrix is $10 \times 5$.
   • $((M_1 \times (M_2 \times M_3)) \times M_4)$ costs $(qrs+pqs) + (pst) = 15000 + (10 \times 5 \times 80) = 15000 + 4000 = 19000$.

3. $(M_1 \times M_2) \times (M_3 \times M_4)$:

   • $(M_1 \times M_2)$ costs $pqr = 10 \times 100 \times 20 = 20000$. Resulting matrix is $10 \times 20$.
   • $(M_3 \times M_4)$ costs $rst = 20 \times 5 \times 80 = 8000$. Resulting matrix is $20 \times 80$.
   • $((M_1 \times M_2) \times (M_3 \times M_4))$ costs $(pqr) + (rst) + (prt) = 20000 + 8000 + (10 \times 20 \times 80) = 28000 + 16000 = 44000$.

Comparing the costs: $25000, 19000, 44000$. The minimum number of scalar multiplications is 19000.

The algorithm computes $L_i$ for $i$ from $n-1$ down to $0$, where $L_i$ depends on $L_{i+1}$. This shows an optimal substructure and overlapping subproblems characteristic of dynamic programming. Specifically, the length of the longest increasing subsequence starting at $i$ is found by looking at the length of the subsequence starting at $i+1$, if $A[i] < A[i+1]$. This iterative approach of building solutions from smaller, already solved subproblems is the essence of dynamic programming. The algorithm does not involve breaking the problem into independent subproblems (divide and conquer) nor pruning the search space (branch and bound). The complexity is linear, as each $L_i$ is computed in constant time after $L_{i+1}$ is known, leading to an $O(n)$ total time.

The recurrence relation $l(i, j)$ for the Longest Common Subsequence problem requires $l(i-1, j)$, $l(i, j-1)$, and $l(i-1, j-1)$ to be known before computing $l(i, j)$. Since these dependencies have either a smaller row index or a smaller column index, the values are always available if the traversal order respects these indices. Row-major order computes $L[i, j]$ by traversing rows sequentially, and column-major order does so by columns; both approaches ensure that the necessary sub-problems are solved before reaching the current cell. Thus, both traversal orders are valid for the dynamic programming solution.

The recursive definition for the length of the Longest Common Subsequence (LCS), $l(i, j)$, of prefixes $X[0 \ldots i-1]$ and $Y[0 \ldots j-1]$ is:

1. Base Case: $l(i, j) = 0$, if $i=0$ or $j=0$. (Given)
2. Matching Characters: If $i,j>0$ and $X[i-1] = Y[j-1]$ (the last characters match), then the LCS includes this character. We add 1 to the LCS of the preceding prefixes:
   $\text{expr1} = l(i-1, j-1) + 1$
3. Non-Matching Characters: If $i,j>0$ and $X[i-1] \neq Y[j-1]$ (the last characters do not match), the LCS is the maximum of two possibilities:
   • LCS of $X[0 \ldots i-2]$ and $Y[0 \ldots j-1]$ ($l(i-1, j)$).
   • LCS of $X[0 \ldots i-1]$ and $Y[0 \ldots j-2]$ ($l(i, j-1)$).
     $\text{expr2} = \max(l(i-1, j), l(i, j-1))$

Comparing with the given options:

• Options A and B refer to expr1 but do not match the correct formulation for matching characters.
• Option C correctly defines expr2 for non-matching characters.
• Option D for expr2 is incorrect as it includes $l(i,j)$ in its own definition and uses $l(i-1, j-1)$ incorrectly for the non-matching case.

is the correct definition for expr2.

The subset-sum problem asks if there exists a subset of the entire set $S = \{a_1, a_2, ..., a_n\}$ that sums to the target value $W$. The dynamic programming table entry $X[i, j]$ is defined to be TRUE if a subset of the first $i$ elements $\{a_1, ..., a_i\}$ sums to $j$. By setting $i = n$ (to include all elements of $S$) and $j = W$ (the target sum), we check if a subset of $\{a_1, ..., a_n\}$ sums to $W$. Thus, $X[n, W]$ is the entry that indicates whether a solution to the problem exists.

The problem of finding all-pairs shortest paths is most efficiently solved using the Floyd-Warshall algorithm. This algorithm relies on the principle of optimality, where the shortest distance between two vertices $i$ and $j$ is computed by iteratively considering intermediate vertices $k$. The recurrence relation $d[i][j] = \min(d[i][j], d[i][k] + d[k][j])$ demonstrates that the solution depends on solving and storing overlapping subproblems. Because the approach constructs the final solution by combining results from smaller, previously computed subproblems, it is a classic application of Dynamic Programming.

To determine if a sum $j$ is achievable using the subset $\{a_1, \dots, a_i\}$, we consider two cases:

1. Exclude $a_i$: The sum $j$ must be representable using only $\{a_1, \dots, a_{i-1}\}$, which corresponds to $X[i-1, j]$.
2. Include $a_i$: The remaining sum $j - a_i$ must be representable using $\{a_1, \dots, a_{i-1}\}$, which corresponds to $X[i-1, j - a_i]$.
   Since either case makes sum $j$ possible, we use the logical OR ($\vee$) operator to combine them.
   Thus, the recurrence relation is $X[i, j] = X[i-1, j] \vee X[i-1, j - a_i]$.

The total number of paths from (0,0) to (10,10) without any constraints is the number of ways to arrange 10 'right' moves and 10 'up' moves, which is $\binom{10+10}{10} = \binom{20}{10}$.

Next, we identify paths that traverse the forbidden segment from (4,4) to (5,4). A path traversing this segment must:

1. Go from (0,0) to (4,4). The number of ways is $\binom{4+4}{4} = \binom{8}{4}$.
2. Move one step right from (4,4) to (5,4). There is only 1 way to do this.
3. Go from (5,4) to (10,10). This requires $(10-5)=5$ right moves and $(10-4)=6$ up moves. The number of ways is $\binom{5+6}{5} = \binom{11}{5}$.

The number of paths that traverse the forbidden segment is the product of these steps: $\binom{8}{4} \times 1 \times \binom{11}{5} = \binom{8}{4} \binom{11}{5}$.

The number of distinct paths that do not traverse the forbidden segment is the total number of paths minus the number of paths that do traverse it:
$\binom{20}{10} - \binom{8}{4} \binom{11}{5}$
This matches option D.

To reach the point $(10,10)$ from $(0,0)$, the robot must make exactly 10 moves to the right and 10 moves up.
The total number of steps required is $10 \text{ (right)} + 10 \text{ (up)} = 20$ steps.
Each distinct path is a sequence of these 20 moves, where 10 are 'Right' (R) and 10 are 'Up' (U).
This is equivalent to choosing which 10 of the 20 total steps will be 'Right' moves (the remaining 10 will automatically be 'Up' moves).
The number of ways to choose 10 positions out of 20 is given by the binomial coefficient:
$\binom{20}{10} = \frac{20!}{10!10!}$
This matches option A.

Recursive calls use the call stack implicitly; backtracking unwinds this stack when a dead end is reached.

Backtracking incrementally builds candidates and abandons (backtracks) as soon as a partial candidate cannot lead to a valid solution.

A dead end (or non-promising node) is one where the bounding function determines no valid solution can exist in its subtree.