Algorithms Q&A: MST, Knapsack, and Backtracking

Posted on Oct 5, 2026 in Computer Engineering

Q1. State Minimum Cost Spanning Trees Problem. Discuss Prim’s Algorithm to Solve This Problem and State Its Running Time.

Minimum Cost Spanning Tree (MCST/MST): Given a connected, weighted, undirected graph G = (V, E), a spanning tree connects all vertices using exactly |V| − 1 edges and contains no cycle. An MST is a spanning tree having minimum total edge weight: Cost(T) = Σ w(e), e ∈ T.

Prim’s Algorithm: A greedy algorithm that starts from any vertex and repeatedly adds the minimum-weight edge connecting a vertex already in the tree to a vertex outside it.

Algorithm:

  • Select starting vertex s.
  • Put s in MST.
  • Find the minimum-weight edge from MST to an unvisited vertex.
  • Add that edge and vertex.
  • Repeat until all V vertices are included.

Pseudocode:

Prim(G): choose s; key[s]=0; key[v]=∞ for others; MST=∅. While vertices remain: choose u with minimum key; add u to MST; for each adjacent v, if v ∉ MST and w(u,v) < key[v], set key[v]=w(u,v), parent[v]=u. Return MST.

Example: Edges AB = 1, AC = 4, BD = 2, CD = 3. Starting A: choose AB = 1, then BD = 2, then DC = 3. MST = {AB, BD, DC}; total cost = 1 + 2 + 3 = 6.

Running time:

  • Adjacency matrix: O(V²)
  • Binary heap + adjacency list: O(E log V)
  • Fibonacci heap: O(E + V log V)

Q2. State 0-1 Knapsack Problem and Describe How the Solution to This Problem Can Be Formulated Using Dynamic Programming. What Is Its Computational Behavior?

Problem: There are n items with weight wn and profit/value pn and knapsack capacity W. Maximize total profit subject to total weight ≤ W. In 0/1 knapsack each item is either selected (1) or not selected (0); it cannot be divided.

DP Formulation: Let DP[i][w] = maximum profit obtainable using the first i items with capacity w.

If wn > w: DP[i][w] = DP[i − 1][w]. Otherwise: DP[i][w] = max(DP[i − 1][w], pn + DP[i − 1][w − wn]). Initial conditions: DP[0][w] = 0 and DP[i][0] = 0.

Example: W = 5; items: (w, p) = (2, 12), (1, 10), (3, 20). Choosing items 1 + 3 gives weight 5 and profit 32, which is maximum. Thus optimal profit = 32.

Computational Behavior: Table has (n + 1)(W + 1) entries. Time = O(nW), space = O(nW). With 1-D optimization, space = O(W). O(nW) is pseudo-polynomial because it depends on numerical capacity W.

Q3. Demonstrate Branch-and-Bound Algorithm Design Technique Using 4-Queens Problem.

4-Queens: Place 4 queens on a 4 × 4 chessboard so that no two queens share the same row, column, or diagonal.

Branch-and-Bound: Branch by generating possible positions for the next queen. Bound/prune a node when the partial placement violates constraints or cannot lead to a feasible solution. Represent a state as [xn, xn, xn, xn], where xn is the column of the queen in row i.

Validity condition: For every pair i, j: xn ≠ xn and |xn − xn| ≠ |i − j|.

Example of pruning: From [1], [1, 1] is rejected because of the same column; [1, 2] is rejected because of a diagonal conflict; [1, 3] is valid and can be expanded. Continue branching and prune every invalid partial solution.

Valid solutions: [2, 4, 1, 3] and [3, 1, 4, 2]. For [2, 4, 1, 3], queens are at (1, 2), (2, 4), (3, 1), (4, 3), with no common row, column or diagonal.

Complexity: The search is exponential in general; for N-Queens, with one queen per row/column, the commonly stated worst-case search is O(N!). Branch-and-bound reduces practical work by pruning invalid branches.

Q4. Demonstrate the Search Strategy Used in Backtracking Algorithm Design Technique.

Backtracking: A systematic search technique that constructs a solution step-by-step and abandons a partial solution as soon as it becomes invalid. It performs depth-first search (DFS) on the state-space tree.

Strategy:

  • Start with an empty solution.
  • Select a candidate.
  • Test whether it is promising/valid.
  • If valid, recursively continue.
  • If invalid, reject/prune it.
  • If no candidate works, return to the previous decision and try another candidate.
  • Continue until a solution is found or all choices are exhausted.

4-Queens Example: Starting with [1], [1, 1] is invalid (same column), [1, 2] is invalid (diagonal), while [1, 3] is valid. If a later partial solution reaches a dead end, undo the last choice and try the next column. A complete valid solution is [2, 4, 1, 3].

Generic Pseudocode:

Backtrack(k): if solution complete → output; else for each possible choice x: if promising(x): add x; Backtrack(k+1); remove x ← backtrack.

Complexity: Backtracking generally has exponential worst-case complexity depending on the problem. For N-Queens, it is commonly expressed as O(N!) with pruning reducing the actual search.