Dynamic Programming – GATE CSE AlgorithmsPractice Questions & PYQs

The OBST DP has three nested loops: the outer loop iterates over chain length (n iterations), the middle loop iterates over starting indices (n iterations), and the inner loop iterates over the root choice r (up to n iterations). This gives O(n³) time complexity. Space complexity is O(n²) for the cost and root tables.

In the subset sum state space tree, each element $s_i$ either is included (left branch) or excluded (right branch) - a binary decision at each level. The tree has $n$ levels with branching factor 2, giving $2^n$ leaf nodes. The total number of nodes in a complete binary tree of height $n$ is $2^0 + 2^1 + \ldots + 2^n = 2^{n+1} - 1$. Pruning occurs when the partial sum exceeds $T$ (if sorted in increasing order) or the remaining elements cannot possibly reach $T$.

Matrix Chain Multiplication DP fills an n×n table (m[i][j] = minimum cost to multiply matrices i through j). The table has O(n²) entries. For each entry, we try all possible split points k from i to j-1 (O(n) choices). Total time = O(n³). The cost table m[i][j] and split table s[i][j] each require O(n²) space. Overall space = O(n²).

A live node in Branch and Bound is a node that has been generated (added to the search tree) but has not yet been processed - it has neither been expanded (branched upon) nor pruned (discarded). Live nodes are stored in the data structure (queue, stack, or priority queue) waiting to be selected for expansion. The choice of which live node to expand next determines the search strategy (FIFO, LIFO, or best-first).

For a minimization problem, the goal is to find the minimum cost solution. The current best upper bound (incumbent) is the cost of the best complete feasible solution found so far. A node is pruned if its lower bound ≥ current best upper bound, because no solution in that subtree can improve upon the current best. If lower bound < current best, the node may contain a better solution and must be explored.

The standard 2D DP table for 0/1 Knapsack has dimensions (n+1) × (W+1), giving O(nW) time and O(nW) space. However, since each row depends only on the previous row, space can be optimized to O(W) using a 1D array filled in reverse order. Both A and D are correct depending on whether the space-optimized version is used.

(A) TRUE: In the worst case (no pruning), backtracking explores all $2^n$ subsets of items - one include/exclude decision per item. (B) TRUE: A tight bounding function uses the fractional knapsack value of remaining items as an upper bound. If this upper bound plus the current value does not exceed the best known solution, the subtree is pruned. (C) TRUE: Backtracking is a complete algorithm - it will always find the optimal solution given enough time (since it explores all valid branches). (D) FALSE: 0/1 knapsack is NP-complete (no known polynomial algorithm). DP solves it in $O(nW)$ pseudo-polynomial time (polynomial in $n$ and $W$, but exponential in the input size when $W$ is large). Backtracking with memoization doesn't change this.

Branch and Bound can use different node selection strategies: FIFO (BFS order) explores nodes level by level and guarantees finding the shallowest solution first. LIFO (DFS order) uses less memory and finds feasible solutions quickly but may explore deeply before pruning. Best-first uses a priority queue ordered by bound values, exploring the most promising node first - typically yielding fewer nodes expanded. All three are valid strategies; best-first generally gives the best pruning.

For the 4-Queens problem, backtracking places queens row by row. Starting with column 1 in row 1: Row 1, Col 1: place queen. Row 2: Col 1 (same col) ✗, Col 2 (diagonal) ✗, Col 3: place queen (node 3). Row 3: Col 1 (diagonal) ✗, Col 2 ✗, Col 3 (same col) ✗, Col 4 ✗: backtrack. Row 2, Col 4: place queen (node 5). Row 3: Col 1 ✗, Col 2: place queen (node 6). Row 4: Col 1 ✗, Col 2 (same col) ✗, Col 3 ✗, Col 4 (diagonal) ✗: backtrack. Row 3, Col 3 (same col as row 2 col 4?) No - Row 3 Col 3 vs Row 2 Col 4: diagonal. ✗. Row 3, Col 4 (same col as row 2 col 4) ✗. Backtrack to row 1. Row 1 Col 2: place queen. Row 2 Col 4: place queen (node 8). Row 3 Col 1: place queen. Row 4 Col 3: place queen. First solution found! Total nodes explored $= \mathbf{8}$.

One LCS is "BCAB" with length 4. Fill the DP table: matching characters extend diagonal, else take max of left/top.

A: Both paradigms decompose problems into smaller subproblems. C: DP uses memoization/tabulation to reuse subproblem results; Divide & Conquer solves non-overlapping subproblems independently without caching. D: Merge Sort divides the array into halves (non-overlapping subproblems) - classic Divide & Conquer. B is FALSE - it is exactly REVERSED: in DP, subproblems overlap (that's why caching helps); in Divide & Conquer, subproblems are disjoint.

(A) TRUE: The N-Queens problem is the canonical backtracking problem - place $N$ queens with constraint checking at each step. (B) TRUE: Finding a Hamiltonian cycle uses backtracking - try adding vertices to the path one by one, backtrack if a vertex is already visited or the last vertex cannot connect back to the start. (C) FALSE: Huffman encoding uses a greedy algorithm (always merge the two lowest-frequency nodes) - backtracking is not involved. (D) TRUE: Sudoku is a constraint satisfaction problem solved with backtracking - try digits 1-9 in each empty cell, backtrack when a conflict arises.

Matrix Chain Multiplication uses DP to find the optimal parenthesization - it has overlapping subproblems and optimal substructure. Coin Change (minimum coins) uses DP: dp[i] = min coins needed for amount i. Fractional Knapsack is solved greedily (sort by value/weight ratio). Activity Selection is solved greedily (select activity finishing earliest). So A and C use DP.

The LCS of X = 'ABCBDAB' and Y = 'BDCAB' is 'BCAB' or 'BDAB', both of length 4. The DP recurrence is: LCS[i][j] = LCS[i-1][j-1] + 1 if X[i] == Y[j], else max(LCS[i-1][j], LCS[i][j-1]). Filling the table for these strings yields a maximum LCS length of 4.

At each node in 0/1 Knapsack B&B: A: The upper bound is computed using fractional knapsack on remaining items given current remaining capacity - this is the key bounding step. B: Feasibility is checked - if adding the current item exceeds capacity, the include-branch is infeasible and immediately pruned. C: Branching creates two children - include the next item (if feasible) and exclude the next item. D: Items are sorted once before B&B begins (by v/w ratio) and this order is fixed throughout - no resorting at each node.

Build DP table. With capacity 7: Take item 2 (w=2, v=6) and item 3 (w=3, v=10): total weight=5, value=16. Add item 1 (w=1, v=1): total weight=6, value=17. Or take item 3 (w=3,v=10) + item 4(w=5 - too heavy with 3: 3+5=8>7). Take item 2(w=2,v=6) + item 4(w=5,v=16): weight=7, value=22. Take item 1+2+3: weight=6, value=17. Maximum = 22 (items 2 and 4).

Option 1: (A₁A₂)A₃ = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500. Option 2: A₁(A₂A₃) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000. Minimum = 4500, achieved by parenthesization (A₁A₂)A₃.

Floyd-Warshall uses three nested loops over all vertices → O(n³).

In the worst case, the Hamiltonian cycle backtracking algorithm explores all permutations of vertices. At each step, up to $V-1$ choices exist for the next vertex. In a complete graph $K_V$, the pruning condition (adjacency check) never fires, and the algorithm explores all $(V-1)!$ possible orderings starting from a fixed vertex. This gives worst-case time complexity $O((V-1)!) = O(V!)$. No known polynomial-time algorithm exists for Hamiltonian cycle (it is NP-complete).

(A) TRUE: Forward checking propagates constraints immediately after each assignment, detecting failures earlier and reducing the search space. (B) TRUE: MRV heuristic (fail-first principle) selects the variable most likely to cause a failure early, avoiding wasted exploration of large subtrees. (C) TRUE: Arc Consistency (AC-3) enforces constraints between pairs of variables, shrinking domains and detecting inconsistencies before deeper search. (D) FALSE: Choosing the variable with the most remaining values (maximum) is the opposite of MRV - it delays constraint failures and leads to more wasted work, making backtracking less efficient.