Module IV — Greedy & Dynamic Programming Algorithms

Course: MAT5EJ302(1) — Data Structures and Algorithms
Hours: 12 | Textbook Sections: 5.1, 5.4, 6.1, 6.6 (Dasgupta et al.)

1. Greedy Algorithms — What and Why

A greedy algorithm builds a solution step by step, always making the locally optimal choice at each step — the choice that looks best right now — without reconsidering previous choices.

When does greedy work? Not always. Greedy fails for many problems (e.g., the 0-1 Knapsack problem). It works when the problem has:

1. Greedy choice property: The locally optimal choice is also globally optimal.
2. Optimal substructure: An optimal solution to the whole problem contains optimal solutions to subproblems.

For minimum spanning trees, greedy works beautifully — and we can prove it.

2. Minimum Spanning Trees

2.1 Definition

Given a connected undirected weighted graph $G = (V, E, w)$, a spanning tree $T$ is a subgraph that:

• Contains all $

  V

  $ vertices

• Is a tree (connected and acyclic, so has $

  V

  -1$ edges)

A minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

Example use cases: Minimum cost to connect cities with roads, lay cables to connect all buildings, etc.

Note: If all edge weights are distinct, the MST is unique. With equal weights, there may be multiple MSTs.

2.2 The Cut Property

This is the fundamental theorem that justifies greedy MST algorithms.

Definition: A cut is a partition of vertices into two non-empty sets $(S, V \setminus S)$. An edge crosses the cut if one endpoint is in $S$ and the other is in $V \setminus S$.

Theorem (Cut Property): Let $(S, V \setminus S)$ be any cut of $G$. Let $e$ be the minimum-weight edge crossing this cut. Then $e$ is in every MST of $G$ (assuming all edge weights are distinct; with equal weights, some MST contains $e$).

Proof: Let $T$ be any spanning tree. If $e \in T$, we are done. If $e \notin T$, we show we can swap in $e$ to get a lighter tree.

Since $T$ is a spanning tree, there is a unique path in $T$ between the two endpoints of $e$. This path must cross the cut (since one endpoint is in $S$ and the other in $V \setminus S$), so it contains some edge $e’$ that also crosses the cut.

Construct $T’ = T \cup {e} \setminus {e’}$. Since $e$ is the minimum-weight edge crossing the cut and $w(e) < w(e’)$ (or $w(e) \leq w(e’)$ if weights may be equal), $T’$ is a spanning tree with weight $\leq$ weight($T$).

So $T’$ is also an MST, and it contains $e$. $\blacksquare$

2.3 The Cycle Property (Complementary)

Theorem (Cycle Property): Let C be any cycle in G. Let e be the maximum-weight edge in C. Then e is in no MST (assuming distinct weights).

This is the dual of the cut property and justifies Kruskal’s approach.

3. Kruskal’s Algorithm

Kruskal’s algorithm builds the MST by greedily adding the cheapest safe edge at each step.

3.1 Algorithm

Algorithm: Kruskal(G)
  Sort all edges by weight: e₁, e₂, ..., e_m with w(e₁) ≤ w(e₂) ≤ ... ≤ w(eₘ)
  T = {}                             [start with empty edge set]
  for i = 1 to m:
      if adding eᵢ to T does not create a cycle:
          T = T ∪ {eᵢ}
  return T

Why it produces an MST: Each edge added is the minimum-weight edge crossing some cut (specifically, the cut separating the component containing $e_i$’s left endpoint from everything else). By the cut property, it belongs to some MST.

3.2 Worked Example

Graph: $V = {A, B, C, D, E}$ Edges (sorted by weight):

A-B: 1, C-D: 2, B-C: 3, A-D: 4, B-D: 5, B-E: 6, D-E: 7

Step 1: Add A-B (weight 1). T = {A-B}. Components: {A,B},{C},{D},{E}
Step 2: Add C-D (weight 2). T = {A-B, C-D}. Components: {A,B},{C,D},{E}
Step 3: Add B-C (weight 3). Connects {A,B} and {C,D}. T = {A-B, C-D, B-C}.
        Components: {A,B,C,D},{E}
Step 4: Skip A-D (weight 4). Would create cycle A-B-C-D-A.
Step 5: Skip B-D (weight 5). Would create cycle.
Step 6: Add B-E (weight 6). T = {A-B, C-D, B-C, B-E}.
        Components: {A,B,C,D,E}. All vertices connected → MST found!

MST edges: A-B, C-D, B-C, B-E. Total weight: 1+2+3+6 = 12.

3.3 Time Complexity

• Sorting edges: $O(E \log E)$
• Union-Find for cycle detection: $O(E \alpha(V)) \approx O(E)$ amortised
• Total: $O(E \log E)$ $= O(E \log V)$ since $E \leq V^2$.

4. Data Structure for Disjoint Sets (Union-Find)

Kruskal’s algorithm needs to efficiently:

• Check if two vertices are in the same component (same set)
• Merge two components (union)

4.1 The Problem

We maintain a collection of disjoint sets and support two operations:

• Find(x): return the representative (root) of the set containing x
• Union(x, y): merge the sets containing x and y

4.2 Naive Implementation

Each element points to its set representative. Find: $O(1)$. Union: $O(n)$ (update all elements). Too slow.

4.3 Forest Representation

Represent each set as a tree. The root is the representative.

• Find(x): follow parent pointers to the root
• Union(x, y): make one root point to the other

Without optimisations: A chain of $n$ Unions can make Find take $O(n)$.

4.4 Union by Rank

Always attach the smaller tree under the root of the larger tree (using “rank” as a proxy for height).

Algorithm: Union-by-Rank(x, y)
  rx = Find(x), ry = Find(y)
  if rank[rx] > rank[ry]: parent[ry] = rx
  elif rank[ry] > rank[rx]: parent[rx] = ry
  else: parent[ry] = rx; rank[rx]++

Result: Trees have height at most $O(\log n)$. Find takes $O(\log n)$.

4.5 Path Compression

When doing Find(x), make every node on the path directly point to the root.

Algorithm: Find-with-compression(x)
  if parent[x] ≠ x:
      parent[x] = Find(parent[x])   [recurse and compress]
  return parent[x]

4.6 Combined Complexity

Union by rank + path compression: both Union and Find take $O(\alpha(n))$ amortised time, where $\alpha$ is the inverse Ackermann function — a function that grows so slowly it is essentially constant ($\leq 4$ for all practical values of $n$).

5. Prim’s Algorithm

Prim’s algorithm is an alternative MST algorithm that grows a single tree from a starting vertex, adding the cheapest edge that expands the tree.

5.1 Algorithm

Algorithm: Prim(G, s)
  for each vertex v: key[v] = ∞, inMST[v] = False
  key[s] = 0
  PQ = priority queue of all vertices, keyed by key[]
  while PQ is not empty:
      u = ExtractMin(PQ)
      inMST[u] = True
      for each edge (u, v) with weight w:
          if not inMST[v] and w < key[v]:
              key[v] = w
              parent[v] = u
              UpdateKey(PQ, v, w)
  return {(parent[v], v) : v ≠ s, inMST[v]}

5.2 Comparison: Kruskal vs Prim

Both algorithms are correct by the cut property: each edge added is the minimum across some cut.

6. Dynamic Programming

6.1 What Is Dynamic Programming?

Dynamic programming (DP) solves problems by:

1. Breaking them into overlapping subproblems (same subproblems appear repeatedly)
2. Solving each subproblem exactly once
3. Storing the result (memoisation or tabulation)
4. Building up the final answer from smaller answers

DP differs from divide-and-conquer: in D&C, subproblems are independent. In DP, subproblems overlap.

Two approaches:

• Top-down (memoisation): Recursive with a cache. Compute as needed.
• Bottom-up (tabulation): Fill a table from smallest subproblems upward.

6.2 Optimal Substructure

For DP to work, the problem must have optimal substructure: an optimal solution to the whole problem contains optimal solutions to its subproblems.

Example: Shortest path from $s$ to $t$ passes through some vertex $v$. The subpaths $s \to v$ and $v \to t$ must each be shortest paths (otherwise we could find a better path through $v$, contradicting optimality).

6.3 DP on DAGs — Shortest Paths (revisited)

The shortest path problem on a DAG was solved in Module III using topological order. This is actually dynamic programming:

Let dist[v] = shortest path from s to v.

Recurrence:

dist[s] = 0
dist[v] = min over all edges (u,v): dist[u] + w(u,v)

Process vertices in topological order ensures all dist[u] values are computed before dist[v] needs them.

7. All-Pairs Shortest Paths

7.1 The Problem

Single-source shortest paths: Find shortest paths from one source to all others. → Dijkstra’s algorithm.

All-pairs shortest paths (APSP): Find shortest paths between every pair of vertices. Applications: network routing tables, distance matrices.

Naïve approach: Run Dijkstra’s from every vertex → $O(V(V+E) \log V)$. For dense graphs this is $O(V^3 \log V)$.

7.2 Floyd-Warshall Algorithm

Floyd-Warshall is a DP algorithm that solves APSP in $O(V^3)$ time, and also works with negative edge weights (as long as there are no negative cycles).

7.3 The DP Formulation

Number the vertices 1, 2, …, n.

Define: d[i][j][k] = shortest path from i to j using only vertices {1, 2, …, k} as intermediate vertices.

Base case: d[i][j][0] $= w(i,j)$ if edge $(i,j)$ exists, $\infty$ otherwise (0 if $i=j$).

Recurrence: Either the shortest path from i to j through {1,…,k} uses vertex k as an intermediate, or it doesn’t:

d[i][j][k] = min(d[i][j][k-1],  d[i][k][k-1] + d[k][j][k-1])
              \_________________/ \___________________________/
              doesn't use k        goes through k

Final answer: d[i][j][n] = shortest path from i to j through any intermediate vertices.

7.4 Space Optimisation

Note: d[i][j][k] depends only on d[...][...][k-1]. So we only need a 2D array, updating in-place:

Algorithm: Floyd-Warshall(G)
  Initialize: dist[i][j] = w(i,j) if edge exists, ∞ otherwise, dist[i][i] = 0
  for k = 1 to n:
      for i = 1 to n:
          for j = 1 to n:
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  return dist

Time complexity: $O(V^3)$ — three nested loops each of size $V$.
Space: $O(V^2)$ — the distance matrix.

7.5 Worked Example

Graph with 4 vertices, edges and weights:

1→2: 3, 1→4: 7, 2→1: 8, 2→3: 2, 3→1: 5, 3→4: 1, 4→2: 2

Initial distance matrix ($\infty$ = no direct edge):

     1    2    3    4
1 [  0    3    ∞    7 ]
2 [  8    0    2    ∞ ]
3 [  5    ∞    0    1 ]
4 [  ∞    2    ∞    0 ]

After $k=1$ (using vertex 1 as intermediate):

• $d[2][4]$: can go $2 \to 1 \to 4 = 8+7 = 15 < \infty$ → update to 15
• $d[3][4]$: $5+7=12 > 1$, no update
• (Other pairs don’t benefit from routing through 1)

     1    2    3    4
  1 [  0    3    ∞    7 ]
  2 [  8    0    2   15 ]
  3 [  5    8    0    1 ]  ← 3→1→2 = 5+3=8
  4 [  ∞    2    ∞    0 ]
  

After $k=2$ (vertex 2):

• $d[1][3]$: $1 \to 2 \to 3 = 3+2=5 < \infty$ → update
• $d[3][3]$: already 0
• $d[4][3]$: $4 \to 2 \to 3 = 2+2=4 < \infty$ → update
• …

Continue until $k=4$. Final matrix gives all-pairs shortest paths.

Detecting negative cycles: After Floyd-Warshall, if any dist[i][i] < 0, there is a negative cycle reachable from i.

7.6 Comparison: Dijkstra vs Floyd-Warshall for APSP

For dense graphs ($E \approx V^2$): Dijkstra gives $O(V^3 \log V)$, Floyd-Warshall gives $O(V^3)$ — Floyd-Warshall wins.
For sparse graphs ($E \approx V$): Dijkstra gives $O(V^2 \log V)$, Floyd-Warshall gives $O(V^3)$ — Dijkstra wins.

8. Summary

Key ideas:

• Greedy works for MST because of the cut property — locally optimal edge choices are globally optimal.
• DP handles overlapping subproblems by storing and reusing computed results.
• Floyd-Warshall is a classic DP algorithm: building from paths using 0 intermediates up to paths using all n vertices.

9. Practice Problems

1. Find the MST of the following graph using Kruskal’s algorithm: $V={1,2,3,4,5}$, Edges: 1-2:2, 1-3:6, 2-3:4, 2-4:5, 3-4:3, 3-5:7, 4-5:1. Show all steps.

2. Find the MST of the same graph using Prim’s algorithm (start from vertex 1). Compare the order in which edges are added.

3. Prove the Cut Property: the minimum-weight edge crossing any cut belongs to some MST.

4. Simulate the Union-Find structure (with union by rank and path compression) for the sequence: Union(1,2), Union(3,4), Union(5,6), Union(2,4), Find(1), Find(6), Union(4,6). Draw the forest after each operation.

5. Write out the recurrence for Floyd-Warshall and explain why the in-place update is valid.

6. Apply Floyd-Warshall to the graph: $V={1,2,3}$, edges: $1 \to 2$:1, $2 \to 3$:2, $1 \to 3$:10. Show the distance matrix after each value of $k$.

7. Can Floyd-Warshall detect negative cycles? Explain how.

8. Given a weighted DAG with vertices ${A, B, C, D, E}$ and edges $A \to B$:2, $A \to C$:4, $B \to C$:1, $B \to D$:7, $C \to D$:3, $C \to E$:6, $D \to E$:2, find all shortest paths from $A$ using the DP-on-DAG method.

9. True or False: Kruskal’s algorithm always adds the globally minimum-weight edge first. Justify.

10. Challenge: Show that if all edge weights in a connected graph are distinct, the MST is unique.

11. Why does Prim’s algorithm produce an MST? Give an informal argument using the cut property.

12. For a graph with V vertices and E edges, when would you prefer Prim’s over Kruskal’s? Give a specific example with complexity calculations.