Scribd
Upload
6 views

Final Ada Lab Program

Design and analysis of algorithm

Uploaded by

ficonin418
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

Final Ada Lab Program

Design and analysis of algorithm

Uploaded by

ficonin418
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

9. Write a program to evaluate a polynomial using brute force based algorithm.

#include <stdio.h>
#include<conio.h>
int main() {
float a[100],sum=0,x;
int n,i;
printf("enter the degree of the polynomial::");
scanf("%d",&n);
printf("enter coefficient of the polynomial x::\n");
for(i=n;i>=0;i--)
{
printf("\n Enter coefficient of [x^%d]::",i);
scanf("%f",&a[i]);
}
printf("\n Enter the value of x::");
scanf("%f",&x);
for(i=n;i>0;i--)
{
sum=(sum+a[i])*x;
}
sum=sum+a[0];
printf("\n Value of the polynomial is [%f]\n",sum);
getch();
return 0;
}

OUTPUT:

enter the degree of the polynomial::3


enter coefficient of the polynomial x::

Enter coefficient of [x^3]::4

Enter coefficient of [x^2]::3


Enter coefficient of [x^1]::2

Enter coefficient of [x^0]::1

Enter the value of x::3

Value of the polynomial is [142.000000]

8. Write a program to implement Floyd algorithm


#include<stdio.h>
#include<conio.h>
int min(int,int);
void floyds(int p[10][10],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
p[i][j]=0;
else
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b)
{
if(a<b)
return(a);
else
return(b);
}
void main()
{
int p[10][10],w,n,e,u,v,i,j;
clrscr();
printf("\nEnter the number of vertices: ");
scanf("%d",&n);
printf("Enter the number of edges: ");
scanf("%d",&e);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=999;
}
for(i=1;i<=e;i++)
{
printf("Enter the end vertices of edge %d with its weight : ",i);
scanf("%d%d%d",&u,&v,&w);
p[u][v]=w;
}
printf("Matrix of input data\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",p[i][j]);
printf("\n");
}
floyds(p,n);
printf("\nTransitive closure \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",p[i][j]);
printf("\n");
}
printf("\nThe shortest paths are \n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
printf("\n%d,%d>=%d",i,j,p[i][j]);
}
getch();
}
Output
Enter the number of vertices: 4
Enter the number of edges: 5
Enter the end vertices of edge 1 with its weight : 1
3
3
Enter the end vertices of edge 2 with its weight : 2
1
2
Enter the end vertices of edge 3 with its weight : 3
2
7
Enter the end vertices of edge 4 with its weight : 3
4
1
Enter the end vertices of edge 5 with its weight : 4
1
6
Matrix of input data
999 999 3 999
2 999 999 999
999 7 999 1
6 999 999 999

Transitive closure
0 10 3 4
2 0 5 6
7 7 0 1
6 16 9 0

The shortest paths are

<1,2>=10
<1,3>=3
<1,4>=4
2,1>=2
2,3>=5
2,4>=6
3,1>=7
3,2>=7
3,4>=1
4,1>=6
4,2>=16
4,3>=9

10.Write a C program to solve the string matching problem using Boyer Moore
Algorithm
#include <limits.h>
#include <stdio.h>
#include <string.h>

#define NO_OF_CHARS 256

// A utility function to get maximum of two integers


int max(int a, int b) { return (a > b) ? a : b; }

// The preprocessing function for Boyer Moore's


// bad character heuristic

void badCharHeuristic(char* str, int size, int badchar[NO_OF_CHARS])


{
int i;

// Initialize all occurrences as -1

for (i = 0; i < NO_OF_CHARS; i++)


badchar[i] = -1;

// Fill the actual value of last occurrence of a character

for (i = 0; i < size; i++)


badchar[(int)str[i]] = i;
}

/* A pattern searching function that uses Bad


Character Heuristic of Boyer Moore Algorithm */

void search(char* txt, char* pat)


{
int m = strlen(pat);
int n = strlen(txt);

int badchar[NO_OF_CHARS];

/* Fill the bad character array by calling


the preprocessing function badCharHeuristic()
for given pattern */

badCharHeuristic(pat, m, badchar);

int s = 0; // s is shift of the pattern with respect to text


while (s <= (n - m))
{
int j = m - 1;

/* Keep reducing index j of pattern while


characters of pattern and text are
matching at this shift s */

while (j >= 0 && pat[j] == txt[s + j])


j--;

/* If the pattern is present at current


shift, then index j will become -1 after
the above loop */

if (j < 0)
{
printf("\n pattern occurs at shift = %d", s);

/* Shift the pattern so that the next


character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */

s += (s + m < n) ? m - badchar[txt[s + m]] : 1;


}

else

/* Shift the pattern so that the bad character


in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */

s += max(1, j - badchar[txt[s + j]]);


}
}

int main()
{
char txt[] = "ABAAABCD";
char pat[] = "ABC";
search(txt, pat);
return 0;
}

Output
pattern occurs at shift = 4

You might also like