This is default featured slide 2 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

This is default featured slide 3 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

This is default featured slide 4 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

This is default featured slide 5 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.

Showing posts with label daa. Show all posts
Showing posts with label daa. Show all posts

Monday, February 7, 2011

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

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