ch2

• Divide and conquer approach


  The problem in hand is divided into smaller sub-problems and then each problem is solved independently
• Divide and conquer steps

  1. Divide: a problem to be solved is broken into a number of sub problems

  2. Conquer: the sub problems are then solved independently, usually recursively

  3. Combine: finally, the solutions to the sub problems are combined to provide the answer to the original problem
• Divide and Conquer algorithms are normally recursive
• Algorithms based on divide-and-conquer programming approach


  • Finding Max and Min
  • Binary Search
  • Merge Sort
  • Quick Sort
  • Strassen's Matrix Multiplication

  
• Sorting


  • Ordering a list of values
• Searching


  • Finding the position of a value within a list
• Time complexity


  How the number of steps required depends on the size of the input
• Space complexity


  How the amount of extra memory or storage required depends on the size of the input
• Algorithm for maximum and minimum using divide-and-conquer

  1. If the problem size is small, solve this problem directly

  2. Recursively solve the 2 sub-problems

  3. Merge the solutions of the 2 sub-problems into a solution of the original problem
• The best, average, worst case number of comparisons for MaxMin is 3n/2 - 2 when n is a power of two
• Binary search algorithm


  1. If only one element remains in the array, solve it directly

  2. Compare x with the middle element of the array

  3. If x = middle element, then output it and stop

  4. If x < middle element, then recursively solve the problem with x and the left half array

  5. If x > middle element, then recursively solve the problem with x and the right half array

  
• Binary search is optimal for searching a sorted array

  
• Merge sort algorithm


  1. DIVIDE the input sequence in half

  2. RECURSIVELY sort the two halves

  3. COMBINE the two sorted subsequences by merging them
• The merge sort algorithm recursively divides the array into halves until the base condition is met, where we are left with only 1 element in the array, and then the merge function picks up the sorted sub-arrays and merges them back to sort the entire array
• Merge Sort


  Algorithm that keeps splitting an array into two halves until a condition is met where we try to perform Merge Sort on a subarray of size 1, and then combines the individually sorted subarrays into larger arrays until the whole array is merged
• Merge Sort algorithm


  1. If p<r

  2. Then q → ( p+ r)/2

  3. MERGE-SORT (A, p, q)

  4. MERGE-SORT ( A, q+1,r)

  5. MERGE ( A, p, q, r)
• Merge Sort algorithm recursively divides the array into halves until the base condition is met, where we are left with only 1 element in the array, and then the merge function picks up the sorted sub-arrays and merge them back to sort the entire array
• Merge Sort


  • Divides the array into halves until the base condition is met, where we are left with only 1 element in the array
  • Merge function picks up the sorted sub-arrays and merge them back to sort the entire array
• Algorithm Merge-Sort


  1. If |S|2, solve it directly

  2. Recursively apply this algorithm to solve the left half part and right half part of S, and the results are stored in S1 and S2, respectively

  3. Perform the two-way merge scheme on S1 and S2
• Methods of Solving Recurrences


  • Substitution method
  • Iteration method
  • Master method
• Master Theorem


  a is the number of subproblems that are solved recursively; b is the size of each subproblem relative to n; f(n) is the cost of dividing and recombining the subproblems

  
• You cannot use the Master Theorem if T(n) is not monotone, f(n) is not a polynomial, or b cannot be expressed as a constant

  
• Master Theorem: Example 1


  • T(n) = T(n/2) + ½ n2 + n
  • a = 1, b = 2, d = 2
  • T(n) (n2)
• Master Theorem: Example 2


  • T(n)= 2 T(n/4) + n + 42
  • a = 2, b = 4, d = 1/2
  • T(n) (n log n)

  
• Master Theorem: Example 3


  • T(n)= 3 T(n/2) + 3/4n + 1
  • a = 3, b = 2, d = 1
  • T(n) (n1.584)
• Recurrence Relation for Merge sort


  • If n = 1, then T(n) = (1) (constant)
  • If n > 1, then T(n) = 2 T(n/2) + (n)
• Merge sort requires log2n passes and has a time complexity of O(nlogn)
• Time complexity of the general algorithm


  • T(n)= 2T(n/2)+S(n)+M(n)
  • S(n): time for splitting
  • M(n): time for merging
• Merge Sort is considered the method of choice for internal sorting of large files (n ≥ 10000)
• Divide and Conquer Algorithms often reduce the number of iterations of the main loop from n to log2 n
• Strassen's Matrix Multiplication Algorithm


  Reduces the number of matrix multiplications required to compute the product of two matrices from 8 to 7
• Strassen's Matrix Multiplication


  1. Divide A, B and C into 4 quadrants

  2. Compute the 4 quadrants of C by doing 7 matrix multiplications on the quadrants of A and B, plus (n2) scalar operations
• Strassen's Matrix Multiplication algorithm has a recurrence of T(n) = 7T(n/2) + (n2), which results in a time complexity of (n2.807)