01: Analysis of the Making change Problem by using Greedy Algorithm.
#include<iostream.h>
#include<conio.h> class makechange { public: void greedy(float *a,float n1,int z)
{ int x=0; float sol=0; for(int i=0;i<z;i++)
{ while(sol<n1)
{ sol=sol+a[i]; if(sol>n1)
{ sol=sol-a[i]; break;
} else x++;
}
cout<<endl<<x<<" "<<a[i]<<" s"; x=0;
} if(sol!=n1) cout<<endl<<"Change not Enough!!!"<<endl; else cout<<endl<<"Solution Found..."<<endl;
}
}; void main()
{ float a[9],amt; int z=9; a[0]=100.00f; a[1]=50.00f; a[2]=20.00f; a[3]=10.00f; a[4]=5.00f; a[5]=2.00f; a[6]=1.00f; a[7]=0.50f; a[8]=0.25f; makechange obj; clrscr();
cout<<"Please Enter the Amount: "; cin>>amt;
cout<<endl<<"SOLUTION :"<<endl; obj.greedy(a,amt,z); getch();
}
OUTPUT:
Please Enter the Amount: 167.75 SOLUTION :
1 100 s
1 50 s
0 20 s
1 10 s
1 5 s
1 2 s
0 1 s
1 0.5 s
1 0.25 s Solution Found... 
02: Analysis of the Job Sequencing Problem by using Greedy Algorithm.
#include<iostream.h>
#include<conio.h> struct Job
{ char id; int dead; int profit;
};
class JobSchedule { public: int min(int a, int b)
{ if(a<=b) return a; else return b;
}
void printJobScheduling(Job arr[], int n)
{ int i,j,temp; char ch; for(i=0;i<n;i++)
{ for(j=i+1;j<n;j++)
{ if(arr[i].profit < arr[j].profit)
{ ch = arr[i].id; arr[i].id = arr[j].id; arr[j].id = ch;
temp = arr[i].dead; arr[i].dead = arr[j].dead; arr[j].dead = temp;
temp = arr[i].profit; arr[i].profit = arr[j].profit; arr[j].profit = temp;
}
}
}
int result[50]; int slot[50];
for (i=0; i<n; i++) slot[i] = 0;
for (i=0; i<n; i++)
{ for (j=min(n, arr[i].dead)-1; j>=0; j--)
{ if (slot[j]==0)
{ result[j] = i; slot[j] = 1; break;
}
}
}
for (i=0; i<n; i++) if (slot[i]) cout<<arr[result[i]].id<<" ";
}
}; int main()
{ clrscr();
JobSchedule js;
Job arr[50]; int i,n;
cout<<"Please Enter Number of Jobs: "; cin>>n;
cout<<"Please Enter JobID, Deadline and Profit of Job"<<endl; for(i=0;i<n;i++)
{ cout<<"Job ID: "; cin>>arr[i].id; cout<<"Deadline: "; cin>>arr[i].dead; cout<<"Profit: "; cin>>arr[i].profit;
}
cout<<"\nFollowing is maximum profit sequence of jobs\n"<<endl; js.printJobScheduling(arr, n); getch(); return 0;
}
OUTPUT:
Please Enter Number of Jobs: 5
Please Enter JobID, Deadline and Profit of Job
Job ID: a
Deadline: 2
Profit: 100
Job ID: b
Deadline: 1
Profit: 19
Job ID: c
Deadline: 2
Profit: 27
Job ID: d
Deadline: 1
Profit: 25
Job ID: e
Deadline: 3
Profit: 15 Following is maximum profit sequence of jobs c a e
03: Comparative Analysis of the Bubble Sort and Selection Sort by using Divide and Conquer Algorithm.
#include<iostream.h>
#include<conio.h> class SelBubSort { public:
void accept(int arr[], int s); void display(int arr[], int s); void ssort(int arr[], int s); void bsort(int arr[],int s);
};
void SelBubSort::accept(int arr[], int s)
{ for(int i=0;i<s;i++)
{ cout<<"Enter element "<<i+1<<":"; cin>>arr[i];
}
}
void SelBubSort::display(int arr[], int s)
{ cout<<"The elements of the array are:\n"; for(int i=0;i<s;i++) cout<<arr[i]<<" ";
}
void SelBubSort::ssort(int arr[], int s)
{ int i,j,temp,small; for(i=0;i<s-1;i++)
{ small=i; for(j=i+1;j<s;j++) if(arr[j]<arr[small]) small=j;
if(small!=i)
{ temp=arr[i]; arr[i]=arr[small]; arr[small]=temp;
}
}
}
void SelBubSort::bsort(int arr[],int s)
{ int i,j,temp; for(i=0;i<s-1;i++)
{ for(j=0;j<(s-1-i);j++) if(arr[j]>arr[j+1])
{ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp;
}
}
}
int main()
{
SelBubSort obj; int arr[100],n,choice; clrscr();
cout<<"Enter Size of Array: "; cin>>n; do { cout<<"\nMENU";
cout<<"\n1. Accept elements of Array"; cout<<"\n2. Display elements of Array";
cout<<"\n3. Sort the array using Selection Sort Method"; cout<<"\n4. Sort the array using Bubble Sort Method"; cout<<"\n5. Exit";
cout<<"\n\nEnter your choice 1-5: "; cin>>choice;
switch(choice)
{ case 1: obj.accept(arr,n); break;
case 2: obj.display(arr,n); break;
case 3: obj.ssort(arr,n); break;
case 4: obj.bsort(arr,n); break;
case 5: break;
default:cout<<"\nInvalid choice";
}
}while(choice!=5); return 0;
}
OUTPUT: Enter Size of Array: 10
MENU
1. Accept elements of Array
2. Display elements of Array
3. Sort the array using Selection Sort Method
4. Sort the array using Bubble Sort Method
5. Exit
Enter your choice 1-5: 1
Enter element 1:89
Enter element 2:56
Enter element 3:34
Enter element 4:23
Enter element 5:12
Enter element 6:76
Enter element 7:54
Enter element 8:98
Enter element 9:23
Enter element 10:11
MENU
1. Accept elements of Array
2. Display elements of Array
3. Sort the array using Selection Sort Method
4. Sort the array using Bubble Sort Method
5. Exit
Enter your choice 1-5: 2 The elements of the array are:
89 56 34 23 12 76 54 98 23 11
MENU
1. Accept elements of Array
2. Display elements of Array
3. Sort the array using Selection Sort Method
4. Sort the array using Bubble Sort Method
5. Exit
Enter your choice 1-5: 3
MENU
1. Accept elements of Array
2. Display elements of Array
3. Sort the array using Selection Sort Method
4. Sort the array using Bubble Sort Method
5. Exit
Enter your choice 1-5: 2 The elements of the array are:
11 12 23 23 34 54 56 76 89 98
MENU
1. Accept elements of Array
2. Display elements of Array
3. Sort the array using Selection Sort Method
4. Sort the array using Bubble Sort Method
5. Exit
Enter your choice 1-5: 5
04: The Median of two sorted arrays by using Divide and Conquer Algorithm.
#include<iostream.h>
#include<conio.h> class MedianArrays { public:
getMedian(int ar1[], int ar2[], int n);
};
int MedianArrays :: getMedian(int ar1[],int ar2[],int n)
{ int i=0; int j=0; int count; int m1=-1, m2=-1;
for(count=0;count<=n;count++)
{ if(i==n)
{ m1=m2; m2=ar2[0]; break;
}
else if(j==n)
{ m1=m2; m2=ar1[0]; break;
}
if(ar1[i]<ar2[j])
{ m1=m2; m2=ar1[i]; i++;
} else
{ m1=m2; m2=ar2[j]; j++;
}
}
return(m1+m2)/2;
} int main()
{
MedianArrays obj; int n1,n2,ar1[10],ar2[10]; clrscr();
cout<<"Enter Array Size for both arrays: "; cin>>n1; n2=n1;
cout<<"Enter First Array Elements: "<<endl; for(int i=0;i<n1;i++) cin>>ar1[i];
cout<<"Enter Second Array Elements: "<<endl; for(i=0;i<n2;i++) cin>>ar2[i];
cout<<"Median is "<<obj.getMedian(ar1, ar2, n1)<<endl; getch();
return 0;
}
OUTPUT:
Enter Array Size for both arrays: 5 Enter First Array Elements:
12
34
55
12
33 Enter Second Array Elements:
45
87
56
33
12
Median is 22 
05: The Merge Sort by using Divide and Conquer Algorithm.
#include<iostream.h>
#include<conio.h> class MergeSort { public:
void merge(int arr[], int l, int m, int r); void mergeSort(int arr[],int l,int r); void printArray(int A[],int size);
};
void MergeSort :: merge(int arr[],int l,int m,int r)
{ int i, j, k; int n1=m-l+1; int n2=r-m; int L[10],R[10]; for(i=0;i<n1;i++)
L[i]=arr[l+i]; for(j=0;j<n2;j++)
R[j]=arr[m+1+j]; i=0; j=0; k=l; while(i<n1&&j<n2)
{ if(L[i]<=R[j])
{ arr[k]=L[i]; i++;
} else { arr[k]=R[j]; j++;
} k++;
} while(i<n1)
{ arr[k]=L[i]; i++; k++;
} while(j<n2)
{ arr[k]=R[j]; j++; k++;
}
}
void MergeSort :: mergeSort(int arr[],int l,int r)
{ if(l<r)
{ int m=l+(r-l)/2; mergeSort(arr,l,m); mergeSort(arr,m+1,r); merge(arr,l,m,r);
}
}
void MergeSort :: printArray(int A[],int size)
{ int i; for(i=0;i<size;i++) cout<<A[i]<<" ";
cout<<endl;
} int main()
{
MergeSort obj; int arr[10]; int arr_size; clrscr(); cout<<"Enter size of Array: "; cin>>arr_size;
cout<<"Enter Array Elements: "<<endl; for(int i=0;i<arr_size;i++) cin>>arr[i]; cout<<"Given array is "<<endl;; obj.printArray(arr,arr_size); obj.mergeSort(arr,0,arr_size-1); cout<<"\nSorted array is \n"<<endl; obj.printArray(arr,arr_size); getch(); return 0;
}
OUTPUT:
Enter size of Array: 10 Enter Array Elements:
12
56
78
90
22
43
10
9
5
77
Given array is
12 56 78 90 22 43 10 9 5 77
Sorted array is
5 9 10 12 22 43 56 77 78 90
06: The Matrix Chain Multiplication Problem by using Dynamic Programming Algorithm.
#include<iostream.h>
#include<conio.h>
#include<limits.h> class MatrixChainMult { public: int MatrixChainOrder(int p[], int i, int j)
{ if(i == j) return 0;
int k; int min = INT_MAX; int count; for(k=i;k<j;k++)
{
count = MatrixChainOrder(p,i,k) +
MatrixChainOrder(p,k+1,j) + p[i-1]*p[k]*p[j]; if(count<min) min = count;
}
return min;
}
}; int main()
{
MatrixChainMult obj; clrscr(); int arr[10]; int m,n,i,a,b;
cout<<"Please Enter Number of Matrices: "; cin>>m; n=m+1; cout<<"Please Enter Number of rows and columns for every Matrix:
"<<endl; for(i=0;i<m;i++)
{ cout<<"Matrix "<<i+1<<" : "; cin>>a>>b; arr[i]=a;
} arr[i]=b;
cout<<"\nMinimum number of multiplications is :
"<<obj.MatrixChainOrder(arr, 1, n-1); getch(); return 0;
}
OUTPUT:
Please Enter Number of Matrices: 3 Please Enter Number of rows and columns for every Matrix:
Matrix 1 : 3 4
Matrix 2 : 4 5
Matrix 3 : 5 6
Minimum number of multiplications is : 150
