Divide And Conquer Algorithms

Divide And Conquer Algorithms

(Quick Notes)

General Approach

• This paradigm has three steps involved in order to solve the problems
  • Divide:Break the problem into sub problem.
  • Conquer:Solve the sub-problems recursively.
  • Combine:Combine the sub-problem solutions to get the final solution.

Binary Search

• The D&C Approach
  • Divide:Check the mid element.
  • Conquer:Recursively search the sub array
  • Combine:Trivial.(lol ;-)) means no need to as such combine as we are searching
• Recurrence Relation
  • T(n)=1T(n/2)+ϴ(1)
    • 1=># sub-problem
    • n/2=>size of sub problems
    • ϴ(1)=>work done in dividing and conquering
• Complexity
  • Applying Master's Theorem to T(n)=1T(n/2)+ϴ(1).
  • {Master Theorem ComplainceT(n)=aT(n/b)+f(n)}
  • n ^log_b^a = n ^log₂¹ = n⁰=1=f(n)
  • T(n)=ϴ(lg n)
• Pseudo-code
  • BinarySearch(A,min,max,key)
    • if min>max
      • then return Φ //Element Not Found
    • if A[mid]=num
      • return mid //The index where element is
    • else if A[mid]<num
      • return BinarySearch(A,mid+1,max,num)
    • else
      • return BinarySearch(A,min,mid-1,num)

Merge Sort

• The D&C Approach
  • Divide:Divide the n-element sequence to be sorted into two sub sequences of n/2 element.
  • Conquer:Recursively Sort the two sub sequences
  • Combine: Merge two
• Recurrence Relation
  • T(n)=ϴ(1) if n=1
  • T(n)=2T(n/2)+ϴ(n) if n>1
    • 2=># sub-problem
    • n/2=>size of sub problems
    • ϴ(n)=>work done in dividing and conquering
• Complexity
  • Applying Master's Theorem to T(n)=2T(n/2)+ϴ(n).
  • {Master Theorem ComplainceT(n)=aT(n/b)+f(n)}
  • n ^log_b^a = n ^log₂² = n
  • T(n)=ϴ(n.lg n)
• Pseudo-code
  • MergeSort(A,p,r)
    • if p<r then,
      • q <=(p+r)/2
      • MergeSort(A,p,q)
      • MergeSort(A,q+1,r)
      • Merge(A,p,q,r)
  • Merge(A,p,q,r)
    • //Merge two sorted arrays

Posted in: Notes