Submitted By :
B. Tech (IT) 4th sem
Aim : Program
to find longest common
subsequence
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
void print(int,int);
char x[10],y[10];
int b[10][10];
void main()
{
int
m,n,i,j,c[10][10];
clrscr();
cout<<"Enter the length of first
sequence:=";
fflush(stdin);
cin>>m;
cout<<"Enter the first
sequence:=\n";
for(i=1;i<=m;i++)
{
fflush(stdin);
cin>>x[i];
}
cout<<"Enter
the length of second sequence:=";
fflush(stdin);
cin>>n;
cout<<"Enter the second
sequence:=\n";
for(i=1;i<=n;i++)
{
fflush(stdin);
cin>>y[i];
}
for(i=1;i<=m;i++)
{
c[i][0]=0;
}
for(j=0;j<=n;j++)
{
c[0][j]=0;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=10;
}
else
if(c[i-1][j]>=c[i][j-1])
{
b[i][j]=20;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=30;
}
}
}
cout<<"The longest common
subsequence is:";
print(m,n);
getch();
}
void print(int i,int j)
{
if(i==0||j==0)
{
return;
}
if(b[i][j]==10)
{
print(i-1,j-1);
cout<<x[i];
}
else
if(b[i][j]==20)
{
print(i-1,j);
}
else
print(i,j-1);
}
OUTPUT
Enter the length of first sequence:=4
Enter the first sequence:=acda
Enter the length of second sequence:=6
Enter the second sequence:=
xghtac
The longest common subsequence is: ac
AIM: - WAP To
Implement Shortest Path Using Dijkastra’s Algorithm.
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void
main()
{
int
g[20][20],s[15],path[20],mark[20];
int
n, source,i,j,u,pred[20];
int
count=0;
int
min(int a[],int m[],int k);
void
printpath(int,int,int[]);
clrscr();
cout<<"Enter
the no. of vertices:\t";
cin>>n;
if(n<=0)
{
cout<<"This
is meaningless";
exit(1);
}
cout<<"\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"Enter
the cost of vertex
between\t"<<i<<"\tand\t"<<j<<":\t";
cin>>g[i][j];
}
}
cout<<"\nEnter
the source vertex:\t";
cin>>source;
cout<<"\nFollowing
are the shortest paths from source vertex: "<<"\n";
for(j=1;j<=n;j++)
{
mark[j]=0;
path[j]=999;
pred[j]=0;
}
path[source]=0;
while(count<n)
{
u=min(path,mark,n);
s[++count]=u;
mark[u]=1;
for(i=1;i<=n;i++)
{
if(g[u][i]>0)
{
if(mark[i]!=1)
{
if(path[i]>path[u]+g[u][i])
{
path[i]=path[u]+g[u][i];
pred[i]=u;
}
}
}
}
}
for(i=1;i<=n;i++)
{
printpath(source,i,pred);
if(path[i]!=999)
cout<<"(
"<<path[i]<<" )\n";
}
getch();
}
int
min(int a[],int m[],int k)
{
int
mi=999;
int
i,t;
for(i=1;i<=k;i++)
{
if(m[i]!=1)
{
if(mi>=a[i])
{
mi=a[i];
t=i;
}
}
}
return
t;
}
void
printpath(int x,int i,int p[])
{
cout<<"\n";
if(i==x)
{
cout<<x;
}
else
if(p[i]==0)
{ cout<<"There is no path from
"<<x<<" to "<<i;
}
else
{printpath(x,p[i],p);
cout<<"........."<<i;
}}
OUTPUT
Enter
the no. of vertices: 3
Enter
the cost of vertex between 1 and 1:
2
Enter
the cost of vertex between 1 and 2:
3
Enter
the cost of vertex between 1 and 3:
9
Enter
the cost of vertex between 2 and 1:
54
Enter
the cost of vertex between 2 and 2:
32
Enter
the cost of vertex between 2 and 3:
67
Enter
the cost of vertex between 3 and 1:
6
Enter
the cost of vertex between 3 and 2: 1
Enter
the cost of vertex between 3 and 3:
81
Enter
the source vertex: 3
Following
are the shortest paths from source vertex:
3.........1(6)
3.........2(1)
3.........3(0)
AIM : To find the complexity in finding the median
of given elements
#include<iostream.h>
#include<time.h>
#include<conio.h>
void sort (int arr[],int num)
{ int
temp=0;
for(int i=0;i<num;i++)
{ for(int
j=0;j<(num-1);j++)
{ if(arr[j]>arr[j+1])
{ temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
} } }
return; }
void main()
{
clrscr();
int a[50],b[10],med[10];
int n,m,i,j;
int k=0;
clock_t start,end;
cout<<"enter the no elements";
cin>>n;
for(i=0;i<n;i++)
{ cin>>a[i]; }
Start=clock();
for(i=0;i<n;i++)
{ for(j=0;j<5;j++)
{ b[j]=a[i];
i++; }
i--;
sort(b,5);
med[k]=b[2];
k++;
m=m+1;
}
sort(med,m);
delay(100);
end=clock();
cout<<"the final median is"<<endl;
if(m%2!=0)
cout<<med[(m/2)];
else
cout<<med[(m/2)]<<"and"<<med[(m/2+1)];
cout<<”Time complexity:”<<((end-start)/CLK_TCK);
getch();
return;
}
OUTPUT
Enter the no of elements :9
5
9
7
2
8
4
3
1
6
Final median is : 5
Time complexity :0.10989
AIM
: TO FIND COMPLEXITY OF MERGE SORT TECHNIQUE
#include<iostream.h>
#include<conio.h>
#include<dos.h>
#include<time.h>
void merge(int a[], int p, int q, int r1)
{
int n1=q-p+1;
int n2=r1-q;
int l[20],r[20];
for(i=0;<n1;i++)
{ l[i]=a[p+i];}
For(j=0;j<n2;j++)
{ r[j]=a[q+j+1];}
l[n1+1]=999999;
r[n2+1]=999999;
for(int k=p;k<=r1;k++0
{
if(l[i]<=r[j])
if(l[i]<=r[j])
{a[k]=l[i]; i++;}
else
{a[k]=r[j];j++;}
}
}
void mergesort(int a[], int p, int r)
{
int q;
if(q<r)
{
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
}
}
void
main()
{
int
a[20],i,j,n;
clock_t
start,end;
cout<<"enter
array size :";cin>>n;
cout<<”\n
enter elements:”;
for(i=0;i<n;i++)
{ cin>>a[i];}
start=clock();
mergesort(a,0,n);
delay(100);
end=clock();
cout<<"\n\n";
cout<<”\n\nSorted array:”;
for(i=0;i<n;i++)
{cout<<a[i];}
cout<<"\n\n COMPLEXITY
:"<<(end-start)/CLK_TCK;
getch();
}
Output
Enter
the size of array :5
Enter
elements :2
9
7
5
0
Sorted array : 0
2
5
7
9
COMPLEXITY: 0.1098
AIM
: To find the complexity of linear
search and binary search
#include<iostream.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
void
main()
{
clrscr();
clock_t start,end;
int ch;
int arr[10];
cout<<"\n Enter choice ";
cout<<"\n 1. Binary search ";
cout<<"\n 2. Linear Search
\n";
cin>>ch;
switch(ch)
{
case 1 :
int no1,lb,ub,mid,item1,pos1=-1;
cout<<"\n Enter the no. of
elements in the array(not exceeding 10)";
cin>>no1;
lb=0;
ub=no1;
mid=(lb+ub)/2;
cout<<"\n Enter the array(sorted
order) ";
for(int i=0;i<no1;i++)
{
cout<<"\n"<<i+1<<" ";
cin>>arr[i];
}
cout<<"\n Entered array ";
for(i=0;i<no1;i++)
{
cout<<" "<<arr[i];
}
cout<<"\n Enter item to be
searched ";
cin>>item1;
start=clock();
while(lb<=ub)
{
mid=(lb+ub)/2;
if(arr[mid]==item1)
{
pos1=mid;
break;
}
else if(arr[mid]>item1)
{
ub=mid-1;
}
else
{
lb=mid+1;
}
}
delay(100);
end=clock();
if(pos1==-1)
{
cout<<"\n Element not found ";
}
else
{
cout<<"\n Element found at
position "<<pos1+1;
}
cout<<"\n Time complexity
"<<(end-start)/CLK_TCK;
break;
case 2 :
int pos2=-1,no2,item2;
cout<<"\n Enter number if elements
on array(not exceeding 10) ";
cin>>no2;
cout<<"\n Enter array ";
for(i=0;i<no2;i++)
{
cout<<"\n"<<i+1<<" ";
cin>>arr[i];
}
for(i=0;i<no2;i++)
{
cout<<" "<<arr[i];
}
cout<<"\n Enter item to be
searched ";
cin>>item2;
start=clock();
for(i=0;i<no2;i++)
{
if(item2==arr[i])
{
pos2=i;
break;
}
}
delay(100);
end=clock();
if(pos2==-1)
{
cout<<"\n Element not found
";
}
else
{
cout<<"\n Element found at
position "<<pos2;
}
cout<<"\n Time complexity
"<<(end-start)/CLK_TCK;
break;
}
getch();
}
OUTPUT
Enter
choice
1.BINARY
SEARCH
2.LINEAR
SEARCH
1
ENTER
THE NUMBER OF ELEMENTS ON ARRAY : 5
ENTER
SORTED ARRAY
2
4
5
7
8
ENTER
ELEMENT To BE SEARCHED: 7
ELEMENT
FOUND AT POSITION 4
TIME
COMPLEXIBILITY 0.10989
Enter
choice
1.BINARY
SEARCH
2.LINEAR
SEARCH
2
ENTER
THE NUMBER OF ELEMENTS ON ARRAY : 4
ENTER
ARRAY
4
8
3
10
ENTER ELEMENT To BE SEARCHED: 3
ELEMENT
FOUND AT POSITION 3
TIME
COMPLEXIBILITY 0.10903
AIM
: TO FIND OUT THE COMPLEXITY OF BUBBLE , INSERTION AND SELECTION SORTING
METHODS
#include<iostream.h>
#include<conio.h>
Void
bubble(int a[], int s)
{
Int y;
for(int x=0; x<n; x++)
{for(y=0; y<n-1; y++)
{
if(array[y]>array[y+1])
{
int temp = array[y+1];
array[y+1] = array[y];
array[y] = temp;
}}}
cout<<"The array after BUBBLE
sorting is : ";
for(i=0;i<s;i++)
cout<<a[i]<<" ";
}
Void
insert(int a[], int n)
{
for(i=2; i<=n; i++)
{
temp = a[i];
j = i-1;
while(temp<a[j] && j>=1)
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
cout<<"The array after INSERTION
sorting is : ";
for(i=0;i<s;i++)
cout<<a[i]<<" ";
}
Void
select(int a[], int s)
{
for(i=0;i<s;i++)
{
for(j=i+1;j<s;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
cout<<"The array after SELECTION
sorting is : ";
for(i=0;i<s;i++)
cout<<a[i]<<" ";
}
void
main()
{
clrscr();
int s,i,j,temp,a[20];
cout<<"Enter size of the array :
";
cin>>s;
cout<<"Enter the unsorted array
:";
for(i=0;i<s;i++)
cin>>a[i];
cout<<” [1] BUBBLE SORT “;
cout<<” [2] SELECTION SORT “;
cout<<” [1] INSERTION SORT “;
cin>>ch;
switch(ch)
{
Case 1: start=clock();
Bubble(a,s);delay(100);
End=clock();
cout<<"\n Time complexity
"<<(end-start)/CLK_TCK;
break;
Case 2: start=clock();
select(a,s);delay(100);
End=clock();
cout<<"\n Time complexity
"<<(end-start)/CLK_TCK;
break;
Case 3: start=clock();
insert(a,s);delay(100);
End=clock();
cout<<"\n Time complexity
"<<(end-start)/CLK_TCK;
break;
};
getch();
}
OUTPUT
[1].
BUBBLE SORT
[2].
SELECTION SORT
[3].
INSERTION SORT
Enter
choice :1
Enter
size of the array : 5
Enter
the unsorted array : 67 89 45 56 13
The
array after BUBBLE sorting is : 13
45 56 67 89
TIME
COMPLEXIBILTY : 0.109
#include<stdio.h>
#include<time.h>
#include<conio.h>
#include<dos.h>
void quicksort(int [10],int,int);
void main(){
int x[20],size,i;
clock_t start,end;
printf("Enter
size of the array: ");
scanf("%d",&size);
printf("Enter
%d elements: ",size);
for(i=0;i<size;i++)
scanf("%d",&x[i]);
start=clock();
quicksort(x,0,size-1);
delay(100);
end=clock();
printf("Sorted
elements: ");
for(i=0;i<size;i++)
printf(" %d",x[i]);
cout<<”COMPLEXITY is :”<<(end-start)/CLK_TCK;
getch();
}
void quicksort(int x[10],int first,int last){
int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
Output:
Enter size of the array: 5
Enter 5 elements: 3 8 0 1 2
Sorted elements: 0 1 2 3 8
Complexity is : 0.10989
For Updates Please revisit again or Bookmark us (ctrl+D)
No comments:
Post a Comment