Category Archives: Data Structure

Algorithm paradigm | Introduction to Divide and conquer algorithm

Divide and conquer algorithm

Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. A typical Divide and Conquer algorithm solves a problem using following three steps.

  1. Divide: Break the problem into sub-problems of same type.
  2. Conquer: Recursively solve these sub-problems.
  3. Combine: Combine the solution sub-problems.

 

These are methods of designing algorithms that (informally) proceed as follows:

Given an instance of the problem to be solved, split this into several smaller sub-instances (of the same problem), independently solve each of the sub-instances and then combine the sub-instance solutions so as to yield a solution for the original instance.

With the divide-and-conquer method the size of the problem instance is reduced by a factor (e.g. half the input size), while with the decrease-and-conquer method the size is reduced by a constant.

Example of divide-and-conquer algorithms:

  • Merge Sort
  • Quick Sort
  • Binary Search
  • Strassen’s Matrix Multiplication
  • Closest pair (points)
  • Cooley–Tukey Fast Fourier Transform (FFT) algorithm
  • Karatsuba algorithm for fast multiplication

Examples of decrease-and-conquer algorithms:

  1.  Insertion sort
  2.  Topological sorting
  3. Binary Tree traversals: inorder, preorder and postorder (recursion)
  4.  Computing the length of the longest path in a binary tree (recursion)
  5.  Computing Fibonacci numbers (recursion)
  6.  Reversing a queue (recursion)
  7.  Warshall’s algorithm (recursion)

 

 Advantages of Divide and Conquer

  • The most recognizable benefit of the divide and conquer paradigm is that it allows us to solve difficult problem, such as the Tower of Hanoi, which is a mathematical game or puzzle. Being given a difficult problem can often be discouraging if there is no idea how to go about solving it. However, with the divide and conquer method, it reduces the degree of difficulty since it divides the problem into sub problems that are easily solvable, and usually runs faster than other algorithms would.
  • It also uses memory caches effectively. When the sub problems become simple enough, they can be solved within a cache, without having to access the slower main memory.

 Disadvantages of Divide and Conquer

  • One of the most common issues with this sort of algorithm is the fact that the recursion is slow, which in some cases outweighs any advantages of this divide and conquer process.
  • Sometimes it can become more complicated than a basic iterative approach, especially in cases with a large n. In other words, if someone wanted to add a large amount of numbers together, if they just create a simple loop to add them together, it would turn out to be a much simpler approach than it would be to divide the numbers up into two groups, add these groups recursively, and then add the sums of the two groups together.

Example Merge sort:

Merge Sort is a Divide and conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following algorithm for details.

mergeSort(arr[], left,  right)
If right > left
     1. Find the middle point to divide the array into two halves:  
             middle  = (left+right)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, left, middle)
     3. Call mergeSort for second half:
             Call mergeSort(arr, middle+1, right)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, left, middle, right)

 

Java implementation of merge sort is given below:


/* Java program for implement Merge Sort */
class MergeSort {

// Merges two subarrays of arr[].
// First subarray is arr[left to middle]
// Second subarray is arr[middle+1 to right]
void merge(int arr[], int left, int middle, int right) {
// Find sizes of two subarrays to be merged
int n1 = middle - left + 1;
int n2 = right - middle;

/* Create temp arrays */
int LEFT[] = new int[n1];
int RIGHT[] = new int[n2];

/*Copy data to temp arrays*/
for (int i = 0; i < n1; ++i) {
LEFT[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
RIGHT[j] = arr[middle + 1 + j];
}

/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;

// Initial index of merged subarry array
int k = left;
while (i < n1 && j < n2) {
if (LEFT[i] <= RIGHT[j]) {
arr[k] = LEFT[i];
i++;
} else {
arr[k] = RIGHT[j];
j++;
}
k++;
}

/* Copy remaining elements of LEFT[] if any */
while (i < n1) {
arr[k] = LEFT[i];
i++;
k++;
}

/* Copy remaining elements of RIGHT[] if any */
while (j < n2) {
arr[k] = RIGHT[j];
j++;
k++;
}
}

// Main function that sorts arr[l..r] using
// merge()
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int middle = (left + right) / 2;

// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);

// Merge the sorted halves
merge(arr, left, middle, right);
}
}

/* A utility function to print array of size n */
void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

// Driver method
public static void main(String args[]) {
int arr[] = {12, 19, 13, 51, 6, 7, 68};
MergeSort ob = new MergeSort();
System.out.println("Given Array");
ob.printArray(arr);

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

System.out.println("\nSorted array");
ob.printArray(arr);
}
}
/* This code is contributed by Sani Kamal */

 

output:

run:
Given Array
12 19 13 51 6 7 68

Sorted array
6 7 12 13 19 51 68
BUILD SUCCESSFUL (total time: 1 second)

Time Complexity: \Theta(nLogn)

Auxiliary Space: O(n)

Algorithmic Paradigm: Divide and Conquer

Sorting In Place: No in a typical implementation

Stable: Yes

Applications of Merge Sort

  1. Merge sort is useful for sorting linked lists in O(nLogn) time
  2. Inversion count problem
  3. Used in External Sorting

 

 

 

Advertisements

Java program to find LCM of given array

Least Common Multiple (LCM) of two numbers is the smallest number which can be divided by both numbers. or The smallest positive number that is a multiple of two or more numbers.

Let’s start with an Example …
List the multiples of each number,
Least Common Multiple (LCM) of 15 and 20:
The multiples of 15 are 15, 30, 45, 60<, 75, 90, … etc
The multiples of 20 are 20, 40, 60, 80, 100, … etc

Find the first Common (same) value:

LCM of 15 and 20 is 60

For example LCM of 15 and 20 is 60 and LCM of 5 and 7 is 35.

LCM of two numbers ‘x’ and ‘y’ can be calculated using following formula.

x * y = LCM(x, y) * GCD (x, y)

LCM(x, y) = (x * y) / GCD(x, y)

The above relation only holds for two numbers,

LCM(x, y, z) != (x * y * z) / GCD( x, y, z)

The main steps of our algorithm are:

Initialize ans = arr[0].
Iterate over all the elements of the array i.e. from i = 1 to i = n-1
At the ith iteration ans = LCM(arr[0], arr[1], …….., arr[i-1]). This can be done easily as LCM(arr[0], arr[1], …., arr[i]) = LCM(ans, arr[i]). Thus at i’th iteration we just have to do ans = LCM(ans, arr[i]) = ans x arr[i] / gcd(ans, arr[i])

Below is a implementation in java of above algorithm:

 

 

// Java program to find LCM of array elements
public class TestLCM {

// function to find GCD of 'x' and 'y'
int gcd(int x, int y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}

// Returns LCM of array elements
int lcm(int arr[], int n) {
// Initialize result
int ans = arr[0];

// ans contains LCM of arr[0],..arr[i]
// after i'th iteration,
for (int i = 1; i < n; i++) {
ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
}

return ans;
}
//driver method
public static void main(String[] args) {
TestLCM t1 = new TestLCM();
int a[] = {1, 5, 7, 4, 8};
System.out.println("LCM is " + t1.lcm(a, a.length));
int b[] = {3, 5, 7, 9, 34, 12};
System.out.println("LCM is:" + t1.lcm(b, b.length));
}

}

 

 

output:

run:
LCM is 280
LCM is:21420
BUILD SUCCESSFUL (total time: 0 seconds)

Java program to find LCM of two numbers

Least Common Multiple (LCM)

of two numbers is the smallest number which can be divided by both numbers. or The smallest positive number that is a multiple of two or more numbers.

Let’s start with an Example …
List the multiples of each number,
Least Common Multiple (LCM) of 15 and 20:
The multiples of 15 are 15, 30, 45, 60, 75, 90, … etc
The multiples of 20 are 20, 40, 60, 80, 100, … etc

Find the first Common (same) value:

LCM of 15 and 20 is 60

For example LCM of 15 and 20 is 60 and LCM of 5 and 7 is 35.

LCM of two numbers ‘x’ and ‘y’ can be calculated using following formula.

x * y = LCM(x, y) * GCD (x, y)

LCM(x, y) = (x * y) / GCD(x, y)

// Java program to find LCM of given two number

class TestLCM {

// Recursive method to return gcd of x and y
static int gcd(int x, int y) {
// Everything divides 0
if (x == 0 || y == 0) {
return 0;
}

// base case
if (x == y) {
return x;
}

// x is greater
if (x > y) {
return gcd(x - y, y);
}
return gcd(x, y - x);
}

// method to return LCM of two numbers
public int lcm(int x, int y) {
return (x * y) / gcd(x, y);
}

// Driver method
public static void main(String[] args) {
TestLCM t1 = new TestLCM();
int a = 3, b = 5;
System.out.println("LCM of " + a + " and " + b + " is " + t1.lcm(a, b));
int c = 5, d = 7;
System.out.println("LCM of " + c + " and " + d + " is " + t1.lcm(c, d));
}
}

output:
run:
LCM of 3 and 5 is 15
LCM of 5 and 7 is 35
BUILD SUCCESSFUL (total time: 1 second)

Tower of Hanoi implementation in java

The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower  and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a canonical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

Recursive Algorithm

The recursive solution to move n discs from the start pole to the end pole using an auxiliary pole is given below.

Base Case – When n = 1
Move the disc from start pole to end pole
Recursive Case – When n > 1
Step 1: Move (n-1) discs from start pole to auxiliary pole.
Step 2: Move the last disc from start pole to end pole.
Step 3: Move the (n-1) discs from auxiliary pole to end pole.
Steps 1 and 3 are recursive invocations of the same procedure.
Java Program
The recursive program for the puzzle in Java is given below:
<pre>import java.util.Scanner;

/**
 * java program to implement tower of hanoi
 * Created by sani kamal on 07-May-17.
 */
public class TowerOfHanoi {
    //main function
    public static void main(String[] args) {
        System.out.println("Enter number of disc:");
        Scanner sc = new Scanner(System.in);
        int numberOfDiscs = sc.nextInt();
        moveDiscs(numberOfDiscs, "A", "B", "C");


    }

    public static void moveDiscs(int n, String start, String middle, String end) {
        //Moved n-th disc to the end pole
        if (n == 1) {
            System.out.println("Move " + n + " disc from " + start + " to " + end);
        } else {
            //Move n-1 discs from start pole to the midle
            moveDiscs(n - 1, start, end, middle);
            System.out.println("Move " + n + " disc from " + start + " to " + end);
            //Move n-1 discs from middle pole to the end
            moveDiscs(n - 1, middle, start, end);

        }

    }
}</pre>

Java Program to Implement Euclid GCD Algorithm using Recursion

The Euclidean algorithm calculates the greatest common divisor (GCD) of two number a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for the GCD include the greatest common factor (GCF), the highest common factor (HCF), the highest common divisor (HCD), and the greatest common measure (GCM).

The Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:
  • If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
  • If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
  • Write A in quotient remainder form (A = B⋅Q + R)
  • Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)
           // Function to return gcd of a and b
        int gcd(int a, int b)
          {
             if (a == 0)
                 return b;
             return gcd(b%a, a);
           }
This is a program to find GCD (Greatest Common Divisor) of two numbers using Euclid’s Algorithm.
<pre>import java.util.Scanner;

/**
 * Java Program to Implement Euclid GCD Algorithm using Recursion
 * Created by sani kamal on 07-May-17.
 */
public class GCDEuclid {
    //main function
    public static void main(String[] args) {
        GCDEuclid gcdeu = new GCDEuclid();
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number1:");
        int num1 = sc.nextInt();
        System.out.println("Enter number2:");
        int num2 = sc.nextInt();
        System.out.println("GCD of " + num1 + " and " + num2 + " is:" + gcdeu.gcd(num1, num2));


    }

    // This function calculate GCD
    private int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);

    }
}</pre>
The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
"C:\Program Files\Java\jdk1.8.0_65\bin\java" -Didea.launcher.port=7536 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.1.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_65\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\rt.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\out\production\JavaByExample;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\laf-plugin-7.2.1.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\laf-widget-6.3.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\substance-7.2.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\trident.jar.zip;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\xmlbeans-2.6.0.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-ooxml-schemas-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-ooxml-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\mail.jar;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.1.3\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain com.muktangon.net.recursion.GCDEuclid
Enter number1:
5
Enter number2:
25
GCD of 5 and 25 is:5

Process finished with exit code 0

java program to find n-th fibonacci number using recursion

The Fibonacci numbers are the numbers in the following integer sequence called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

The fibonacci series is defined as follows:

0,1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , …

Recursive Algorithm for Fibonacci Numbers

Algorithm F(n)

if n ≤ 1 then return n

else return F(n-1) + F(n-2)

 

Full java program is given below:

<pre>import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to find n-th fibonacci number using recursion
 * Created by sani kamal on 07-May-17.
 */
public class Fibonacci {
    public static void main(String[] args) {
        Fibonacci fib = new Fibonacci();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            System.out.println("Enter a number:");
            int num = Integer.parseInt(br.readLine());
            System.out.print(num+"th Fibonacci number is:" + fib.fibonacci(num));

        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }

    }

    private int fibonacci(int n) {
        if (n < 1)
            return 0;
        else if (n == 1)
            return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}</pre>

Java program to find factorial of given number using recursion

Recursion  is a method where the solution to a problem depends on solutions to smaller instances of the same problem.One of the classic problems for introducing recursion is calculating the factorial of an integer. The factorial of any given integer — call it — is the product of all the integers from 1 to n. Thus, the factorial of 7 is 5040:7x6x 5 x 4 x 3 x 2 x 1.

Here’s the recursive version of the factorial method:

public static int factorial(int n)
{
    if (n <= 1)
        return 1;
    else
        return n * factorial(n-1);
}
<pre>import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to find factorial using recursion
 * Created by sani kamal on 07-May-17.
 */

public class Factorial {
    public static void main(String[] args) {
        Factorial fl = new Factorial();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            System.out.println("Enter number to find factorial(less than 20):");
            int n=Integer.parseInt(br.readLine());
            System.out.println("Factorial of "+n+" is:" + fl.factorial(n));
        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }
    }

    public int factorial(int num) {
        if (num <= 1) {
            return 1;
        }
        return num * factorial(num - 1);
    }
}</pre>