Divide and Conquer Algorithms

Divide and Conquer Algorithm Design Strategy

• Divide the problem into smaller subproblems
• Solve the smaller subproblems recursively
• Combine the solutions of subproblems to obtain the solution to the original problem

Divide and Conquer Technique

• A problem of size n is divided into smaller subproblems of size n/2
• A solution to each subproblem is obtained recursively
• The solutions are combined to obtain the solution to the original problem

Control Abstraction for Divide and Conquer

• Algorithm DAndC(P)
  • If Small(P), return S(P)
  • Else:
    • Divide P into smaller instances P₁, P₂, ..., Pₖ (k ≥ 1)
    • Apply DAndC to each sub-problem
    • Return Combine(DAndC(P₁), DAndC(P₂), ..., DAndC(Pₖ))

General Divide-and-Conquer Recurrence

• For divide-and-conquer algorithms producing sub-problems of the same type:
  • A problem of size n can be divided into b instances of size n/b, with a of them needing to be solved.
  • a and b are constants, a ≥ 1 and b > 1.
  • The running time T(n) follows the recurrence:
    • T(n) = aT(n/b) + f(n) for n > 1
    • T(1) = c for n = 1, where c is a constant
  • n is a power of b, i.e., n = bᵏ
  • f(n) represents time spent on dividing the original problem into smaller ones and combining their solutions

Solving Recurrence Using Substitution Method

• Example using T(n) = 2T(n/2) + n with T(1) = 2 and f(n) = n
  • After k substitutions: T(n) = 2ᵏT(n/2ᵏ) + n(1 + 2 + 4 + … + (2^(k-1)))
  • For k = log₂ n, T(n) = nT(1) + n log₂ n
  • T(n) = 2n + n log₂ n (assuming T(1) = 2)
  • Therefore, T(n) ∈ Θ(n log n)

Binary Search

• A very efficient algorithm for searching in a sorted array A[0…n-1]
  • Compares the target K with the middle element A[m]
  • If they are equal, stop.
  • If K < A[m], search in A[0…m-1].
  • If K > A[m], search in A[m+1…n-1].

Recursive Binary Search

• Procedure BinSrch(a, l, r, x)
  • If l == r, return 1 if x == a[l], else 0
  • Calculate mid = (l + r)/2
  • If x == a[mid], return mid
  • If x < a[mid], recursively call BinSrch on a, l, mid-1, x
  • If x > a[mid], recursively call BinSrch on a, mid+1, r, x

Non-Recursive Binary Search

• Procedure BinSearch(a, n, x)
  • Initialize low = 1, high = n
  • While low <= high:
    • Calculate mid = (low + high)/2
    • If x < a[mid], high = mid - 1
    • Else if x > a[mid], low = mid + 1
    • Else, return mid
  • Return 0 if not found

Binary Search- Three Examples

• Demonstrates how binary search works with different target values in a sorted array

Binary Decision Tree

• A tree representing the comparisons made in binary search.
• The average number of comparisons for successful searches is approximately 3.21, and for unsuccessful searches is approximately 3.93.

Time Analysis of Binary Search

• Successful searches: Best, Average, and Worst case complexity is Θ(log₂n)
• Unsuccessful searches: Best, Average, and Worst case complexity is Θ(log₂n)

Mergesort

• Splits the array into two approximately equal halves.
• Sorts the halves recursively.
• Merges the sorted halves into a single sorted array (using an auxiliary array)

Merge Sort and Merge Algorithm

• Procedure MergeSort(low, high)

  • If low < high:
    • mid = (low + high)/2
    • MergeSort(low, mid)
    • MergeSort(mid+1, high)
    • Merge(low, mid, high)

• Procedure Merge(low, mid, high)

• Merges two sorted sub-arrays of a into the auxiliary array b

Time Complexity of Merge Sort

• T(n) = 2T(n/2) + cn for n > 1, T(1) = c, where c is a constant
• The complexity is Θ(n log n) in all cases

Analysis of Mergesort

• All cases have the same efficiency: Θ(n log n)
• Space requirement: Θ(n) (not in-place)
• Can be implemented without recursion (bottom-up approach).

Two Inefficiencies of Merge Sort

• Not in-place (uses another array)
• Copy operation between arrays is required
• Space and time for stack due to recursion
• For small set sizes, most of the time consumed by recursion instead of sorting

Quicksort

• Sorts an array in place using a divide-and-conquer approach
• Divides the array based on a pivot element
• Recursive calls to sort the partitions
• No extra array needed for merging
• Can be inefficient if partitions are unbalanced

Quicksort Procedure

• Procedure Quicksort(p, q)
  • If p<q:
    • j = Partition(a, p, q+1)
    • Quicksort(p, j – 1)
    • Quicksort(j+1, q)

Quicksort Partition Procedure

• Procedure Partition(a, m, p) -Partition elements of a such that part of the elements are smaller/equal to a[m] and other part are greater.

Analysis of Quicksort

• Best, Average and Worst case analysis:
  • Best Case: Θ(nlogn)
  • Average Case: Θ(nlogn)
  • Worst Case: Θ(n²) (if input is sorted or nearly sorted)