Module II — Divide and Conquer Algorithms and Graph Search

Course: MAT5EJ302(1) — Data Structures and Algorithms
Hours: 12 | Textbook Sections: 2.1, 2.2, 2.3, 3.1–3.3 (Dasgupta et al.)

1. The Divide and Conquer Paradigm

Many efficient algorithms follow a three-step template:

1. Divide: Break the input into smaller subproblems of the same type.
2. Conquer: Solve each subproblem recursively. (Base case: when the input is small enough, solve directly.)
3. Combine: Merge the subproblem solutions into a solution for the original problem.

The power of this approach comes from the fact that a problem of size $n$ is often solvable by combining solutions to problems of size $n/2$, leading to running times like $O(n \log n)$ rather than $O(n^2)$.

2. Fast Integer Multiplication (Karatsuba’s Algorithm)

2.1 The Baseline: Grade-School Multiplication

For two $n$-bit integers $x$ and $y$, grade-school multiplication requires $O(n^2)$ bit operations (as shown in Module I). Can we do better?

2.2 A First Attempt

Split $x$ and $y$ at the halfway point:

x = x_L · 2^(n/2) + x_R      [left and right halves of x]
y = y_L · 2^(n/2) + y_R

Then:

x · y = (x_L · 2^(n/2) + x_R)(y_L · 2^(n/2) + y_R)
      = x_L · y_L · 2^n  +  (x_L · y_R + x_R · y_L) · 2^(n/2)  +  x_R · y_R

This requires 4 multiplications of $(n/2)$-bit numbers, giving recurrence:

T(n) = 4T(n/2) + O(n)

By the Master Theorem (see Section 3), this gives $T(n) = O(n^2)$ — no improvement!

2.3 Karatsuba’s Trick

Observe that $x_L \cdot y_R + x_R \cdot y_L$ can be computed with just one extra multiplication:

(x_L + x_R)(y_L + y_R) = x_L·y_L + x_L·y_R + x_R·y_L + x_R·y_R

So:

x_L·y_R + x_R·y_L = (x_L + x_R)(y_L + y_R) - x_L·y_L - x_R·y_R

We already compute $x_L \cdot y_L$ and $x_R \cdot y_R$. So we only need 3 multiplications total:

Algorithm: Karatsuba(x, y)
  n = max(bits of x, bits of y)
  if n = 1: return x · y        [base case]
  
  Split: x_L = x >> n/2, x_R = x mod 2^(n/2)
         y_L = y >> n/2, y_R = y mod 2^(n/2)
  
  p = Karatsuba(x_L, y_L)
  q = Karatsuba(x_R, y_R)
  r = Karatsuba(x_L + x_R, y_L + y_R)
  
  return p · 2^n + (r - p - q) · 2^(n/2) + q

Recurrence:

T(n) = 3T(n/2) + O(n)

By the Master Theorem: $T(n) = O(n^{\log_2 3}) = O(n^{1.585})$.

This is a significant improvement over $O(n^2)$ for large $n$. Modern fast multiplication algorithms achieve even better — $O(n \log n \log\log n)$ — but Karatsuba’s is the easiest to understand.

3. Solving Recurrence Relations

Many divide-and-conquer algorithms lead to recurrences of the form:

T(n) = aT(n/b) + O(nᵈ)

where:

• $a$ = number of subproblems
• $n/b$ = size of each subproblem
• $O(n^d)$ = work done outside recursive calls

3.1 The Master Theorem

Theorem: For $T(n) = aT(n/b) + O(n^d)$ with $a \geq 1$, $b > 1$, $d \geq 0$:

Intuition: Think about the recursion tree.

• At level $k$ ($k$ levels deep), there are $a^k$ subproblems, each of size $n/b^k$, each doing $(n/b^k)^d$ work.
• Work at level $k$ = $a^k \cdot (n/b^k)^d = n^d \cdot (a/b^d)^k$.
• This is a geometric series with ratio $a/b^d$.
  • If $a/b^d < 1$: the first level dominates → $O(n^d)$.
  • If $a/b^d = 1$: all levels equal → $\log n$ levels × $n^d$ each → $O(n^d \log n)$.
  • If $a/b^d > 1$: the deepest level dominates → $O(n^{\log_b a})$.

3.2 Worked Examples

Example 1: Merge sort: $T(n) = 2T(n/2) + O(n)$

• $a = 2$, $b = 2$, $d = 1$. Check: $\log_2 2 = 1 = d$. Case 2 → $T(n) = O(n \log n)$.

Example 2: Binary search: $T(n) = T(n/2) + O(1)$

• $a = 1$, $b = 2$, $d = 0$. Check: $\log_2 1 = 0 = d$. Case 2 → $T(n) = O(\log n)$.

Example 3: Karatsuba: $T(n) = 3T(n/2) + O(n)$

• $a = 3$, $b = 2$, $d = 1$. Check: $\log_2 3 \approx 1.585 > 1 = d$. Case 3 → $T(n) = O(n^{\log_2 3}) = O(n^{1.585})$.

Example 4: Naive 4-subproblem split: $T(n) = 4T(n/2) + O(n)$

• $a = 4$, $b = 2$, $d = 1$. Check: $\log_2 4 = 2 > 1 = d$. Case 3 → $T(n) = O(n^2)$.

4. Binary Search

Problem: Given a sorted array $A[1..n]$ and a target value $v$, find the index of $v$ in $A$ (or report that it is absent).

4.1 Algorithm

Algorithm: BinarySearch(A, v, lo, hi)
  if lo > hi: return NOT FOUND
  mid = (lo + hi) / 2
  if A[mid] = v: return mid
  if A[mid] > v: return BinarySearch(A, v, lo, mid - 1)
  else:          return BinarySearch(A, v, mid + 1, hi)

Call initially as BinarySearch(A, v, 1, n).

4.2 Why It Works

The key invariant: at every call, if $v$ exists in $A$, then $v \in A[\text{lo}..\text{hi}]$.

• Initially this is trivially true ($\text{lo}=1$, $\text{hi}=n$).
• At each step, we compare $v$ with $A[\text{mid}]$ and narrow the search range by half.
• The invariant is preserved throughout.
• The range shrinks by half each step, so we terminate in $O(\log n)$ steps.

4.3 Worked Example

Search for $v = 23$ in $A = [2, 5, 8, 12, 16, 23, 38, 56]$:

Step 1: lo=1, hi=8, mid=4, A[4]=12. 23 > 12 → search right half.
Step 2: lo=5, hi=8, mid=6, A[6]=23. Found at index 6!

Time complexity: $T(n) = T(n/2) + O(1)$ → $O(\log n)$.

5. Merge Sort

Problem: Sort an array $A[1..n]$ of $n$ numbers.

5.1 Algorithm

Algorithm: MergeSort(A, lo, hi)
  if lo ≥ hi: return          [base case: single element or empty]
  mid = (lo + hi) / 2
  MergeSort(A, lo, mid)        [sort left half]
  MergeSort(A, mid+1, hi)      [sort right half]
  Merge(A, lo, mid, hi)        [merge the two sorted halves]

Algorithm: Merge(A, lo, mid, hi)
  L = A[lo..mid], R = A[mid+1..hi]    [copy the two halves]
  i = 1, j = 1, k = lo
  while i ≤ len(L) and j ≤ len(R):
      if L[i] ≤ R[j]:
          A[k] = L[i]; i++
      else:
          A[k] = R[j]; j++
      k++
  copy remaining elements of L or R into A

5.2 Trace on Example

Sort $A = [5, 2, 8, 1, 9, 3]$:

Split: [5, 2, 8]       [1, 9, 3]
Split: [5] [2, 8]      [1] [9, 3]
Split:     [2] [8]          [9] [3]
Merge:     [2, 8]           [3, 9]
Merge: [2, 5, 8]       [1, 3, 9]
Merge: [1, 2, 3, 5, 8, 9]

5.3 Time Complexity

Merge sort divides into 2 halves and merges in $O(n)$ time:

T(n) = 2T(n/2) + O(n)   →   T(n) = O(n log n)

The Merge step visits each element once → $O(n)$. There are $\log n$ levels of recursion. Total work = $n \times \log n$ = $O(n \log n)$.

5.4 Comparison with Other Sorting Algorithms

Merge sort is optimal for comparison-based sorting: any comparison-based sort requires $\Omega(n \log n)$ comparisons in the worst case.

6. Graphs

6.1 What Is a Graph?

A graph $G = (V, E)$ consists of:

• A set of vertices (or nodes) $V$
• A set of edges $E$, where each edge connects two vertices

Types:

• Undirected graph: edges have no direction; ${u, v} = {v, u}$
• Directed graph (digraph): edges have direction; $(u, v) \neq (v, u)$
• Weighted graph: each edge has a numerical weight/cost

Basic terminology:

• Degree of a vertex $v$ = number of edges incident to $v$
• Path = sequence of distinct vertices connected by edges
• Cycle = path that starts and ends at the same vertex
• Connected graph = any two vertices are connected by some path
• Tree = connected undirected graph with no cycles (has $n-1$ edges for $n$ vertices)

6.2 Graph Representations

Two standard ways to store a graph in memory:

Adjacency Matrix

An $n \times n$ matrix $A$ where $A[i][j] = 1$ if there is an edge from $i$ to $j$, 0 otherwise (or the weight for weighted graphs).

Graph:  1-2, 1-3, 2-3, 3-4
Matrix:
      1  2  3  4
  1 [ 0  1  1  0 ]
  2 [ 1  0  1  0 ]
  3 [ 1  1  0  1 ]
  4 [ 0  0  1  0 ]

Space: $O(|V|^2)$ Check if edge $(u,v)$ exists: $O(1)$ Find all neighbours of $v$: $O(|V|)$

Adjacency List

For each vertex $v$, store the list of its neighbours.

1 → [2, 3]
2 → [1, 3]
3 → [1, 2, 4]
4 → [3]

Space: $O(|V| + |E|)$ Check if edge $(u,v)$ exists: $O(\text{degree}(u))$ Find all neighbours of $v$: $O(\text{degree}(v))$

Comparison

Most real-world graphs are sparse (social networks, road networks, web graphs), so adjacency lists are used more often.

7. Depth-First Search (DFS)

DFS is one of the most fundamental graph algorithms. It explores as deep as possible along each branch before backtracking.

7.1 DFS on Undirected Graphs

Algorithm: DFS(G)
  for each vertex v ∈ V:
      visited[v] = False
      pre[v] = post[v] = -1
  clock = 1
  for each vertex v ∈ V:
      if not visited[v]:
          Explore(G, v)

Algorithm: Explore(G, v)
  visited[v] = True
  pre[v] = clock; clock++
  for each edge (v, u) ∈ E:
      if not visited[u]:
          Explore(G, u)
  post[v] = clock; clock++

pre[v] = the time when $v$ is first visited (“pre-visit number”).
post[v] = the time when $v$’s exploration is completed (“post-visit number”).

7.2 Trace Example — Undirected Graph

Graph: vertices ${A, B, C, D, E}$, edges ${A\text{-}B, A\text{-}C, B\text{-}D, C\text{-}D, D\text{-}E}$

Starting DFS from A:

Visit A (pre=1)
  Visit B (pre=2)
    Visit D (pre=3)
      Visit C (pre=4)
        C's unvisited neighbour: none (A visited, D visited)
      post[C] = 5
      Visit E (pre=6)
      post[E] = 7
    post[D] = 8
  post[B] = 9
post[A] = 10

Pre-order: $A(1), B(2), D(3), C(4), E(6)$ Post-order (completion): $C(5), E(7), D(8), B(9), A(10)$

7.3 DFS on Directed Graphs

The same algorithm applies. For directed graphs, we distinguish edge types based on the DFS tree structure:

Important property: A directed graph has a cycle $\leftrightarrow$ DFS finds a back edge.

7.4 Applications of DFS

• Cycle detection: Look for back edges during DFS
• Topological sort: Order vertices so all edges go forward (post-order reversed)
• Connectivity: Check if all vertices are reachable from a source
• Strongly connected components: (covered in Module III)

8. Summary

9. Practice Problems

1. Apply the Master Theorem to solve:
   • a) $T(n) = 2T(n/4) + \sqrt{n}$
   • b) $T(n) = 2T(n/2) + n^2$
   • c) $T(n) = 4T(n/2) + n^2$
   • d) $T(n) = 8T(n/2) + n^2$

2. Trace Karatsuba’s algorithm on $x = 1234$, $y = 5678$ (use base 100 splitting: $x_L = 12$, $x_R = 34$, $y_L = 56$, $y_R = 78$).

3. Trace binary search for $v = 38$ in $A = [2, 5, 8, 12, 16, 23, 38, 56]$. Show each step.

4. Trace merge sort on $A = [3, 1, 4, 1, 5, 9, 2, 6]$. Show the recursion tree and all merge steps.

5. Prove that the lower bound for comparison-based sorting is $\Omega(n \log n)$. (Hint: count the number of leaves in a decision tree.)

6. For a graph with 5 vertices and edges ${(1,2),(1,3),(2,3),(3,4),(4,5),(5,1)}$: draw the adjacency matrix and adjacency list representations.

7. Run DFS on the directed graph: $V = {1,2,3,4}$, $E = {(1,2),(2,3),(3,1),(1,4)}$. Record pre and post times. Identify the back edge.

8. Show that in a DFS on an undirected graph, every edge is either a tree edge or a back edge (no forward or cross edges exist).

9. Explain why DFS runs in $O(

   V

   +

   E

   )$ time when using adjacency lists.

10. Challenge: Implement merge sort in Python and verify it gives the correct output for A = [9, 4, 7, 2, 5, 1, 8, 3, 6].