Design and Analysis Algorithms Lab

Program List


Quick Sort
Binary Search
Binary Tree Traversal
Prim's Algorithm
Strassen's Matrix Multiplication
Dijkstra's Algorithm
Knapsack Problem
Subset Sum Problem
Travelling Salesman Problem
Warshall's Algorithm











1 2 3 4 5 6 7 8 9 10
at 8:56 PM

Quick Sort




SOURCE CODE


#include”stdio.h”
#include”iostream.h”
#include”conio.h”
#include”iomanip.h”

class quick
{
private:
int elements[20],maxsize;
public:
void quicksort(int elements[20],int maxsize);
void sort(int elements[20],int left,int right);
};

void main()
{
int i,maxsize,elements[20];
clrscr();
cout < < "Enter The Number Of Elements : "; cin > > maxsize;
for(i=0;i <> > elements[i];
}
cout < < "Array Before Sorting \n"; cout < < "INDEX \t ELEMENT \n"; for(i=0;i < i="0;i" l="left;" r="right;" pivot="elements[left];"> =pivot)&&(left < pivot="left;" left="l;" right="r;"> pivot)
sort(elements,pivot+1,right);
}



at 8:55 PM

Binary Search






SOURCE CODE


#include”iostream.h”
#include”conio.h”

void binsearch(int ar[],int size,int ele)
{
int lb=0,ub=size-1,mid;
for(;lb < =ub;) { mid=(lb+ub)/2; if(ar[mid]==ele) { cout < < "\n SEARCH SUCCESSFULL"; break; } else if(ar[mid] < lb="mid+1;" ub="mid-1;" i="0;i" j="i+1;j"> ar[j])
{
temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}

void display(int ar[],int size)
{
cout < < "\n The Elements In Sorted Order Is \n"; for(int i=0;i < i="0;i"> > ar[i];
}
void main()
{
clrscr();
int size;
cout < < "Enter The Number Of Elements : "; cin > > size;
int *ar=new int(size);
cout < < "\n Enter The Elements Of The Array \n"; input(ar,size); sort(ar,size); int ele; display(ar,size); cout < < "\n Enter The Element To Be Found: "; cin > > ele;
binsearch(ar,size,ele);
getch();
}




OUTPUT

Enter The Number Of Elements : 5
Enter The Elements Of The Array
2
4
6
3
1

The Elements In Sorted Order Is
1
2
3
4
6
Enter The Element To Be Found: 1
SEARCH SUCCESSFULL
at 8:54 PM

Binary Tree Traversal





SOURCE CODE


#include”iostream.h”
#include”conio.h”
#include”stdio.h”
#include <>

struct node
{
int data;
node *left;
node *right;
};

node *tree=NULL;
node *insert(node *tree,int ele);
void preorder(node *tree);
void inorder(node *tree);
void postorder(node *tree);

void main()
{
clrscr();
int ch,ele;
do
{
clrscr();
cout < < "\n\t 1.INSERT A NODE IN BINARY TREE "; cout < < "\n\t 2.PREORDER TRAVERSAL"; cout < < "\n\t 3.INORDER TRAVERSAL"; cout < < "\n\t 4.POSTORDER TRAVERSAL "; cout < < "\n\t 5.EXIT"; cout < < "\n\n\t ENTER YOUR CHOICE: "; cin > > ch;

switch(ch)
{
case 1:
cout < < "\t ENTER THE ELEMENT: "; cin > > ele;
tree=insert(tree,ele);
break;

case 2:
cout < < "\n\t PREORDER TRAVERSAL \n"; preorder(tree); break; case 3: cout < < "\n\t INORDER TRAVERSAL \n"; inorder(tree); break; case 4: cout < < "\n\t POSTORDER TRAVERSAL \n"; postorder(tree); break; case 5: exit(0); } }while(ch!=5); } node *insert(node *tree,int ele) { static count=1; if(tree==NULL) { tree=new node; tree- > left=tree- > right=NULL;
tree- > data=ele;
count++;
}
else
{
if(count%2==0)
tree- > left=insert(tree- > left,ele);
else
tree- > right=insert(tree- > right,ele);
}
return (tree);
}

void preorder(node *tree)
{
if(tree!=NULL)
{
cout < < "\n " < <> data;
preorder(tree- > left);
preorder(tree- > right);
getch();
}
}

void inorder(node *tree)
{
if(tree!=NULL)
{
inorder(tree- > left);
cout < < "\n " < <> data;
inorder(tree- > right);
getch();
}
}

void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree- > left);
postorder(tree- > right);
cout < < "\n " < <> data;
getch();
}
}














OUTPUT:
1.INSERT A NODE IN BINARY TREE
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.EXIT
ENTER YOUR CHOICE: 1
ENTER THE ELEMENT: 4

1.INSERT A NODE IN BINARY TREE
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.EXIT
ENTER YOUR CHOICE: 1
ENTER THE ELEMENT: 3

1.INSERT A NODE IN BINARY TREE
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.EXIT
ENTER YOUR CHOICE: 1
ENTER THE ELEMENT: 5

1.INSERT A NODE IN BINARY TREE
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.EXIT
ENTER YOUR CHOICE: 2
PREORDER TRAVERSAL

4
3
5

1.INSERT A NODE IN BINARY TREE
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.EXIT
ENTER YOUR CHOICE: 3
INORDER TRAVERSAL
3
4
5



1.INSERT A NODE IN BINARY TREE
2.PREORDER TRAVERSAL
3.INORDER TRAVERSAL
4.POSTORDER TRAVERSAL
5.EXIT
ENTER YOUR CHOICE: 4
POSTORDER TRAVERSAL
3
5
4
at 8:53 PM

Prim's Algorithm

Page 1 2 3 4 5 6 7 8 9 10




SOURCE CODE



#include”iostream.h”
#include”stdio.h”
#include”conio.h”
#include”iomanip.h”
#define INFINITY 32767

class graph
{
char vertex[15],path[15];
int visited[15],w[15][15],dist[15],i,j,k,d;
public:
graph(int);
void create(int);
void spantree(int);
};
graph::graph(int n)
{
for(i=1;i < =n;i++) { path[i]=0; dist[i]=INFINITY; } } void graph::create(int v) { int n; char m; for(i=1;i < =v;i++) { cin > > vertex[i];
visited[i]=0;
for(j=1;j < =v;j++) w[i][j]=0; } for(i=1;i < =v;i++) { cout < < "\n No Of Adjecency For " < <> > n;
for(j=1;j < =n;j++) { cout < < "Adjecency " < <> > m;
cout < < "Distance Is : "; cin > > d;
for(k=1;k < =v;k++) { if(vertex[k]==m) w[i][k]=d; } } } for(i=1;i < =v;i++) { for(j=1;j < =v;j++) cout < < count="0;"> > source;
for(i=1;i < =n&&vertex[i]!=source;i++) if(i < i="1;i" dec="i;" i="1;i" min="INFINITY;" i="1;i" min="dist[i];" dec="i;" i="1;i" j="1;j" i="1;i"> > ch;
if(ch=='y'ch=='Y')
{
for(i=1;i < =n;i++) { visited[i]=0; dist[i]=INFINITY; path[i]=0; } count=0; goto source; } } void main() { int n; clrscr(); cout < < "\n Enter The Number Of Nodes: "; cin > > n;
graph x(n);
cout < < "\n Enter The Vertex' One By One: \n"; x.create(n); x.spantree(n); getch(); }

at 8:47 PM

Strassen's Matrix Multiplication


Page 1 2 3 4 5 6 7 8 9 10







SOURCE CODE

#include”iostream.h”
#include”conio.h”

class smm{
int a[2][2],b[2][2],c[2][2];
public:
void smm1();
void strmatmul();
};

void smm::smm1()
{
int i,j;
cout < < "Enter The Values Of A Matrix \n"; for(i=0;i < j="0;j"> > a[i][j];
cout < < "Enter The Values For B Matrix \n"; for(i=0;i < j="0;j"> > b[i][j];
}

void smm::strmatmul()
{
int m[25]={0},i,j;

m[1]=(a[0][0]+a[1][1])*(b[0][0]+b[1][1]);
m[2]=(a[1][0]+a[1][1])*b[0][0];
m[3]=a[0][0]*(b[0][1]-b[1][1]);
m[4]=a[1][1]*(b[1][0]-b[0][0]);
m[5]=(a[0][0]+a[0][1])*b[1][1];
m[6]=(a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
m[7]=(a[0][1]-a[1][1])*(b[1][0]+b[1][1]);

c[0][0]=m[1]+m[4]-m[5]+m[7];
c[0][1]=m[3]+m[5];
c[1][0]=m[2]+m[4];
c[1][1]=m[1]+m[3]-m[2]+m[6];


cout < < "\n STRASSEN'S MATRIX MULTIPLICATION \n"; for(i=0;i < j="0;j">


at 8:46 PM

Dijkstra's Algorithm




SOURCE CODE


#include”iostream.h”
#include”conio.h”
#include”iomanip.h”
#define MAX 10

class dijkstra
{
private:
int cost[MAX][MAX],d[MAX],p[MAX],visited[MAX],n;
public:
void readmatrix();
void shortpath(int);
void display(int);
};

void dijkstra::readmatrix()
{
int i,j;
cout < < "Enter The Number Of Vertices : "; cin > > n;
cout < < "Enter The Cost Matrix Of The Graph: "; for(i=1;i < =n;i++) for(j=1;j < =n;j++) cin > > cost[i][j];
}
void dijkstra::shortpath(int src)
{
int i,j,min,u,v;
for(i=1;i < =n;i++) { d[i]=cost[src][i]; visited[i]=0; p[i]=src; } visited[src]=1; for(i=1;i < =n;i++) { min=999; u=0; for(j=1;j < =n;j++) { if((!visited[j])&&(d[j]!=0)) if(d[j] < min="d[j];" u="j;" v="1;v" i="1;i" i="="src)" k="i;" k="p[k];"> > source;
dij.shortpath(source);
dij.display(source);
getch();
return 0;
}
at 8:45 PM

Knapsack Problem






SOURCE CODE

#include”iostream.h”
#include”stdio.h”
#include”conio.h”
void knapsack(int n,int w);
int n,i,w,W;
int weight[50],v[50],item[10];
int C[50][50];
void main()
{
clrscr();
cout < < "Enter The Number Of Items: ";
cin > > n;
cout < < "Enter capacity : ";
cin > > W;
cout < < "Enter Weights: ";
for(i=1;i < =n;i++)
cin > > weight[i];
cout < < "Enter Values \n";
for(i=1;i < =n;i++)
{
item[i]=0;
cin > > v[i];
}
knapsack(n,w);
getch();
}

void knapsack(int n,int w)
{
for(int c=0;c < =W;c++)
C[0][c]=0;
for(i=0;i < =n;i++)
C[i][0]=0;
for(i=1;i < =n;i++)
{
for(w=1;w < =n+1;w++)
if(weight[i] < =w)
if(v[i]+C[i-1][w-weight[i]] > C[i-1][w])
{
C[i][w]=v[i]+C[i-1][w-weight[i]];
item[i]=1;
}
else
C[i][w]=C[i-1][w];
else
C[i][w]=C[i-1][w];
}
for(i=0;i < =n;i++)
{
cout < < "\n";
for(w=0;w < =W;w++)
cout < < C[i][w] < < "\t";
}
cout < < "\n";
}

at 8:44 PM

Subset Sum Problem

Page 1 2 3 4 5 6 7 8 9 10


SOURCE CODE


#include”iostream.h”
#include”conio.h”
#include <>
#define MAX 10

class subset
{
private:
int n,exsetsum,set[MAX],selected[MAX];
public:
void readset();
void setsum();
};

void subset::readset()
{
int i;
cout < < "Enter the Number Of Elements In The Set : "; cin > > n;
cout < < "\n Enter The Elements Of The Set \n"; for(i=1;i < =n;i++) cin > > set[i];
cout < < "\n Enter The Expected Sum Of Subset : "; cin > > exsetsum;
}
void subset::setsum()
{
int i,j,no,sum,k,s;
no=pow(2,n);
cout < < "\n All Possible Subsets Whose Sums Is Equal Is " < < i="1;i" s="i;" sum="0;" j="1;j" k="1;"> 0)
{
if(s%2)
{
sum+=set[k];
selected[k]=1;
}
s=s/2;
k++;
}

if(sum==exsetsum)
{
for(j=1;j < =n;j++) if(selected[j]) cout < <>


at 8:41 PM

Travelling Salesman Problem




SOURCE CODE

#include”iostream.h”
#include”conio.h”
int a[10][10],visited[10],cost=0,n,min1;
void mincost(int city);
int least(int c)
{
int i,nc=999,min=999;
for(i=1;i < =n;i++) { if((a[c][i]!=0)&&(visited[i]==0)) if(a[c][i] < min="a[i][0]+a[c][i];" nc="i;" min1="a[c][i];" cost="min1;"> ";
ncity=least(city);
if(ncity==999)
{
ncity=0;
cout < <> > n;
cout < < "Enter The Cost Matrix \n"; for(i=0;i < j="0;j"> > a[i][j];
visited[i]=0;
}
}
cout < < "\n\n Starting From The City: "; mincost(0); cout < < "\n Minimum Cost Is :\t " < <>
at 8:21 PM

Warshall's Algorithm



SOURCE CODE


#include”iostream.h”
#include”conio.h”
#include”stdio.h”
#include <>
#define INFINITY 32768

class path
{
int n;
int p[10][10];
int p1[10][10];
int a[10][10];
int c[10][10];
public:
void get();
void pm();
void ap();
void disp();
};
void path::get()
{
int i,j,k;
clrscr();
cout < < "Enter The Number Of Vertices: "; cin > > n;
cout < < "Enter The Adjacency Matrix \n"; for(i=1;i < =n;i++) { for(j=1;j < =n;j++) { cout < < "a[" < <> > a[i][j];
p[i][j]=0;
}
}
cout < < "Enter The Cost Matrix \n"; for(i=1;i < =n;i++) { for(j=1;j < =n;j++) { cin > > c[i][j];
}
}
for(i=1;i < =n;i++) { for(j=1;j < =n;j++) { p[i][j]=a[i][j]; } } } void path::disp() { for(int i=1;i < =n;i++) { for(int j=1;j < =n;j++) { cout < < k="1;k" i="1;i" j="1;j" i="1;i" j="1;j" k="1;k" i="1;i" j="1;j">
at 8:20 PM
Subscribe to: Posts (Atom)