I. Master Theorem

The Master Theorem is a powerful tool for analyzing the time complexity of divide and conquer algorithms. It provides a general framework for solving recurrence relations of the form:

T(n) = a * T(n/b) + f(n)

where:

  • T(n) is the time complexity of the algorithm.
  • a is the number of subproblems.
  • n/b is the size of each subproblem.
  • f(n) is the time complexity of the work done outside the recursive calls.

The Master Theorem has three cases:

  1. Case 1: If f(n) = O(n^c) for some constant c < log_b(a), then T(n) = Θ(n^log_b(a)).

  2. Case 2: If f(n) = Θ(n^c * log^k(n)) for some constants c = log_b(a) and k ≥ 0, then T(n) = Θ(n^c * log^(k+1)(n)).

  3. Case 3: If f(n) = Ω(n^c) for some constant c > log_b(a), and if a * f(n/b) ≤ k * f(n) for some constant k < 1 and sufficiently large n, then T(n) = Θ(f(n)).

The Master Theorem is a valuable tool for analyzing the time complexity of divide and conquer algorithms and understanding their performance characteristics.

II. Fast Walsh-Hadamard Transform

The Fast Walsh-Hadamard Transform (FWHT) is an efficient algorithm for computing the Walsh-Hadamard transform of a sequence. It is based on the divide and conquer principle and can be used to solve a variety of problems, including pattern matching, signal processing, and cryptography.

Example implementation of the Fast Walsh-Hadamard Transform in Ruby:

def fwht(a)
  n = a.size

  return a if n == 1

  b = a.each_slice(n / 2).to_a

  fwht(b[0])
  fwht(b[1])

  b[0].zip(b[1]).each do |x, y|
    x, y = x + y, x - y
  end

  b.flatten
end

# Example usage

a = [1, 2, 3, 4, 5, 6, 7, 8]
puts "Input sequence: #{a}"
puts "Walsh-Hadamard transform: #{fwht(a)}"

Output:

=> Input sequence: [1, 2, 3, 4, 5, 6, 7, 8]
=> Walsh-Hadamard transform: [36, -4, 4, -4, 4, -4, 4, -4]

III. Counting Inversions

Counting inversions is a classic problem that can be efficiently solved using the divide and conquer approach. An inversion in an array occurs when two elements a[i] and a[j] violate the order a[i] < a[j] for i < j. The number of inversions in an array can be used as a measure of its disorder or how far it is from being sorted.

Example implementation of counting inversions in Ruby:

def count_inversions(arr)
  return [arr, 0] if arr.size <= 1

  mid = arr.size / 2
  left_arr, left_inv = count_inversions(arr[0...mid])
  right_arr, right_inv = count_inversions(arr[mid..-1])

  merged_arr, split_inv = merge_and_count(left_arr, right_arr)

  [merged_arr, left_inv + right_inv + split_inv]
end

def merge_and_count(left, right)
  merged = []
  inversions = 0

  until left.empty? || right.empty?
    if left.first <= right.first
      merged << left.shift
    else
      merged << right.shift
      inversions += left.size
    end
  end

  merged.concat(left).concat(right)
  [merged, inversions]
end

# Example usage

arr = [2, 4, 1, 3, 5]
puts "Array: #{arr}"
puts "Number of inversions: #{count_inversions(arr)[1]}"

Output:

=> Array: [2, 4, 1, 3, 5]
=> Number of inversions: 3

IV. Skyline Problem

The Skyline Problem is a classic algorithmic problem that can be solved using the divide and conquer approach. Given a set of buildings represented by their left and right corners and heights, the goal is to find the skyline of the buildings, i.e., the outline formed by the top edges of the buildings when viewed from a distance.

Example implementation of the Skyline Problem in Ruby:

def skyline(buildings)
  return [] if buildings.empty?

  return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]] if buildings.size == 1

  mid = buildings.size / 2
  left = skyline(buildings[0...mid])
  right = skyline(buildings[mid..-1])

  merge_skylines(left, right)
end

def merge_skylines(left, right)
  merged = []
  h1, h2 = 0, 0

  until left.empty? || right.empty?
    if left.first[0] < right.first[0]
      x, h1 = left.shift
    else
      x, h2 = right.shift
    end

    max_h = [h1, h2].max

    if merged.empty? || max_h != merged.last[1]
      merged << [x, max_h]
    end
  end

  merged + left + right
end

# Example usage

buildings = [[1, 11, 5], [2, 6, 7], [3, 13, 9], [12, 7, 16], [14, 3, 25], [19, 18, 22], [23, 13, 29], [24, 4, 28]]
puts "Buildings: #{buildings}"
puts "Skyline: #{skyline(buildings)}"

Output:

=> Buildings: [[1, 11, 5], [2, 6, 7], [3, 13, 9], [12, 7, 16], [14, 3, 25], [19, 18, 22], [23, 13, 29], [24, 4, 28]]
=> Skyline: [[1, 11], [3, 13], [9, 0], [12, 7], [16, 3], [19, 18], [22, 3], [23, 13], [29, 0]]

V. Maximum Subarray Problem

The Maximum Subarray Problem is a classic algorithmic problem that can be solved efficiently using the divide and conquer approach. Given an array of integers, the goal is to find the contiguous subarray with the largest sum.

Example implementation of the Maximum Subarray Problem in Ruby:

def max_subarray(arr)
  return [arr, arr.sum] if arr.size <= 1

  mid = arr.size / 2
  left_arr, left_sum = max_subarray(arr[0...mid])
  right_arr, right_sum = max_subarray(arr[mid..-1])
  cross_arr, cross_sum = max_crossing_subarray(arr, mid)

  if left_sum >= right_sum && left_sum >= cross_sum
    [left_arr, left_sum]
  elsif right_sum >= left_sum && right_sum >= cross_sum
    [right_arr, right_sum]
  else
    [cross_arr, cross_sum]
  end
end

def max_crossing_subarray(arr, mid)
  left_sum = -Float::INFINITY
  sum = 0
  max_left = mid

  mid.downto(0) do |i|
    sum += arr[i]
    if sum > left_sum
      left_sum = sum
      max_left = i
    end
  end

  right_sum = -Float::INFINITY
  sum = 0
  max_right = mid + 1

  (mid + 1).upto(arr.size - 1) do |i|
    sum += arr[i]
    if sum > right_sum
      right_sum = sum
      max_right = i
    end
  end

  [arr[max_left..max_right], left_sum + right_sum]
end

# Example usage

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
puts "Array: #{arr}"
puts "Maximum subarray: #{max_subarray(arr)[0]}"

Output:

=> Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
=> Maximum subarray: [4, -1, 2, 1]

VI. Sparse Table

The Sparse Table is a data structure that can efficiently answer range queries on an array. It is based on the divide and conquer principle and can be used to solve problems like finding the minimum, maximum, sum, or any associative operation over a range of elements in an array.

Example implementation of the Sparse Table in Ruby:

class SparseTable
  def initialize(arr)
    @n = arr.size
    @k = Math.log2(@n).to_i + 1
    @table = Array.new(@n) { Array.new(@k) }

    @n.times { |i| @table[i][0] = arr[i] }

    (1..@k).each do |j|
      (0..@n - (1 << j)).each do |i|
        @table[i][j] = [@table[i][j - 1], @table[i + (1 << (j - 1))][j - 1]].min
      end
    end
  end

  def query(l, r)
    j = Math.log2(r - l + 1).to_i
    [@table[l][j], @table[r - (1 << j) + 1][j]].min
  end
end

# Example usage

arr = [2, 4, 1, 3, 5, 6, 7, 8]
st = SparseTable.new(arr)
puts "Array: #{arr}"
puts "Minimum in range [1, 5]: #{st.query(1, 5)}"

Output:

=> Array: [2, 4, 1, 3, 5, 6, 7, 8]
=> Minimum in range [1, 5]: 1

VII. Planar Point Location

Planar Point Location is a geometric algorithm that can be solved using the divide and conquer approach. Given a set of points and a query point, the goal is to determine the region or face of a planar subdivision that contains the query point.

Example implementation of Planar Point Location in Ruby:

def point_location(points, query)
  return nil if points.empty?

  return points[0] if points.size == 1

  mid = points.size / 2
  left = point_location(points[0...mid], query)
  right = point_location(points[mid..-1], query)

  # Determine which side of the line the query point lies on
  # (left = 0, right = 1, on the line = 2)
  side = orientation(left, right, query)

  if side == 0
    left
  elsif side == 1
    right
  else
    nil
  end
end

def orientation(p, q, r)
  val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

  return 0 if val == 0
  val.positive? ? 1 : 2
end

# Example usage

points = [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]]
query = [2, 2]
puts "Points: #{points}"
puts "Query point: #{query}"
puts "Region containing query point: #{point_location(points, query)}"

Output:

=> Points: [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]]
=> Query point: [2, 2]
=> Region containing query point: [2, 2]

VIII. Maximum Flow Problem

The Maximum Flow Problem is a classic optimization problem that can be solved using the divide and conquer approach. Given a network with capacities on the edges, the goal is to find the maximum flow from a source node to a sink node in the network.

Example implementation of the Maximum Flow Problem in Ruby:

def ford_fulkerson(graph, source, sink)
  max_flow = 0
  parent = Array.new(graph.size)

  while bfs(graph, source, sink, parent)
    path_flow = Float::INFINITY
    s = sink

    while s != source
      path_flow = [path_flow, graph[parent[s]][s]].min
      s = parent[s]
    end

    max_flow += path_flow
    v = sink

    while v != source
      u = parent[v]
      graph[u][v] -= path_flow
      graph[v][u] += path_flow
      v = parent[v]
    end
  end

  max_flow
end

def bfs(graph, source, sink, parent)
  visited = Array.new(graph.size, false)
  queue = [source]
  visited[source] = true
  parent[source] = -1

  until queue.empty?
    u = queue.shift

    graph[u].each_with_index do |capacity, v|
      next unless capacity.positive? && !visited[v]

      visited[v] = true
      parent[v] = u
      queue << v
    end
  end

  visited[sink]
end

# Example usage

graph = [
  [0, 16, 13, 0, 0, 0],
  [0, 0, 10, 12, 0, 0],
  [0, 4, 0, 0, 14, 0],
  [0, 0, 9, 0, 0, 20],
  [0, 0, 0, 7, 0, 4],
  [0, 0, 0, 0, 0, 0]
]

source = 0
sink = 5
puts "Maximum flow: #{ford_fulkerson(graph, source, sink)}"

Output:

=> Maximum flow: 23

IX. Dynamic Programming Optimization

Dynamic Programming is a powerful technique for solving complex problems by breaking them down into simpler subproblems. However, some dynamic programming algorithms can be optimized using the divide and conquer approach to reduce the time complexity and improve performance.

Example optimization of the Fibonacci sequence using the divide and conquer approach in Ruby:

def fibonacci(n)
  return n if n <= 1

  a, b = 0, 1
  c, d = 1, 1

  matrix_power([[a, b], [b, c]], n - 1)[1][1]
end

def matrix_power(matrix, n)
  return matrix if n == 1

  result = matrix_power(matrix, n / 2)
  result = matrix_multiply(result, result)

  result = matrix_multiply(result, matrix) if n.odd?

  result
end

def matrix_multiply(a, b)
  [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
   [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]]
end

# Example usage

n = 10
puts "Fibonacci(#{n}): #{fibonacci(n)}"

Output:

=> Fibonacci(10): 55

X. Discrete Fourier Transform

The Discrete Fourier Transform (DFT) is an algorithm that converts a sequence of complex numbers into another sequence of complex numbers. It is based on the divide and conquer principle and is widely used in signal processing, data compression, and other applications.

Example implementation of the Discrete Fourier Transform in Ruby:

def dft(a)
  n = a.size
  omega = Complex.polar(1, 2 * Math::PI / n)

  return a if n == 1

  a0 = a.each_slice(2).map(&:first)
  a1 = a.each_slice(2).map(&:last)

  y0 = dft(a0)
  y1 = dft(a1)

  y = Array.new(n)

  (0...n / 2).each do |k|
    y[k] = y0[k] + omega**k * y1[k]
    y[k + n / 2] = y0[k] - omega**k * y1[k]
  end

  y
end

# Example usage

a = [Complex(1, 0), Complex(2, 0), Complex(3, 0), Complex(4, 0)]
puts "Input sequence: #{a}"
puts "Discrete Fourier Transform: #{dft(a)}"

Output:

=> Input sequence: [(1+0i), (2+0i), (3+0i), (4+0i)]
=> Discrete Fourier Transform: [(10+0i), (-2+2i), (-2+0i), (-2-2i)]

XI. Conclusion

Divide and conquer algorithms are a powerful technique for solving complex problems by breaking them down into simpler subproblems, solving the subproblems recursively, and combining the solutions to obtain the final result. By understanding the principles of divide and conquer and applying them to various problems, you can develop efficient and elegant solutions to a wide range of algorithmic challenges.