## Divide and Conquer method Illustrated

Divide and Conquer is one of the famous algorithmic techniques. It works with the philosophy that divide the whole problem into smaller managable chunks of subproblems and work out these small subproblems there by combining the intermediate partial solutions.

There are many famous examples which use the Divide and Conqure strategy, for example Binary search, Merge sort, Insertion sort, Quick sort etc.,

Let us take a small example of finding minimum and maximum elements in a given array. If we adapt a normal methodology it takes atleast 2*(n-1) comparisions. We can decrease the number of comparisions using this technique which results in [ Ceil(3*n/2)-2 ] comparisions.

The below is the code for finding MIN and MAX of the given array which was compiled and tested using GNU g++compiler.

//Author: Vasanth Raja Chittampally #include <iostream> using namespace std; void findMin(int [],int, int,int &, int &); int main() { int n,min,max; cout<<"Enter n:"; cin>>n; int a[n]; for(int i=0;i<n;i++) { cout<<"Enter a["<<i<<"]:"; cin>>a[i]; } findMin(a,0,n-1,min,max); cout<<"Minimun of the given array is: "<<min<<;endl; cout<<"Maximum of the gvien arrays is: "<<max<<endl; return 0; } void findMin(int a[], int left, int right, int &min, int &max) { if(left==right) { min=a[left]; max=a[right]; } else { int mid=(left+right)/2; findMin(a,left,mid,min,max); int left_min=min; int left_max=max; findMin(a,mid+1,right,min,max); int right_min=min; int right_max=max; if(left_min<right_min) min=left_min; else min=right_min; if(left_max>right_max) max=left_max; else max=right_max; } }

In this example it divides whole array into two equal parts recursively and tries to compare partial solutions to find the minimum and maximum elements.

T(n)=2T(n/2) + **2 ** —–>(2 comparisions are needed one for minimum and the other of maximum)

.

.

.

.

number of comparisions = [ Ceil(3*n/2)-2 ]

**The above number of comparisions can be verified by substituting in T(n)**

T(n)=2*[3*n/(2*2) – 2]+2

T(n)=3n/2-2 (hence verfied)

## program to swap two numbers with out using temporary variable with in one line

#include <stdio.h>#include <conio.h>int main(void){int a , b;printf(“Enter two integers: “);scanf(“%d%d”,&a,&b);printf(“Before swapping: a=%d,b=%d\n”,a,b);a=(a+b)-(b=a);//This is just one lineprintf(“After swapping: a=%d,b=%d”,a,b);getch();return 0;}compiled on :gcc logic :simple and tricky

## program to swap two numbers with out using temporary variable

#include < stdio.h > #include < conio.h > int main(void) { int a,b,i,j; clrscr(); printf(“Enter two integers: “); scanf(“%d%d”,&a,&b); printf(“a=%d,b=%d\n”,a,b); for(i=0;i<sizeof(int)*8;i++) { if((a&(1<<i))^(b&(1<<i))) { a=a^(1<<i); b=b^(1<<i); } } printf(“a=%d,b=%d”,a,b); getch(); return 0; }

## Program to extract source code from comment lines

Compiled on: Turbo C, gcc

Description : Extracts the program source code with out the comment lines in the given source file