Design Analysis Algorithm Lab programming

 

 

 

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

#include<iostream.h>

#include<conio.h>

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;i<n;i++)

cin>>a[i];

}

void mergesort :: merge_sort(int p,int r)

{

int q;

if(p<r)

{

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;i<n;i++)

cout<<a[i];

}

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<iostream.h>

#include<conio.h>

#include<stdlib.h>

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<<" "<<c[i][j];

cout<<endl;

}

}

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<iostream.h>

#include<conio.h>

#include<iomanip.h>

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"<<i<<":";

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]<r[j+1])

{

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 : "<<profit;

}

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<iostream.h>

#include<conio.h>

#include<stdlib.h>

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"<<i<<"and"<<j<<":";

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<<p->i<<"-->"<<p->j<<endl;

}

p=p->link;

}

cout<<"\nThe cost is:"<<cost;

}

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

/ *5. BREADTH FIRST SEARCH */

#include<iostream.h>

#include<conio.h>

int a[10][10],visited[10],n;

void search_from1(int);

void main()

{

int i,j;

clrscr();

cout<<"\n Enter the number of nodes:";

cin>>n;

cout<<"\n Enter the adjancency matrix:\n";

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(i!=j)

{

cout<<"\nEnter the value of "<<i<<j<<”element”;

cin>>a[i][j];

}

cout<<"\n Nodes are visited in the order";

for(i=1;i<=n;i++)

if(visited[i]==0)

search_from1(i);

getch();

}

void search_from1(int z)

{

int i,j;

cout<<"-->"<<z;

visited[z]=1;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

if(visited[i]==0)

if(a[z][j]!=0)

search_from1(i);

break;

}

getch();

}

OUTPUT:

BREADTH FIRST SEARCH

Enter the number of nodes:4

Enter the adjancency matrix:

Enter the value of 12 element 1

Enter the value of 13 element 0

Enter the value of 14 element 0

Enter the value of 21 element 1

Enter the value of 23 element 0

Enter the value of 24 element 1

Enter the value of 31 element 1

Enter the value of 32 element 0

Enter the value of 34 element 0

Enter the value of 41 element 0

Enter the value of 42 element 1

Enter the value of 43 element 1

Nodes are visited in the order

-->1-->2-->3-->4

*6. DEPTH FIRST SEARCH * /

#include<iostream.h>

#include<conio.h>

int a[10][10],visited[10],n;

void search_from(int);

void main()

{

int i,j;

clrscr();

cout<<"\n Enter the number of nodes:";

cin>>n;

cout<<"\n Enter the adjancency matrix:\n";

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(i!=j)

{

cout<<"\nEnter the value of "<<i<<j<<” element”;

cin>>a[i][j];

}

cout<<"\n Nodes are visited in the order";

for(i=1;i<=n;i++)

if(visited[i]==0)

search_from(i);

getch();

}

void search_from(int k)

{

int i,j;

cout<<"-->"<<k;

visited[k]=1;

for(i=1;i<=n;i++)

if(visited[i]==0)

if(a[k][i]!=0)

search_from(i);

getch();

}

OUTPUT:

DEPTH FIRST SEARCH

Enter the number of nodes:5

Enter the adjancency matrix:

Enter the value of 12 element 0

Enter the value of 13 element 1

Enter the value of 14 element 0

Enter the value of 15 element 0

Enter the value of 21 element 0

Enter the value of 23 element 0

Enter the value of 24 element 0

Enter the value of 25 element 1

Enter the value of 31 element 0

Enter the value of 32 element 1

Enter the value of 34 element 1

Enter the value of 35 element 0

Enter the value of 41 element 0

Enter the value of 42 element 0

Enter the value of 43 element 0

Enter the value of 45 element 0

Enter the value of 51 element 0

Enter the value of 52 element 0

Enter the value of 53 element 0

Enter the value of 54 element 0

Nodes are visited in the order

-->1-->3-->2-->5-->4

/ *7. BINARY TREE TRAVERSAL */

#include<iostream.h>

#include<conio.h>

#include<malloc.h>

struct bnode

{

int data;

struct bnode *left,*right;

}*bt;

void create()

{

struct bnode *temp,*p,*pre;

int flag,key,d;

bt=NULL;

cout<<"\n \t Read the value until -1 to exit:\n\t ";

cin>>d;

while(d!=-1)

{

temp=(struct bnode *)(malloc(sizeof(struct bnode)));

temp->data=d;

temp->left=NULL;

temp->right=NULL;

if(bt==NULL)

bt=temp;

else

{

p=bt;

pre=bt;

while(p!=NULL)

{

key=p->data;

if(d<key)

{

flag=0;

pre=p;

p=p->left;

}

else if(d>key)

{

flag=1;

pre=p;

p=p->right;

}

}

if(flag==0)

pre->left=temp;

else

pre->right=temp;

}

cin>>d;

}

}

void preord(struct bnode *p)

{

if(p==NULL)

return;

cout<<"\t"<<p->data;

if(p->left!=NULL)

preord(p->left);

if(p->right)

preord(p->right);

}

void postord(struct bnode *p)

{

if(p==NULL)

return;

if(p->left)

postord(p->left);

if(p->right)

postord(p->right);

cout<<"\t"<<p->data;

}

void inord(struct bnode *p)

{

if(p==NULL)

return;

if(p->left)

inord(p->left);

cout<<"\t"<<p->data;

if(p->right)

inord(p->right);

}

void main()

{

clrscr();

create();

cout<<"\n\tINORDER TRAVERSAL\n\t";

inord(bt);

cout<<"\n\tPREORDER TRAVERSAL\n\t";

preord(bt);

cout<<"\n\tPOSTORDER TRAVERSAL\n\t";

postord(bt);

getch();

}

OUTPUT:

BINARY TREE TRAVERSAL

~~~~~~~~~~~~~~~~~~~~~~~~~~

Read the value until -1 to exit:

45 67 89 34 12 78 110 -1

INORDER TRAVERSAL

12 34 45 67 78 89 110

PREORDER TRAVERSAL

45 34 12 67 89 78 110

POSTORDER TRAVERSAL

12 34 78 110 89 67 45

/ *8. SHORTEST PATH * /

#include<iostream.h>

#include<conio.h>

void shortestpath(int ,int);

int graph,costs=32760,cost1,num,sor,dest,edge;

int from[20],to[20],cost[20],path[10];

void shortestpath(int graph,int z)

{

int temp,k=0,i=-1,p[10];

for(temp=z;temp<edge;temp++)

{

if(graph==from[temp])

{

p[k]=graph;

i++;

if(to[temp]==dest)

{

cost1=cost1+cost[temp];

if(cost1<costs)

{

costs=cost1;

for(z=0;z<=i;z++)

path[z]=p[z];

num=temp;

break;

}

}

else

{

graph=to[temp];

cost1=cost1+cost[temp];

k++;

}

}

}

}

void main()

{

int i,z,cost2;

clrscr();

cout<<"\n Enter the number of edge:";

cin>>edge;

cout<<"\nEnter the source:";

cin>>sor;

cout<<"\nEnter the destination";

cin>>dest;

cout<<"\nDestination"<<"\t\t"<<"Cost";

for(i=0;i<edge;i++)

{

cout<<"From";

cin>>from[i];

cout<<"\nTo";

cin>>to[i];

cout<<"\nCost";

cin>>cost[i];

}

for(i=0;i<edge;i++)

{

if(sor==from[i])

{

graph=to[i];

cost2=cost[i];

for(z=i;z<edge;z++)

{

if(graph==from[z])

{

cost1=cost2;

shortestpath(graph,z);

}

else if(graph==dest)

{

cost1=cost2;

if(cost1<costs)

{

costs=cost1;

num=0;

break;

}

}

}

}

}

cout<<"Cost:"<<costs;

cout<<"Path:"<<sor;

for(z=0;z<num;z++)

cout<<"->"<<path[z];

cout<<"->"<<dest;

getch();

}

OUTPUT:

SHORTEST PATH

Enter the number of edge: 3

Enter the source: 1

Enter the destination: 3

Source Destination Cost

From1

To2

Cost7

From1

To5

Cost7

From1

To3

Cost78

Cost: 78, Path: 1->3

/* 9.QUEENS PROBLEM USING BACKTRACKING */

#include<iostream.h>

#include<conio.h>

#include<math.h>

#include<process.h>

#include<graphics.h>

class queen

{

int n,x[100];

public:

queen();

void nqueen(int,int);

int place(int,int);

};

queen::queen()

{

int k=1;

textcolor(GREEN);

cprintf("Enter the number of queens:");

cin>>n;

nqueen( k, n);

}

void queen::nqueen(int k,int n)

{

for(int i=1;i<=n;i++)

{

if(place(k,i))

{

x[k]=i;

clrscr();

if(k==n)

{

for(int j=1;j<=n;j++)

{textcolor(x[j]);

gotoxy(1,j);

cprintf("queen %d : %d",j,x[j]);

}

getch();

break;

}

else

nqueen(k+1,n);

}

}

return;

}

int queen::place(int k,int i)

{

int j;

for(j=1;j<=k;j++)

{

if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))

return 0;

}

return 1;

}

void main()

{

clrscr();

queen q;

}

OUTPUT:

/* QUEENS PROBLEM USING BACKTRACKING */

Enter the number of queens: 8

queen 1: 1

queen 2: 5

queen 3 : 8

queen 4 : 6

queen 5 : 3

queen 6 : 7

queen 7 : 2

queen 8 : 4

queen 1: 8

queen 2: 4

queen 3: 1

queen 4: 3

queen 5: 6

queen 6: 2

queen 7: 7

queen 8: 5

/*10. KNAPSACK USING BACKTRACKING */

#include<iostream.h>

#include<conio.h>

class knapsack

{

int m,n,w[10],p[10],fw,fp,x[10],y[10],b,c;

float r[10];

int bound(int,int,int);

public:

knapsack();

void bknap(int,int,int);

void display();

};

knapsack::knapsack()

{

fp=-1;

cout<<"\n Enter the no of items:";

cin>>n;

cout<<"\n Enter the capacity of the bag:";

cin>>m;

for(int i=1;i<=n;i++)

{

a:cout<<"\n Enter the weight and profit for the item "<<i<<":";

cin>>w[i]>>p[i];

r[i]=(float)p[i]/w[i];

if(i!=1)

if(r[i-1]<r[i])

{

cout<<"\n This entry is not valid \n";

goto a;

}

}

}

void knapsack::display()

{

cout<<"\n\n The selected items are \n\n";

for(int i=1;i<=n;i++)

cout<<" "<<i;

cout<<endl;

for(int j=1;j<=n;j++)

cout<<" "<<"**";

cout<<endl;

for(i=1;i<=n;i++)

cout<<" "<<x[i];

cout<<"\n\n Final weight="<<fw;

cout<<"\n\n Final profit="<<fp;

}

void knapsack::bknap(int k,int cp,int cw)

{

if(cw+w[k]<=m)

{

y[k]=1;

if(k<n)bknap(k+1,cp+p[k],cw+w[k]);

if(((cp+p[k])>fp)&&(k==n))

{

fp=cp+p[k];

fw=cw+w[k];

for(int j=1;j<=k;j++)

x[j]=y[j];

}

}

if(bound(cp,cw,k)>=fp)

{

y[k]=0;

if(k<n)bknap(k+1,cp,cw);

if((cp>fp)&&(k==n))

{

fp=cp;

fw=cw;

for(int j=1;j<=k;j++)

x[j]=y[j];

}

}

}

int knapsack::bound(int cp,int cw,int k)

{

b=cp;

c=cw;

for(int i=k+1;i<=n;i++)

{

c=c+w[i];

if(c<m)

b=b+p[i];

else return(b+(1-(c-m)/w[i])*p[i]);

}

return b;

}

void main()

{

clrscr();

cout<<"\n\t\t\t KNAPSACK USING BACKTRACKING";

cout<<"\n\t\t\t ***************************";

knapsack ob;

int k=1,cp=0,cw=0;

ob.bknap(k,cp,cw);

ob.display();

getch();

}

OUTPUT:

KNAPSACK USING BACKTRACKING

**********************************

Enter the no of items: 8

Enter the capacity of the bag: 110

Enter the weight and profit for the item 1:1 11

Enter the weight and profit for the item 2:11 21

Enter the weight and profit for the item 3:21 31

Enter the weight and profit for the item 4:23 33

Enter the weight and profit for the item 5:33 43

Enter the weight and profit for the item 6:43 53

Enter the weight and profit for the item 7:45 55

Enter the weight and profit for the item 8:55 65

The selected items are

1 2 3 4 5 6 7 8

** ** ** ** ** ** ** **

1 1 1 0 1 1 0 0

Final weight=109

Final profit=159