design analysis and algorithm

/*1. MERGE SORT USING DIVIDE AND CONQUER METHOD */

#include
#include

class mergesort
{
int a[20];
void merge(int,int,int);
public:
void create(int);
void merge_sort(int,int);
void print(int);
};

void mergesort :: create(int n)
{
int i;
cout<<"\n Enter the array elements\n";
for(i=0;icin>>a[i];
}

void mergesort :: merge_sort(int p,int r)
{
int q;
if(p{
q=((p+r)/2);
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}

void mergesort :: merge(int x,int y,int z)
{
int n1=y-x+1,n2=z-y,i,j,k,l[20],r[20];
for(i=1;i<=n1;i++)
l[i]=a[x+i-1];
for(j=1;j<=n2;j++)
r[j]=a[y+j];
l[n1+1]=999;
r[n2+1]=999;
i=j=1;
for(k=x;k<=z;k++)
{
if(l[i]<=r[j])
{
a[k]=l[i];
i=i+1;
}
else
{
a[k]=r[j];
j=j+1;
}
}
}

void mergesort :: print(int n)
{
int i;
cout<<"\n After sorting the elements are \n";
for(i=0;icout<}

void main()
{
int l,n,r;
mergesort ob;
clrscr();
cout<<"\n\t\t\t merge sort";
cout<<"\n\t\t\t ~~~~~~~~~~~";
cout<<"\n Enter the size of the array:";
cin>>n;
ob.create(n);
l=0;
r=n-1;
ob.merge_sort(l,r);
ob.print(n);
getch();
}











OUTPUT:


MERGE SORT
~~~~~~~~~~~


Enter the size of the array: 5

Enter the array elements
77
88
99
45
22

After sorting the elements are

22
45
77
88
99
/*2. STRASSEN’S MATRIX MULTIPLICATION */

#include
#include
#include

class strassen
{
int a[2][2],b[2][2],c[2][2];
public:
void product()
{
int q1,q2,q3,q4,q5,q6,q7;
q1=(a[1][1]+a[2][2])*(b[1][1]+b[2][2]);
q2=(a[2][1]+a[2][2])*b[1][1];
q3=a[1][1]*(b[1][2]-b[2][2]);
q4=a[2][2]*(-b[1][1]+b[2][1]);
q5=(a[1][1]+a[1][2])*b[2][2];
q6=(-a[1][1]+a[2][1])*(b[1][1]+b[1][2]);
q7=(a[1][2]-a[2][2])*(b[2][1]+b[2][2]);
c[1][1]=q1+q4-q5+q7;
c[1][2]=q3+q5;
c[2][1]=q2+q4;
c[2][2]=q1+q3-q2+q6;
}

void read();
void display();
};

void strassen :: read()
{
cout<<"\n Enter the matrix A elements\n";
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
cin>>a[i][j];
cout<<"\n Enter the matrix B elements \n";
for(i=1;i<=2;i++)
for(j=1;j<=2;j++)
cin>>b[i][j];
}

void strassen::display()
{
cout<<"\n The product of the matrix is \n";
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
{
cout<<" "<cout<}
}

void main()
{
strassen ob;
clrscr();
cout<<"\n\t\t\t MATRIX MULTIPLICATION";
cout<<"\n\t\t\t ~~~~~~~~~~~~~~~~~~~~~~";
ob.read();
ob.product();
ob.display();
getch();
}

OUTPUT:
MATRIX MULTIPLICATION
~~~~~~~~~~~~~~~~~~~~~~
Enter the matrix A elements
1 2
3 4

Enter the matrix B elements
5 6
7 8

The product of the matrix is
19 22
43 50

/ *3. KNAPSACK USING GREEDY METHOD * /

#include
#include
#include

class knapsack
{
float w[10],p[10],profit,r[10],t;
int m,n,i,j,k;
public:
knapsack();
void sort();
void calc();
};


knapsack::knapsack()
{
clrscr();
cout<<"\n\t\t\tKNAPSACK PROBLEM";
cout<<"\n\t\t\t----------------";
cout<<"\n\nEnter the capacity of the bag";
cin>>m;
cout<<"\nEnter the no. of items";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"\nEnter the weight and profit of items"<cin>>w[i]>>p[i];
r[i]=(float)p[i]/w[i];
}
profit=0.0;
}

void knapsack::sort()
{
for(i=1;i<=n;i++)
for(j=1;j<=n-1;j++)
{
if(r[j]{
t=r[j];
r[j]=r[j+1];
r[j+1]=t;
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
}
}
}

void knapsack::calc()
{
for(i=1;i<=n;i++)
{
if(w[i]<=m)
{
m=m-w[i];
profit=profit+p[i];
}
else
{
profit=profit+(p[i]/w[i])*m;
break;
}
}
cout<<"Profit is : "<}
void main()
{
knapsack k;
k.sort();
k.calc();
getch();
}

OUTPUT:
KNAPSACK PROBLEM
*********************

Enter the capacity of the bag: 20

Enter the no. of items:3

Enter the weight and profit of items1:18 25

Enter the weight and profit of items2:15 24

Enter the weight and profit of items3:1015
Profit is: 31.5

/ * 4. KRUSKAL’S MINIMUM SPANNING TREE * /

#include
#include
#include

class kruskal
{
int p1[20],rank[20];
struct graph
{
int c,i,j;
struct graph *link;
};
typedef struct graph node;
node *head,*p,*q;
int v,u,a[20][20],n,w[20][20],t,cnt,cost;
public:

void makeset(int);
int findset(int);
void uinion(int,int);
void link(int,int);
void sort();
kruskal();
}

kruskal::kruskal()
{
clrscr();
t=1;
cnt=1;
cost=0;
cout<<"\n\t\t\tKRUSKAL'S MINIMUM SPANNING TREE";
cout<<"\n\t\t\t*******************************";
cout<<"\n\nEnter the number of vertices:";
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=-1;
for(i=1;i<=n;i++)
makeset(i);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{



if((a[i][j]==-1)&&(i!=j))
{
cout<<"\n\nEnter the cost of the edge"<cin>>a[i][j];
a[j][i]=a[i][j];
if(t==1)
{
p=(node*)malloc(sizeof(node));
p->i=i;
p->j=j;
p->c=a[i][j];
p->link=NULL;
head=p;
t++;
}
else
{
q=(node*)malloc(sizeof(node));
q->i=i;
q->j=j;
q->c=a[i][j];
q->link=NULL;
p->link=q;
p=q;
cnt=cnt+1;
}
}
}
sort();
p=head;
t=1;
cout<<"\nThe minimum spanning tree is\n";


while(p!=NULL)
{
if(findset(p->i)!=findset(p->j))
{
uinion(p->i,p->j);
cost=cost+p->c;
cout<i<<"-->"<j<}


p=p->link;
}
cout<<"\nThe cost is:"<}
void kruskal::sort()
{
for(int i=1;i<=cnt;i++)
{
p=head;
for(int j=1;j<=cnt-i;j++)
{
if(p->c>p->link->c&&p->link!=NULL)
{
int t=p->c;
p->c=p->link->c;
p->link->c=t;
t=p->i;
p->i=p->link->i;
p->link->i=t;
t=p->j;
p->j=p->link->j;
p->link->j=t;
p=p->link;
}
else p=p->link;
}
}
}

void kruskal::makeset(int x)
{
p1[x]=x;
rank[x]=0;
}


void kruskal::uinion(int x,int y) //adding to the list
{
link(findset(x),findset(y));
}


void kruskal::link(int x,int y) //checking for cyclic
{
if(rank[x]>rank[y])
p1[y]=x;
else p1[x]=y;
if(rank[x]==rank[y])
rank[y]=rank[y]+1;
}

int kruskal::findset(int x) //path compression
{
if(x!=p1[x])
p1[x]=findset(p1[x]);
return p1[x];
}

void main() //main program
{
kruskal k;
getch();
}

OUTPUT:


KRUSKAL'S MINIMUM SPANNING TREE
***************************************

Enter the number of vertices:4


Enter the cost of the edge1and2:5


Enter the cost of the edge1and3:10


Enter the cost of the edge1and4:999


Enter the cost of the edge2and3:999


Enter the cost of the edge2and4:15


Enter the cost of the edge3and4:20

The minimum spanning tree is
1-->2
1-->3
2-->4

The cost is:30