design analysis and algorithm

/ *5. BREADTH FIRST SEARCH */


#include
#include
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 "<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<<"-->"<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
#include

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 "<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<<"-->"<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
#include
#include

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{
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"<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"<data;

}







void inord(struct bnode *p)
{
if(p==NULL)
return;

if(p->left)
inord(p->left);
cout<<"\t"<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
#include

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{
if(graph==from[temp])
{
p[k]=graph;
i++;
if(to[temp]==dest)
{
cost1=cost1+cost[temp];
if(cost1{
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{
cout<<"From";
cin>>from[i];
cout<<"\nTo";
cin>>to[i];
cout<<"\nCost";
cin>>cost[i];
}
for(i=0;i{
if(sor==from[i])
{
graph=to[i];
cost2=cost[i];
for(z=i;z{
if(graph==from[z])
{
cost1=cost2;
shortestpath(graph,z);
}
else if(graph==dest)
{
cost1=cost2;
if(cost1{
costs=cost1;
num=0;
break;
}
}
}
}
}
cout<<"Cost:"<cout<<"Path:"<for(z=0;zcout<<"->"<cout<<"->"<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
#include
#include
#include
#include

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
#include

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 "<cin>>w[i]>>p[i];
r[i]=(float)p[i]/w[i];
if(i!=1)
if(r[i-1]{
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<<" "<cout<for(int j=1;j<=n;j++)
cout<<" "<<"**";
cout<for(i=1;i<=n;i++)
cout<<" "<cout<<"\n\n Final weight="<cout<<"\n\n Final profit="<}

void knapsack::bknap(int k,int cp,int cw)
{
if(cw+w[k]<=m)
{
y[k]=1;
if(kif(((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(kif((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(cb=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

Read More

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

Read More