Decrease and Conquer

Basic idea of the decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance.

This approach is also known as incremental or inductive approach.

Decrease or reduce problem instance to smaller instance of the same problem and extend solution.

Conquer the problem by solving smaller instance of the problem.

Extend solution of smaller instance to obtain solution to original problem .

There are three major variations of decrease-and-conquer:

  • Decrease by a constant
  • Decrease by a constant factor
  • Variable size decrease

Decrease by a constant

Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Simulation insertion Sort

Java Program

public class InsertionSortExample {  
    public static void insertionSort(int array[]) {  
        int n = array.length;  
        for (int j = 1; j < n; j++) {  
            int key = array[j];  
            int i = j-1;  
            while ( (i > -1) && ( array [i] > key ) ) {  
                array [i+1] = array [i];  
                i--;  
            }  
            array[i+1] = key;  
        }  
    }  
       
    public static void main(String a[]){    
        int[] arr1 = {9,14,3,2,43,11,58,22};    
        System.out.println("Before Insertion Sort");    
        for(int i:arr1){    
            System.out.print(i+" ");    
        }    
        System.out.println();    
            
        insertionSort(arr1);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");    
        for(int i:arr1){    
            System.out.print(i+" ");    
        }    
    }    
}    

BFS / DFS

Sample Program

BFS

App.java

public class App {

	public static void main(String[] args) {
		
		BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch();
		
		Vertex vertex1 = new Vertex(1);
		Vertex vertex2 = new Vertex(2);
		Vertex vertex3 = new Vertex(3);
		Vertex vertex4 = new Vertex(4);
		Vertex vertex5 = new Vertex(5);
		
		vertex1.addNeighbour(vertex2);
		vertex1.addNeighbour(vertex4);
		vertex4.addNeighbour(vertex5);
		vertex2.addNeighbour(vertex3);
		
		breadthFirstSearch.bfs(vertex1);

	}
}

BreadthFirstSearch.java

import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearch {

	public void bfs(Vertex root){
		
		Queue<Vertex> queue = new LinkedList<>();
		
		root.setVisited(true);
		queue.add(root);
		
		while( !queue.isEmpty() ){
			
			Vertex actualVertex = queue.remove();
			System.out.print(actualVertex+" ");
			
			for( Vertex v : actualVertex.getNeighbourList() ){
				if( !v.isVisited() ){
					v.setVisited(true);
					queue.add(v);
				}
			}			
		}
	}
}

Vertex.java

import java.util.ArrayList;
import java.util.List;

public class Vertex {

	private int data;
	private boolean visited;
	private List<Vertex> neighbourList;
	
	public Vertex(int data){
		this.data=data;
		this.neighbourList = new ArrayList<>();
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}

	public List<Vertex> getNeighbourList() {
		return neighbourList;
	}

	public void addNeighbour(Vertex neighbour) {
		this.neighbourList.add(neighbour);
	}
	
	@Override
	public String toString() {
		return ""+this.data;
	}
}

DFS

App.java


public class App {

	public static void main(String[] args) {
		
		
		
		Vertex vertex1 = new Vertex("1");
		Vertex vertex2 = new Vertex("2");
		Vertex vertex3 = new Vertex("3");
		Vertex vertex4 = new Vertex("4");
		Vertex vertex5 = new Vertex("5");
		
		vertex1.addNeighbour(vertex2);
		vertex1.addNeighbour(vertex4);
		vertex4.addNeighbour(vertex5);
		vertex2.addNeighbour(vertex3);
		
//		DepthFirstSearch depthFirstSearch = new DepthFirstSearch();
//		depthFirstSearch.dfsNormal(vertex1);

	}
}

DepthFirstSearch.java


import java.util.List;
import java.util.Stack;


public class DepthFirstSearch {
	
//	private Stack<Vertex> stack;
//	
//	public DepthFirstSearch(){
//		this.stack=new Stack<>();
//	}
//	
//	public void dfsRecursive(Vertex vertex){
//		
//		System.out.print(vertex+"->");
//		
//		for( Vertex v : vertex.getNeighbourList() ){
//			if( !v.isVisited() ){
//				v.setVisited(true);
//				dfsRecursive(v);
//			}
//		}
//	}
//	
//	public void dfsNormal(Vertex root){
//		
//		stack.add(root);
//		root.setVisited(true);	
//		
//		while( !stack.isEmpty() ){
//			
//			Vertex actualVertex = stack.pop();
//			System.out.print(actualVertex+"->");
//			
//			for( Vertex v : actualVertex.getNeighbourList() ){
//				if( !v.isVisited() ){
//					v.setVisited(true);
//					stack.push(v);
//				}
//			}
//		}	
//	}
	
	private List<Vertex> vertexList;
	private int time = 0;
	
	public DepthFirstSearch(List<Vertex> vertexList){
		this.vertexList = vertexList;
	}
	
	public void runDfs(){
		for( Vertex vertex : vertexList ){
			if( !vertex.isVisited() ){
				dfs(vertex);
			}
		}
	}
	
	public void dfs(Vertex vertex){
		
		System.out.print(vertex.getName()+"-");
		
		time++;
		vertex.setStartingRank(time);
		
		for( Vertex v : vertex.getNeighbourList() ){
			if( !v.isVisited() ){
				v.setVisited(true);
				v.setPredecessor(vertex);
				dfs(v);
			}
		}
		
		time++;
		vertex.setFinishingRank(time);	
	}
	
	public void printVertices(){
		for(Vertex vertex : vertexList){
			System.out.println(vertex+"");
		}
	}
}

Vertex.java


import java.util.ArrayList;
import java.util.List;


public class Vertex {

//	private int data;
//	private boolean visited;
//	private List<Vertex> neighbourList;
//	
//	public Vertex(int data){
//		this.data=data;
//		this.neighbourList = new ArrayList<>();
//	}
//	
//	public void addNeighbour(Vertex vertex){
//		this.neighbourList.add(vertex);
//	}
//
//	public int getData() {
//		return data;
//	}
//
//	public void setData(int data) {
//		this.data = data;
//	}
//
//	public boolean isVisited() {
//		return visited;
//	}
//
//	public void setVisited(boolean visited) {
//		this.visited = visited;
//	}
//
//	public List<Vertex> getNeighbourList() {
//		return neighbourList;
//	}
//	
//	@Override
//	public String toString() {
//		return ""+this.data;
//	}
	
	private String name;
	private List<Vertex> neighbourList;
	private boolean visited;
	private Vertex predecessor;
	private int startingRank;
	private int finishingRank;

	public Vertex(String name) {
		this.name = name;
		this.neighbourList = new ArrayList<>();
	}

	public void addNeighbour(Vertex vertex) {
		this.neighbourList.add(vertex);
	}

	public Vertex getPredecessor() {
		return predecessor;
	}

	public void setPredecessor(Vertex predecessor) {
		this.predecessor = predecessor;
	}

	public int getStartingRank() {
		return startingRank;
	}

	public void setStartingRank(int startingRank) {
		this.startingRank = startingRank;
	}

	public String getName() {
		return name;
	}

	public int getFinishingRank() {
		return finishingRank;
	}

	public void setFinishingRank(int finishingRank) {
		this.finishingRank = finishingRank;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}

	public List<Vertex> getNeighbourList() {
		return neighbourList;
	}

	@Override
	public String toString() {
		return this.name+"- StartTime: "+startingRank+"- EndTime: "+finishingRank;
	}
}

Generating Permuntation

import java.util.*;
 
class Permutation1{
  
static void permute(String s , String answer)
{  
    if (s.length() == 0)
    {
        System.out.print(answer + "  ");
        return;
    }
     
    for(int i = 0 ;i < s.length(); i++)
    {
        char ch = s.charAt(i);
        String left_substr = s.substring(0, i);
        String right_substr = s.substring(i + 1);
        String rest = left_substr + right_substr;
        permute(rest, answer + ch);
    }
}
 
// Driver code
public static void main(String args[])
{
    Scanner scan = new Scanner(System.in);
     
    String s;
    String answer="";
     
    System.out.print("Enter the string : ");
    s = scan.next();
     
    System.out.print("\nAll possible strings are : ");
    permute(s, answer);
}
}
 

Decrease by a constant factor

BinarySearch.java

import java.util.*;  
public class BinarySearch {  
public static void main(String[] args) {  
    int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
    int item, location = -1;  
    System.out.println("Enter the item which you want to search");  
    Scanner sc = new Scanner(System.in);  
    item = sc.nextInt();  
    location = binarySearch(arr,0,9,item);  
    if(location != -1)  
    System.out.println("the location of the item is "+location);  
    else   
        System.out.println("Item not found");  
    }  
public static int binarySearch(int[] a, int beg, int end, int item)  
{  
    int mid;  
    if(end >= beg)   
    {     
        mid = (beg + end)/2;  
        if(a[mid] == item)  
        {  
            return mid+1;  
        }  
        else if(a[mid] < item)   
        {  
            return binarySearch(a,mid+1,end,item);  
        }  
        else   
        {  
            return binarySearch(a,beg,mid-1,item);  
        }  
      
    }  
    return -1;   
}  
}  

Russian peasant multiplication

 RussianMultiplication.java

import java.util.Scanner;
 
class RussianMultiplication
{
 public static void main(String[] args)
 {
  //get the input numbers
  Scanner sc=new Scanner(System.in);

  System.out.print("Enter the first number: ");
  int num1=sc.nextInt();
  
  System.out.print("Enter the second number: ");
  int num2=sc.nextInt();
  int product=0;
  
  if(num1%2!=0)
      product=product+num2;
  
  System.out.println("Multiplicand Multiplier Product");
  System.out.println("\t"+num1+"\t"+num2);
  
  while(num1!=1)
  {
   num1=num1/2;
   num2=num2*2;
   if(num1%2!=0)
    product=product+num2;
   System.out.println("\t"+num1+"\t"+num2);
  }
  
  System.out.println("The product is: "+product);
 }
}

Variable size decrease

Selection Sort

Simulation Selection Sort

SelectionSortExample.java

public class SelectionSortExample {  
    public static void selectionSort(int[] arr){  
        for (int i = 0; i < arr.length - 1; i++)  
        {  
            int index = i;  
            for (int j = i + 1; j < arr.length; j++){  
                if (arr[j] < arr[index]){  
                    index = j;//searching for lowest index  
                }  
            }  
            int smallerNumber = arr[index];   
            arr[index] = arr[i];  
            arr[i] = smallerNumber;  
        }  
    }  
       
    public static void main(String a[]){  
        int[] arr1 = {9,14,3,2,43,11,58,22};  
        System.out.println("Before Selection Sort");  
        for(int i:arr1){  
            System.out.print(i+" ");  
        }  
        System.out.println();  
          
        selectionSort(arr1);//sorting array using selection sort  
         
        System.out.println("After Selection Sort");  
        for(int i:arr1){  
            System.out.print(i+" ");  
        }  
    }  
}  

Computing median

Median.java

import java.util.Scanner;

class Median 
{
   public static void main(String args[]) 
    { 
	
	Scanner sc=new Scanner(System.in);
	System.out.println("enter a number"); 
	int n=sc.nextInt();
	double[] input=new double[n];
	System.out.println("enter "+n+" elements");
	double m=0;
	for(int i=0;i<n;i++) 
	{
		input[i]=sc.nextDouble();
		
	}
	if(n%2==1)
	{
		m=input[(n+1)/2-1];
	}
	else
	{
		m=(input[n/2-1]+input[n/2])/2;
	}
	
       System.out.println("Median :"+m);  
   }
}

Interpolation.java

// Java program to implement interpolation
// search with recursion
import java.util.*;
 
class Interpolation {
 
    // If x is present in arr[0..n-1], then returns
    // index of it, else returns -1.
    public static int interpolationSearch(int arr[], int lo,
                                          int hi, int x)
    {
        int pos;
 
        // Since array is sorted, an element
        // present in array must be in range
        // defined by corner
        if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
 
            // Probing the position with keeping
            // uniform distribution in mind.
            pos = lo
                  + (((hi - lo) / (arr[hi] - arr[lo]))
                     * (x - arr[lo]));
 
            // Condition of target found
            if (arr[pos] == x)
                return pos;
 
            // If x is larger, x is in right sub array
            if (arr[pos] < x)
                return interpolationSearch(arr, pos + 1, hi,
                                           x);
 
            // If x is smaller, x is in left sub array
            if (arr[pos] > x)
                return interpolationSearch(arr, lo, pos - 1,
                                           x);
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
 
        // Array of items on which search will
        // be conducted.
        int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
                      22, 23, 24, 33, 35, 42, 47 };
 
        int n = arr.length;
 
        // Element to be searched
        int x = 18;
        int index = interpolationSearch(arr, 0, n - 1, x);
 
        // If element was found
        if (index != -1)
            System.out.println("Element found at index "
                               + index);
        else
            System.out.println("Element not found.");
    }
}