/* Write a C++ program that uses dynamic programming algorithm to solve the optimal binary search tree problem */

#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
#define MAX 10
int find(int i,int j);
void print(int,int);
int p[MAX],q[MAX],w[10][10],c[10][10],r[10][10],i,j,k,n,m;
char idnt[7][10];
 
main()
{
cout << "enter the no, of identifiers";
cin >>n;
cout <<"enter identifiers";
for(i=1;i<=n;i++)
gets(idnt[i]);
cout <<"enter success propability for identifiers";
for(i=1;i<=n;i++)
cin >>p[i];
cout << "enter failure propability for identifiers";
for(i=0;i<=n;i++)
cin >> q[i];
for(i=0;i<=n;i++)
{
w[i][i]=q[i];
c[i][i]=r[i][i]=0;
w[i][i+1]=q[i]+q[i+1]+p[i+1];
r[i][i+1]=i+1;
c[i][i+1]=q[i]+q[i+1]+p[i+1];
}
w[n][n]=q[n];
r[n][n]=c[n][n]=0;
for(m=2;m<=n;m++)
{
for(i=0;i<=n-m;i++)
{
[...]

/* Write a C++ program to implement dynamic programming algorithm to solve the all pairs shortest path problem */

#include<iostream>
#include<conio.h>
using namespace std;
int min(int a,int b);
int cost[10][10],a[10][10],i,j,k,c;
 
main()
{
int n,m;
cout <<"enter no of vertices";
cin >> n;
cout <<"enter no od edges";
cin >> m;
cout<<"enter the\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin>>i>>j>>c;
a[i][j]=cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]== 0 && i [...]

/* Write C++ program that uses non-recursive functions to traverse a binary tree in Post-order */

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
 
class node
{
public:
class node *left;
class node *right;
int data;
};
 
class tree: public node
{
public:
int stk[50],top;
node *root;
tree()
{
root=NULL;
top=0;
}
void insert(int ch)
{
node *temp,*temp1;
if(root== NULL)
{
root=new node;
root->data=ch;
root->left=NULL;
root->right=NULL;
return;
}
temp1=new node;
temp1->data=ch;
temp1->right=temp1->left=NULL;
temp=search(root,ch);
if(temp->data>ch)
temp->left=temp1;
else
temp->right=temp1;
 
}
node *search(node *temp,int ch)
{
if(root== NULL)
{
cout <<"no node present";
return NULL;
}
if(temp->left==NULL && temp->right== NULL)
return temp;
 
if(temp->data>ch)
{ if(temp->left==NULL) return temp;
search(temp->left,ch);}
else
[...]

/* Write C++ program that uses non-recursive functions to traverse a binary tree in In-order */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *left;
class node *right;
int data;
};
 
class tree: public node
{
public:
int stk[50],top;
node *root;
tree()
{
root=NULL;
top=0;
}
void insert(int ch)
{
node *temp,*temp1;
if(root== NULL)
{
root=new node;
root->data=ch;
root->left=NULL;
root->right=NULL;
return;
}
temp1=new node;
temp1->data=ch;
temp1->right=temp1->left=NULL;
temp=search(root,ch);
if(temp->data>ch)
temp->left=temp1;
else
temp->right=temp1;
 
}
 
node *search(node *temp,int ch)
{
if(root== NULL)
{
cout <<"no node present";
return NULL;
}
if(temp->left==NULL && temp->right== NULL)
return temp;
 
if(temp->data>ch)
{ if(temp->left==NULL) return [...]

/* Write C++ program that uses non-recursive functions to traverse a binary tree in Pre-order */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *left;
class node *right;
int data;
};
 
class tree: public node
{
public:
int stk[50],top;
node *root;
tree()
{
root=NULL;
top=0;
}
void insert(int ch)
{
node *temp,*temp1;
if(root== NULL)
{
root=new node;
root->data=ch;
root->left=NULL;
root->right=NULL;
return;
}
temp1=new node;
temp1->data=ch;
temp1->right=temp1->left=NULL;
temp=search(root,ch);
if(temp->data>ch)
temp->left=temp1;
else
temp->right=temp1;
 
}
 
node *search(node *temp,int ch)
{
if(root== NULL)
{
cout <<"no node present";
return NULL;
}
if(temp->left==NULL && temp->right== NULL)
return temp;
 
if(temp->data>ch)
{ if(temp->left==NULL) return [...]

/* Write a C++ program to solve the single source shortest path problem using Dijkstra’s algorithm */

#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
int shortest(int ,int);
int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p;
main()
{
int c;
cout <<"enter no of vertices";
cin >> n;
cout <<"enter no of edges";
cin >>m;
cout <<"\nenter\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin >> i >> j >>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
cout <<"enter initial vertex";
cin >>v;
cout << v<<"\n";
shortest(v,n);
}
 
int shortest(int v,int n)
{
int min;
for(i=1;i<=n;i++)
{
S[i]=0;
dist[i]=cost[v][i];
}
path[++p]=v;
S[v]=1;
dist[v]=0;
for(i=2;i<=n-1;i++)
{
k=-1;
min=31999;
for(j=1;j<=n;j++)
{
if(dist[j]<min && S[j]!=1)
{
min=dist[j];
k=j;
} [...]

/* Write C++ programs to implement the Kruskal’s algorithm to generate a minimum cost spanning tree */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
 
main()
{
int dup1,dup2;
cout<<"enter no of vertices";
cin >> n;
cout <<"enter no of edges";
cin >>m;
cout <<"EDGE Cost";
for(k=1;k<=m;k++)
{
cin >>i >>j >>c;
cost[i][j]=c;
cost[j][i]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
visit=1;
while(visit<n)
{
v=31999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]!=31999 && cost[i][j]<v && cost[i][j]!=-1 )
{
int count =0;
for(p=1;p<=n;p++)
{
if(visited[p]==i || visited[p]==j)
count++;
}
if(count >= 2)
{
for(p=1;p<=n;p++)
if(cost[i][p]!=31999 && p!=j)
dup1=p;
for(p=1;p<=n;p++)
if(cost[j][p]!=31999 && p!=i)
dup2=p;
 
if(cost[dup1][dup2]==-1)
continue;
}
l=i;
k=j;
v=cost[i][j];
}
cout <<"edge from " [...]

/* Write C++ programs to implement the Prim’s algorithm to generate a minimum cost spanning tree */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u;
 
main()
{
int m,c;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES Cost\n";
for(k=1;k<=m;k++)
{
cin >>i>>j>>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
 
cout <<"ORDER OF VISITED VERTICES";
k=1;
while(k<n)
{
m=31999;
if(k==1)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(cost[i][j]<m)
{
m=cost[i][j];
u=i;
}
}
else
{
for(j=n;j>=1;j–)
if(cost[v][j]<m && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
m=cost[v][j];
u=j;
}
}
cost[v][u]=31999;
v=u;
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}

OUTPUT
enterno of vertices7
ente no of edges9
EDGES Cost
1 6 10
6 [...]

/* Write C++ programs for the implementation of Depth-first search(DFS) for a given graph */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];
 
main()
{
int m;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES \n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}
 
cout <<"enter initial vertex";
cin >>v;
cout <<"ORDER OF VISITED VERTICES";
cout << v <<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n;j>=1;j–)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
}
v=stk[–top];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}

OUTPUT
enterno of vertices9
ente [...]

/* Write C++ programs for the implementation of BFS for a given graph */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];
 
main()
{
int m;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES \n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}
 
cout <<"enter initial vertex";
cin >>v;
cout <<"Visitied vertices\n";
cout << v;
visited[v]=1;
k=1;
while(k<n)
{
for(j=1;j<=n;j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
qu[rare++]=j;
}
v=qu[front++];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}

OUTPUT
enterno of vertices9
ente no of edges9
EDGES
1 2
2 3
1 [...]