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

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Google Analytics Guide for Beginners

Errors and Warnings in Swift 5.1 !!? Checkout if that got listed here.

Why you should have many AWS account(s)!

Personally Tech With Summly Founder Nick D’Aloisio

Terrarbitage, Part 2

Leetcode 1487: Making File Names Unique

Routing table in Linux

Building a REST API E-Wallet MVP Using Spring Boot — Part 2 (Project Lombok)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vaibhav Hajela

Vaibhav Hajela

More from Medium

Gentrification, and a former shell of San Jose

REMEMBER HIS IMPERIAL MAJESTY

The Start of Something New

Can Humans achieve Interstellar Travel