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.");
}
}