Divide and Conquer Cracked

1. Break into non-overlapping subproblems of the same type.
2. Solve subproblems.
3. Combine results

4+6+3+2+8+7+5+1

Lets take a look at recursion

Recursion is when a function calls itself.

Matryoshka dolls are these cute little things:

def getKey(doll):
	item = doll.open()
    if item == key:
    	return key
	else:
    	return getKey(item)
getKey(doll)

Pros of Recursion:

Cracks big problems.

Covert maths formulae to Code.

Fibonacci numbers

F(n)={n,If n = 0 or 1 
      F(n−1)+F(n−2),if n > 1 }
def F(n):
	if n == 0 or n == 1:
		return n
  	else:
		return F(n-1)+F(n-2)

Cons of Recursion:

Stack Overflow

Do not try for smaller problems

Lets get back to work

Calculating the factorial of a number.

Algorithm:

def recur_factorial(n):
   if n == 1:
       return n
   else:
       return n * recur_factorial(n-1)
print(recur_factorial(n))

Lets discuss:

Divide ?

Conquer ?

Combine ?

def F(n):
	if n == 1:
		return n
  	else:
		return n * F(n-1)

Merge Sort

T(n)
MergeSort(A, l, r):
    if l> r 
        return
    m = (l+r)/2
    mergeSort(A, l, m)           T(n/2)
    mergeSort(A, m+1, r)         T(n/2)
    merge(A, l, m, r)            cn

T(n) = T

=T(n/2) + T(n/2) + Cn = 2 T(n/2) + cn

= 2(2(T(n/4) + c(n/2)) + cn

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

= 4T(n/4) + 2cn = 2^kT(n/2^k) + kcn

k = logn

= 2 ^logn (T1) + logn cn = nc + nlogn= o (nlogn)

Merge Step

Algorithm:

Have we reached the end of any of the arrays?
    No:
        Compare current elements of both arrays
        Copy smaller element into sorted array
        Move pointer of element containing smaller element
    Yes:
        Copy all remaining elements of non-empty array

Practice Area:

MergeSort(A)
     n=length(A)
     if (n<2) return 
     mid=n/2
     L=A[0...mid-1]
     R=A[mid....n-1]
     for   0<= l <=mid-1
         L[l]=A[l]
     for  mid<= r <=n-1
         R[r-mid]=A[r]
     MergeSort(L) 
     MergeSort(R) 
     Merge(L,R,A)
void merge (int arr[],int l, int m, int r){
    int s1 =  m - l +1;                   //c1
    int s2 =  r - m;                      //c2
    int L[] = new int[s1];                //c3
    int R[] = new int[s2];                //c3
    for (int i=0; i <s1; i++){            //c4
      L[i] = arr[l + i];
    for (int i=0; i <s2; i++){            //c5
      R[i] = arr[r + 1 +j];
    // Loop through
    // until one of array is finished
    compareAndCopy();                     //C6*i + C6*j
                                          //c6*k
                                          //c*n
 
    copyRemainingFromLeftSubArray();
    copyRemainingFromRIghtSubArray();
//c6 * n/2  + c6*n/2 = c6*n= cn = o(n)
  }
c1 + c2 + c3 + c4 +c5 + c6*n = c7 +c6*n = c6*n = n = O(n)

Merge Method:

class MergeSort {

  public static void merge(int arr[], int l, int m, int r) {

    // Calculate size of left and right subarray
    int n1 = m - l+ 1;
    int n2 = r - m;

    int L[] = new int[n1];
    int M[] = new int[n2];
    // Populate temp left and right subarrays
    for (int i = 0; i < n1; i++)
      L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
      M[j] = arr[m + 1 + j];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = l;


    while (i < n1 && j < n2) {
      if (L[i] <= M[j]) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = M[j];
        j++;
      }
      k++;
    }

    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k] = M[j];
      j++;
      k++;
    }
  }

  void mergeSort(int arr[], int l, int r) {
    if (l < r) {

      int m = (l + r) / 2;

      mergeSort(arr, l, m);
      mergeSort(arr, m + 1, r);

      merge(arr, l, m, r);
    }
  }


  public static void main(String args[]) {
    int arr[] = { 6, 5, 12, 10, 9, 1 };

    MergeSort.mergeSort(arr, 0, arr.length - 1);

  }
}

=================================’

import java.util.Arrays;

public class MergeSortNative {

public static int[] sort(int[] randomNumbers) {
        return mergeSort(randomNumbers, 0, randomNumbers.length - 1);
    }

public static int[] mergeSort(int[] numbers, int first, int last) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergeSort(numbers, first, mid);
            mergeSort(numbers, mid + 1, last);

            merge(numbers, first, mid, last);
        }

        return numbers;
    }

private static int[] merge(int[] numbers, int i, int m, int j) {
        int l = i; //inital index of first subarray
        int r = m + 1; // initial index of second subarray
        int k = 0; // initial index of merged array
        int[] t = new int[numbers.length];

        while (l <= m && r <= j) {
            if (numbers[l] <= numbers[r]) {
                t[k] = numbers[l];
                k++;
                l++;
            } else {
                t[k] = numbers[r];
                k++;
                r++;
            }
        }

// Copy the remaining elements on left half , if there are any
        while (l <= m) {
            t[k] = numbers[l];
            k++;
            l++;
        }

// Copy the remaining elements on right half , if there are any
        while (r <= j) {
            t[k] = numbers[r];
            k++;
            r++;
        }

// Copy the remaining elements from array t back the numbers array
        l = i;
        k = 0;
        while (l <= j) {
            numbers[l] = t[k];
            l++;
            k++;
        }

        return numbers;
    }

public static void main(String args[]) {
        int[] randomNumbers = {13, 3242, 23, 2351, 352, 3915, 123, 32, 67, 5, 9};
        int[] sortedNumbers;
        sortedNumbers = sort(randomNumbers);
        System.out.println(Arrays.toString(sortedNumbers));
    }
}

Find Smallest missing integer from a sorted array

[0,1,2,3,4]

[0,1,3,4,5,6,7]

l > r

def smallestMissing(int[] A, int left, int right):
   if left > right:return left
   find mid
   if A[mid] == mid
      Search smallest Missing on Right SubArray
   else 
      Search smallestMissing on Left SubArray

Program

 public static int smallestMissing(int[] A, int left, int right)
 {
  // base condition //exit condition
  if (left > right) {
   return left;
  }
 int mid = left + (right - left) / 2;
  if (A[mid] == mid) {
   return smallestMissing(A, mid + 1, right);
  }
  else {
   return smallestMissing(A, left, mid - 1);
  }
 }

Maximum subarray sum problem

max_sum_subarray(array, low, high)
{
  if (high == low) // only one element in an array
  {
    return array[high];
  }
  mid = (high+low)/2;
  maximum_sum_left_subarray = max_sum_subarray(array, low, mid)
  maximum_sum_right_subarray = max_sum_subarray(array, mid+1, high)
  maximum_sum_crossing_subarray = max_crossing_subarray(array, low, mid, high);
  return maximum(maximum_sum_left_subarray, maximum_sum_right_subarray, maximum_sum_crossing_subarray);
}

max_crossing_subarray(int ar[], int low, int mid, int high)
{
  left_sum = -infinity
  sum = 0
  for (i=mid downto low)
  {
    sum = sum+ar[i]
    if (sum>left_sum)
      left_sum = sum
  }
  right_sum = -infinity;
  sum = 0
  for (i=mid+1 to high)
  {
    sum=sum+ar[i]
    if (sum>right_sum)
      right_sum = sum
  }
  return (left_sum+right_sum)
}

How to identify Divide and Conquer problems

When we have a problem that looks similar merge sort

If we have an algorithm that takes a list and does something with each element of the list.

If we have an algorithm that is slow and we would like to speed it up