Dynamic Programming – GATE CSE AlgorithmsPractice Questions & PYQs

The bounding step computes an optimistic bound on the best solution achievable from a given node's subtree. For minimization problems, a lower bound is computed; if it exceeds the current best (upper bound), the subtree is pruned. For maximization, an upper bound is computed; if it is below the current best (lower bound), the subtree is pruned. This avoids exhaustive exploration while guaranteeing the optimal solution is not missed.

(A) TRUE: Without constraint pruning, each of $N$ rows can have a queen in any of $N$ columns - $N^N$ leaves. With the row-uniqueness constraint (one queen per row), leaves are at most $N!$ (permutations of column assignments). (B) TRUE: By placing exactly one queen per row (one queen at level $k$ of the tree), the row constraint is implicitly satisfied. (C) TRUE: The pruning checks column uniqueness and diagonal uniqueness: for queen at $(i, c_i)$ and $(j, c_j)$, check $c_i \neq c_j$ and $|c_i - c_j| \neq |i - j|$. (D) TRUE: $N=1$: 1 solution (trivially). $N=2$: 0 solutions (impossible to place 2 non-attacking queens on $2\times2$). $N=3$: 0 solutions (impossible on $3\times3$). First non-trivial solutions appear at $N=4$.

Current state: value=20, weight=6, remaining capacity=10-6=4. Remaining items sorted by v/w: item3(v=12,w=5, ratio=2.4), item4(v=8,w=4, ratio=2.0). Remaining capacity=4. Take fractional item3: 4/5 of item3 → value += 12×(4/5) = 9.6. No remaining capacity for item4. Upper bound = 20 + 9.6 = 29.6.

With memoization, each unique subproblem T(k) for k = 0, 1, ..., n is computed exactly once and stored. There are n+1 distinct subproblems, each taking O(1) to compute after its sub-subproblems are resolved. Total time = O(n). This demonstrates the exponential-to-polynomial speedup achievable by DP when overlapping subproblems are cached.

B: Branch and Bound computes explicit bounds on the objective function to prune subtrees; Backtracking prunes based on constraint violations (infeasibility). C: B&B maintains an incumbent (global best) to enable bound-based pruning; standard Backtracking does not maintain a global optimum for pruning. D: B&B can use BFS, DFS, or best-first search strategies; Backtracking is inherently DFS. A is FALSE - Backtracking can also solve optimization problems (though less efficiently than B&B for such cases).

The recurrence dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j], else max(dp[i+1][j], dp[i][j-1]) is for the Longest Palindromic Subsequence. Here dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i..j]. If the two ends match, they contribute 2 to the inner palindrome; otherwise we try excluding either end. Base case: dp[i][i] = 1 (single character is a palindrome of length 1).

Once intervals are sorted by finish time and p(j) values are precomputed (each using binary search in O(log n)), the DP recurrence OPT(j) = max(wⱼ + OPT(p(j)), OPT(j-1)) fills n entries in O(1) each (since p(j) is already computed). This gives O(n) time for the DP phase itself. Including sorting and binary search for p(j) values, total time is O(n log n).

With 2 eggs and 10 floors, the optimal strategy uses a triangular number approach. With k trials, we can check at most k(k+1)/2 floors. For k=4: 4(5)/2 = 10 floors - exactly enough. Drop first egg at floors 4, 7, 9, 10 (gaps of 4, 3, 2, 1). Worst case = 4 trials. For k=3: 3(4)/2 = 6 < 10 - insufficient. Answer = 4.

In 0/1 Knapsack, each item can be taken at most once. dp[i][w] = max value using first i items with capacity w. Either item i is not taken: dp[i-1][w], or item i is taken (if wᵢ ≤ w): dp[i-1][w-wᵢ] + vᵢ. The key is using dp[i-1][...] (previous row) for both cases, ensuring each item is counted at most once. Option B uses dp[i][w-wᵢ] which allows repeated use (unbounded knapsack), not 0/1.

Checking all subsets of $S = \{3, 5, 6, 7\}$ that sum to $T = 15$: $3+5+7 = 15$ ✓ (option A). $3+6+7 = 16$ ✗. $5+6+7 = 18$ ✗. $3+5+6 = 14$ ✗. $3+12$ - 12 not in set. $\{6, 9\}$ - 9 not in set. Only $\{3, 5, 7\}$ sums to 15. Backtracking would find this by trying include/exclude for each element and pruning when partial sum exceeds 15 or remaining elements cannot make up the deficit.

Floyd-Warshall maintains a 2D distance matrix D of size n × n. At each of the n iterations (for each intermediate vertex k), D is updated in-place. Only the current iteration's n × n matrix is needed (the in-place update works because D^(k)[i][k] = D^(k-1)[i][k] and D^(k)[k][j] = D^(k-1)[k][j] never change). So space complexity = O(n²).

Dynamic Programming is applicable when a problem has: (1) Optimal substructure - the optimal solution of the problem can be constructed from optimal solutions of its subproblems, and (2) Overlapping subproblems - the same subproblems are solved multiple times, allowing memoization or tabulation to avoid redundant computation. Greedy choice property is required for greedy algorithms, not DP.

(A) TRUE: Each node in the state space tree stores the current partial assignment - e.g., in N-Queens, a node at level $k$ represents queens placed in rows 1 through $k$. (B) TRUE: A leaf node is either a complete valid solution or a dead end (a partial solution that cannot be extended because all next choices violate constraints). (C) FALSE: The state space tree is not always binary. In the N-Queens problem, each node at level $k$ has up to $N-k$ children (one per column choice). In graph colouring, each node has up to $m$ children. Binary trees occur only in include/exclude problems (like subset sum). (D) TRUE: Backtracking traverses the state space tree depth-first, going as deep as possible before backtracking when a dead end is reached.

0/1 knapsack requires DP due to overlapping subproblems.

LCS: overlapping subproblems (LCS[i][j] reuses LCS[i-1][j] and LCS[i][j-1]) and optimal substructure (LCS of X[1..m] and Y[1..n] depends on LCS of prefixes). Matrix Chain: subproblems m[i][j] overlap and optimal split gives optimal substructure. Floyd-Warshall: D^(k)[i][j] depends on previous k values and has optimal substructure. Fractional Knapsack: solved greedily - no overlapping subproblems, greedy choice property instead.

Shortest path in a weighted graph is solved by Dijkstra's or Bellman-Ford (greedy/DP). The others are classic backtracking problems.

(i) FALSE: Branch and Bound's running time depends heavily on the bounding function quality and problem instance. For 0/1 Knapsack, DP runs in O(nW) pseudo-polynomial time which can be faster than B&B in many cases. (ii) TRUE: B&B is complete and exact - given sufficient time and memory, it always finds the optimal solution (assuming admissible bounds). (iii) TRUE: The number of nodes pruned - and therefore the practical running time - depends directly on how tight the bounding function is. (iv) FALSE: B&B applies equally to maximization problems (using upper bounds and incumbent as lower bound).

LC (Least Cost) Branch and Bound always expands the node with the best (lowest for minimization) bound next. This ensures that the first complete feasible solution found is likely to be optimal or near-optimal, enabling aggressive pruning of remaining nodes. FIFO B&B (BFS) explores level by level regardless of bound quality, often expanding many nodes before finding a good feasible solution. In general, LC B&B expands fewer or equal nodes compared to FIFO, though it requires a priority queue with O(log n) operations.

DP table: dp[0]=0, dp[1]=1(1), dp[2]=2(1+1), dp[3]=3, dp[4]=4, dp[5]=1(5), dp[6]=1(6), dp[7]=2(1+6), dp[8]=2(2+6 or 1+1+6→3? wait), dp[9]=1(9), dp[10]=2(1+9), dp[11]=2(5+6). So minimum coins for 11 = 2 (coin 5 + coin 6). Answer = 2. Note: greedy with largest first would give 9+1+1 = 3 coins - wrong! DP gives the optimal 2.

While branch and bound can find optimal solutions, it doesn't guarantee it in all cases, especially if the problem is NP-hard.