The Exam Blueprint: Module 3 PYQ Deep Analysis (2022–2024)

An analysis of 22 exam questions spanning 2022 to 2024 reveals that Module 3 is highly standardized. The questions revolve around three core pillars: Graph Traversals (BFS/DFS), Shortest Paths, and Minimum Spanning Trees (MST). A new addition in 2024 is the Ford-Fulkerson algorithm for Network Flow.

Complete PYQ Table (22 Questions)

Total marks tracked: 112 marks across 3 years.

---

Topic Heat Map

---

The Guaranteed Question Types

1. 🔴 Shortest Path Trace (7–14M) Appeared in ALL 3 years. You must know both Dijkstra’s (for graphs with positive weights) and Bellman-Ford (for negative weights/cycles). Examiners expect to see a step-by-step distance table.

2. 🔴 BFS vs DFS Comparison (7M) Highly predictable theory question. You must compare them across 4 dimensions: data structures used, memory complexity, traversal order, and specific applications.

3. 🟠 Prim's vs Kruskal's MST (7M) Either tracing the MST on a graph (2022) or writing the differences/pseudo-code (2023, 2024).

4. 🟡 Real-World Algorithm Selection (7M) A new trend started in 2024 (e.g., Q5b) where you are given a scenario (like Google Maps) and must justify which graph algorithm to use based on edge weights.

Solved Numericals: How to Structure Your Traces

---

Strategy 1: The Dijkstra Distance Table

When asked to trace Dijkstra's algorithm (e.g., 2022 Q4a, 2024 Q6b), do not just write the final shortest paths. Draw a table showing the relaxation of edges at each step.

Standard Table Format:

Key to scoring full marks: Always write the "parent node" in brackets next to the distance cost, e.g., 10 (A). This shows the exact path taken.

---

Strategy 2: Bellman-Ford Relaxation

Bellman-Ford requires relaxing ALL edges $|V| - 1$ times. If the graph has 5 vertices, you must show 4 Passes.

Pseudo-code for the trace:

1For i = 1 to 4:
2    For every edge (u, v) with weight w:
3        If D[u] + w < D[v]:
4            D[v] = D[u] + w

You must state: "After Pass 4, we run one more pass to check for negative weight cycles. If any distance updates, a negative cycle exists."

---

Numerical: Ford-Fulkerson Trace

"Find max flow from S to T. Capacities: S→A=10, S→C=10, A→B=4, A→C=2, C→D=9, B→T=10, D→B=6, D→T=10."

Step-by-step trace format required by examiners:

Path 1: S → A → B → T

• Bottleneck (min capacity): $\min(10, 4, 10) = 4$
• Update residual graph: Decrease forward edges by 4, increase backward edges by 4.
• Flow so far = 4

Path 2: S → C → D → T

• Bottleneck: $\min(10, 9, 10) = 9$
• Update residual graph.
• Flow so far = 4 + 9 = 13

Path 3: S → A → C → D → B → T

• Bottleneck: $\min(10-4=6, 2, 9-9=0 \text{ WAIT! C→D is full})$.
• We must find a valid path in the residual graph. C→D is 0 capacity left.
• Valid residual path: S → A → C ... (cannot go to D).
• Can we go D → C (backward edge)? No path to T from C without D.
• Wait, B has remaining capacity to T (10 - 4 = 6). D has remaining to B (6). D has remaining to T (10 - 9 = 1).
• Let's trace S → C → D → B → T: Bottleneck $\min(10-9=1, 9-9=0)$. S→C has 1 remaining. C→D has 0 remaining.
• Let's look at S → A → C ... C is blocked.

Conclusion format: "No more augmenting paths exist from S to T in the residual graph. Max Flow = sum of flows = 13."

(Note: Always draw the residual graph after each path update to guarantee full marks).

High-Yield Subjective Bank: Structure Your Answers

---

####Compare and contrast BFS and DFS (7 Marks)**

Answer structure (Table Format):

---

####Compare Prim’s and Kruskal’s algorithms (7 Marks)**

Answer structure:

1. Approach:
   • Prim's: Vertex-based. Starts at a root node and greedily grows the tree by selecting the cheapest edge connected to the current tree.
   • Kruskal's: Edge-based. Sorts all edges globally by weight and adds them to the forest one by one, skipping edges that form a cycle.
2. Data Structures:
   • Prim's: Uses a Priority Queue (Min-Heap) to find the minimum connected edge.
   • Kruskal's: Uses the Disjoint-Set (Union-Find) data structure to detect cycles.
3. Graph Suitability:
   • Prim's performs better on dense graphs (lots of edges). Time complexity: $O(E \log V)$.
   • Kruskal's performs better on sparse graphs. Time complexity: $O(E \log E)$.

---

####System Design: Shortest Paths on Google Maps (7 Marks)**

Given a city graph mapping, which algorithm to use?

1. (i) All roads have equal length:
   • Algorithm: BFS (Breadth-First Search).
   • Reasoning: When weights are equal (or 1), BFS inherently finds the shortest path without the overhead of maintaining a priority queue. It is the most efficient choice $O(V+E)$.
2. (ii) Roads have varying lengths, but no negative lengths:
   • Algorithm: Dijkstra's Algorithm.
   • Reasoning: Dijkstra is the standard for non-negative weighted graphs. It uses a greedy approach (priority queue) to efficiently find the shortest path in $O(E \log V)$ time.
3. (iii) Some roads have negative lengths:
   • Algorithm: Bellman-Ford Algorithm.
   • Reasoning: Dijkstra fails on negative weights because a previously finalized node's distance might decrease later. Bellman-Ford correctly handles negative weights by relaxing all edges $V-1$ times.