Dynamic Programming – GATE CSE AlgorithmsPractice Questions & PYQs

The current incumbent (best feasible solution) has cost 35. For minimization (TSP), a node is pruned if its lower bound ≥ current best = 35. Node with LB=30: 30 < 35, so NOT pruned - it may contain a tour better than 35. Node with LB=36: 36 ≥ 35, so PRUNED. Node with LB=35: 35 ≥ 35, so PRUNED (cannot improve strictly). Node with LB=20: 20 < 35, NOT pruned. Nodes B (LB=36) and C (LB=35) are pruned.

Branch and Bound is primarily used for combinatorial optimization problems, especially NP-hard problems such as the Travelling Salesman Problem (TSP), 0/1 Knapsack, Integer Linear Programming, and Job Scheduling. It systematically enumerates candidate solutions (branching) while using bounding functions to prune subspaces that cannot yield a better solution than the current best, making it more efficient than exhaustive search in practice.

Top-down DP (memoization) uses recursion and caches the result of each subproblem when first computed, solving subproblems only as needed. Bottom-up DP (tabulation) iteratively fills a table starting from base cases, solving all subproblems in a specific order. Top-down may skip unnecessary subproblems (advantage) but has recursion overhead. Bottom-up avoids recursion overhead but may solve unneeded subproblems.

At each of the n vertices, up to m color choices exist, giving a state-space tree of size O(m^n).

A tighter bound is one that is closer to the true optimal value of the subproblem. Tighter bounds leave less gap between the bound and the current incumbent, causing more nodes to satisfy the pruning condition (bound ≥ incumbent for minimization) and therefore more nodes to be pruned. Fewer nodes explored means faster computation. The trade-off is that tighter bounds are often more expensive to compute - the ideal bounding function balances tightness with computational cost. The algorithm remains exact regardless of bound tightness.

Tighter bounds don't guarantee fewer nodes explored. The shape of the search space and the specific problem structure also play a crucial role.

DP requires both optimal substructure and overlapping subproblems.

A: 0/1 Knapsack is a classic B&B application - branching on whether to include/exclude each item, bounding with fractional knapsack relaxation. B: TSP is solved with B&B using reduced cost matrix bounds (Little et al. algorithm) - the most well-known exact B&B application. D: ILP (Integer Linear Programming) is solved in practice using B&B with LP relaxation bounds - this is how solvers like CPLEX and Gurobi work. C: Single-source shortest path with non-negative weights is efficiently solved by Dijkstra's algorithm in polynomial time - no need for B&B.

In the worst case, Branch and Bound explores all nodes of the search tree without pruning any branches. For a problem with n binary variables, the search tree has 2ⁿ leaf nodes (complete assignments) and a total of O(2ⁿ) nodes. Without effective pruning, B&B degenerates to exhaustive enumeration. In practice, good bounding functions dramatically reduce the number of nodes explored, but the worst-case guarantee remains exponential for NP-hard problems (unless P=NP).

Items sorted by v/w ratio: Item1(10/2=5), Item2(10/4=2.5), Item3(12/6=2), Item4(18/9=2). Fractional knapsack with W=15: Take Item1 fully (w=2,v=10, remaining=13). Take Item2 fully (w=4,v=10, remaining=9). Take Item3 fully (w=6,v=12, remaining=3). Take 3/9 of Item4 (v=18×3/9=6). Total = 10+10+12+6 = 38. Upper bound = 38. Note: if all items fit: 10+10+12+18=50 but total weight=21>15. Correct UB=38.

The correctness guarantee of Branch and Bound rests on the admissibility of the bounding function. For minimization: the lower bound at any node must never exceed the true minimum achievable in that subtree (it must be optimistic/admissible). This ensures that a node is only pruned when it provably cannot contain the optimal solution. If the bound were too pessimistic (overestimating costs), it might prune nodes containing optimal solutions. Admissibility is the critical property - it is analogous to the admissibility condition in A* search.

The graph is a triangle ($K_3$) - all three vertices are mutually adjacent. Each vertex must receive a different colour from all others. Number of valid 3-colourings $=$ number of ways to assign 3 distinct colours to 3 vertices $= 3! = \mathbf{6}$. Explicitly: $(R,G,B), (R,B,G), (G,R,B), (G,B,R), (B,R,G), (B,G,R)$ - all 6 permutations of the 3 colours are valid since all vertices must be different colours.

Bellman-Ford DP: d^(k)[v] = shortest path from s to v using at most k edges. Base case: d^(0)[s] = 0 (source to itself costs 0), d^(0)[v] = ∞ for all other vertices (unreachable with 0 edges). Recurrence: d^(k)[v] = min(d^(k-1)[v] [don't use the k-th edge], min over all edges (u,v) of d^(k-1)[u] + w(u,v) [use edge (u,v) as the k-th edge]). After V-1 iterations, d^(V-1)[v] gives true shortest distances.

The edit distance between 'SUNDAY' (length 6) and 'SATURDAY' (length 8) is 3. Transformations: SUNDAY → STURDAY (replace U with T, replace N with R, insert A) - one optimal sequence is: insert A (SAUN DAY), insert T (SATUNDAY), replace U→R, replace N→D... The DP table gives a minimum of 3 operations.

The LCS DP table is of size (m+1) × (n+1), where LCS[i][j] represents the LCS of the first i characters of X and the first j characters of Y. The base cases are LCS[0][j] = 0 and LCS[i][0] = 0. So the total number of distinct subproblems is (m+1)(n+1), giving O(mn) time complexity.

The LIS of [3, 10, 2, 1, 20] is either [3, 10, 20] or [2, 20] or [1, 20]. The longest is [3, 10, 20] or [2, 20] - wait, [3, 10, 20] has length 3. The LIS DP: dp[0]=1(3), dp[1]=2(3,10), dp[2]=2(2 alone or 3 alone extended), dp[3]=1(1), dp[4]=3(3,10,20 or 2,20 giving 3→10→20). Maximum = 3.

(A) TRUE: Exhaustive search (brute force) visits all nodes. Backtracking prunes infeasible subtrees (constraint violations). Branch and bound further prunes suboptimal subtrees (using bounds). Each is a strictly stronger form of pruning. (B) FALSE: Backtracking is NOT strictly better in worst-case - on instances where no pruning occurs, backtracking degenerates to exhaustive search with the same worst-case complexity. (C) TRUE: Branch and bound extends backtracking by adding an optimality bounding function to prune subtrees that cannot yield a better solution than the current best - it inherits all of backtracking's feasibility pruning. (D) FALSE: Branch and bound can use best-first search (priority queue ordered by bound) rather than DFS, exploring the most promising nodes first. Exhaustive search and backtracking use DFS, but branch and bound is not restricted to it.

The 8-Queens problem has exactly 92 distinct solutions. This is a well-known result obtained by exhaustive backtracking search. If we consider solutions up to rotation and reflection (fundamental solutions), there are only 12. But counting all distinct arrangements (treating each rotation/reflection as different), the answer is 92. Backtracking with pruning (row, column, diagonal constraints) efficiently finds all 92 solutions by exploring only a small fraction of the $8^8 = 16,777,216$ brute-force possibilities.