Dynamic Programming – GATE CSE AlgorithmsPractice Questions & PYQs

The fractional knapsack is a relaxation of the 0/1 Knapsack - it removes the integrality constraint (items must be taken wholly or not at all) and allows taking fractions of items. Any 0/1 feasible solution is also a feasible fractional solution, so the fractional optimum ≥ the 0/1 optimum. This makes it a valid upper bound for the maximization 0/1 Knapsack. The fractional knapsack can be solved greedily in O(n log n), making bound computation efficient.

(A) TRUE: Backtracking uses DFS and checks feasibility (is the partial solution valid?). Branch and bound uses BFS, DFS, or best-first search and uses a bounding function that estimates the best achievable objective value, pruning branches that cannot beat the current best. (B) FALSE: Backtracking can also find all solutions or an optimal one - it is not limited to one solution. (C) TRUE: Branch and bound has a tighter pruning criterion (cost bound vs. current best), while backtracking prunes only based on constraint violations. (D) FALSE: It is the reverse - backtracking is used for feasibility/enumeration problems, while branch and bound is for optimisation problems.

In the worst case, N queens are placed across N rows with N, N-1, N-2, ... choices respectively, giving O(N!) node explorations.

Each element is either included or excluded, yielding 2^N possible subsets as leaf nodes.

Subsets of $\{1,2,3,4,5\}$ that sum to 5: $\{5\}$: $5 = 5$ ✓. $\{1, 4\}$: $1+4 = 5$ ✓. $\{2, 3\}$: $2+3 = 5$ ✓. $\{1, 2, 3\}$: $1+2+3 = 6$ ✗. No other subsets sum to 5 (checking all: $\{1,4\}, \{2,3\}, \{5\}$ are the only ones). Total $= \mathbf{3}$ distinct subsets. Backtracking explores the include/exclude binary tree and prunes when the partial sum exceeds 5 or the remaining elements cannot make up the deficit.

A path graph $P_n$ ($n \geq 2$) is bipartite - vertices can be split into two sets: odd-indexed $\{1,3,5,\ldots\}$ and even-indexed $\{2,4,6,\ldots\}$, with edges only between the two sets. A bipartite graph has chromatic number 2 (2-colourable). Assign colour $R$ to all odd-indexed vertices and colour $G$ to all even-indexed vertices - no two adjacent vertices share a colour. Hence $\chi(P_n) = \mathbf{2}$ for $n \geq 2$. For $n=1$, $\chi(P_1) = 1$.

(A) TRUE: Backtracking is a complete algorithm - it systematically explores all possibilities and will find a solution if one exists (it never misses a valid solution). (B) TRUE: Backtracking uses DFS - it goes deep into the tree before backtracking to explore sibling branches. (C) FALSE: Backtracking is not always better than brute force. In the worst case (no pruning occurs), backtracking degenerates to brute force. Its advantage depends on how effectively constraints prune the search space. (D) TRUE: Backtracking is a fundamental technique for CSPs like N-Queens, graph colouring, Sudoku, and constraint propagation.

In FIFO (BFS) Branch and Bound, nodes are explored level by level. The first complete feasible solution encountered is the one at the shallowest level in the search tree - it corresponds to the fewest branching decisions needed to reach a complete assignment. This is NOT necessarily the optimal solution (which is why B&B must continue until all live nodes are pruned or explored). LIFO (DFS) B&B tends to find a feasible solution faster (deeper first) but not necessarily the shallowest one.

0/1 Knapsack and Matrix Chain Multiplication exhibit optimal substructure and overlapping subproblems. Fractional Knapsack is solved by Greedy.

For a minimization ILP, the LP relaxation removes integrality constraints, making the feasible region larger (it contains all ILP-feasible points plus additional fractional points). A larger feasible region for minimization means the LP optimum ≤ ILP optimum - wait: relaxing constraints can only make the objective value better (lower for minimization). So LP relaxation optimum ≤ ILP optimum for minimization. This makes the LP value a valid lower bound. Option A states LP ≤ ILP which is correct for minimization - LP gives a lower bound.

Row minimums: Row1=min(10,8,9)=8, Row2=min(10,5,7)=5, Row3=min(8,5,6)=5, Row4=min(9,7,6)=6. Total row reduction = 8+5+5+6 = 24. After subtracting row minimums: Row1=[∞,2,0,1], Row2=[5,∞,0,2], Row3=[3,0,∞,1], Row4=[3,1,0,∞]. Column minimums of reduced matrix: Col1=min(∞,5,3,3)=3, Col2=min(2,∞,0,1)=0, Col3=min(0,0,∞,0)=0, Col4=min(1,2,1,∞)=1. Column reduction = 3+0+0+1=4. Total lower bound = 24+4 = 28. But question asks only for row reduction = 24.

For the Assignment Problem in Branch and Bound, the cost matrix is reduced by subtracting the minimum of each row (row reduction) and then the minimum of each column (column reduction). The sum of all reductions gives a valid lower bound on the total assignment cost. This is equivalent to the first step of the Hungarian algorithm and provides a tight lower bound. Branching is done by fixing or excluding specific worker-job assignments.

In Floyd-Warshall, D^(k)[i][j] represents the length of the shortest path from vertex i to vertex j where all intermediate vertices on the path are drawn from the set {1, 2, ..., k}. When k = 0, D^(0)[i][j] = direct edge weight. When k = n, D^(n)[i][j] is the true shortest path using any intermediate vertices.

The incumbent solution in Branch and Bound is the best complete feasible solution discovered so far during the search process. It serves as the current upper bound (for maximization) or lower bound (for minimization) on the optimal objective value. Whenever a new complete feasible solution better than the incumbent is found, the incumbent is updated. The incumbent is used to prune nodes whose bounds cannot improve upon it, making it central to the efficiency of Branch and Bound.

For generating permutations of $n$ elements: Level 0 (root): 1 node. Level 1: $n$ nodes. Level 2: $n(n-1)$ nodes. ... Level $k$: $n!/(n-k)!$ nodes. Total nodes $= \sum_{k=0}^{n} \frac{n!}{(n-k)!} = \sum_{j=0}^{n} \frac{n!}{j!}$. For $n=3$: $1 + 3 + 6 + 6 = 16$ nodes. For $n=4$: $1 + 4 + 12 + 24 + 24 = 65$ nodes. The formula is $\lfloor e \cdot n! \rfloor$ approximately (by Taylor series of $e$).

Backtracking explores the solution space using a depth-first search (DFS) strategy. At each step, it makes a choice and recursively explores further. If the current partial solution violates the problem's constraints (a condition checked by a pruning/bounding function), it backtracks - undoes the last choice and tries the next alternative. This avoids exploring entire subtrees that cannot lead to valid solutions, making it more efficient than brute-force enumeration.

A: Correct - this is the definition of optimal substructure. B: Correct - optimal substructure enables memoization/tabulation. C: FALSE - the longest simple path in a general graph does NOT have optimal substructure (it has overlapping subproblems but no consistent optimal substructure). D: Correct - shortest paths have optimal substructure (a subpath of a shortest path is itself a shortest path), but longest simple paths do not because choosing the longest subpath may conflict with other subpaths sharing vertices.

If the optimal solution is at the boundary, a poorly chosen bounding function might lead the algorithm to prematurely prune branches containing the optimal solution.

The $\texttt{unassign(k, c)}$ step is the backtracking step itself. After exploring the subtree rooted at choice $c$ for position $k$, the algorithm must undo the assignment before trying the next choice $c'$. Without $\texttt{unassign}$, the state would remain modified and subsequent choices would be evaluated incorrectly - the algorithm would not properly explore alternative branches. This undo/redo mechanism (also called the restore step) is the defining characteristic of backtracking.

The bounding (or pruning) function checks feasibility of a partial candidate; if it fails, the subtree is pruned.