EX NO: 1

LINEAR SEARCH
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

int main()

int array[50],i,target,num;

printf("How many elements do you want in the array");

scanf("%d",&num);

printf("Enter array elements:");

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

scanf("%d",&array[i]);

printf("Enter element to search:");

scanf("%d",&target);

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

if(array[i]==target)

break;

if(i<num)

printf("Target element found at location %d",i);

else

printf("Target element not found in an array");

return 0;

}
OUTPUT :

RESULT:
EX NO: 2
BINARY SEARCH
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>

int main()

int i, low, high, mid, n, key, array[100];

printf("Enter number of elements");

scanf("%d",&n);

printf("Enter %d integers", n);

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

scanf("%d",&array[i]);

printf("Enter value to find");

scanf("%d", &key);

low = 0;

high = n - 1;

mid = (low+high)/2;

while (low <= high) {

if(array[mid] < key)

low = mid + 1;

else if (array[mid] == key) {

printf("%d found at location %d", key, mid+1);

break;

else

high = mid - 1;

mid = (low + high)/2;

if(low > high)

printf("Not found! %d isn't present in the list", key);

return 0;

}
OUTPUT:

RESULT :
EX NO: 3
STRING MATCHING ALGORITHM
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h>

#include<conio.h>

#include<string.h>

int match(char st[100], char pat[100]);

int main(int argc, char **argv) {

char st[100], pat[100];

int status;

printf("*** Naive String Matching Algorithm ***\n");

printf("Enter the String.\n");

gets(st);

printf("Enter the pattern to match.\n");

gets(pat);

status = match(st, pat);

if (status == -1)

printf("\nNo match found");

else

printf("Match has been found on %d position.", status);

return 0;

int match(char st[100], char pat[100]) {

int n, m, i, j, count = 0, temp = 0;

n = strlen(st);

m = strlen(pat);

for (i = 0; i <= n - m; i++) {

temp++;

for (j = 0; j < m; j++) {

if (st[i + j] == pat[j])

count++;

}
 if (count == m)

return temp;

count = 0;

return -1;

OUTPUT :
Enter the String.hingu.Dharmmendra@gmail.com
Enter the pattern to match. Dharm

Match has been found on 6 position.

RESULT :
EX NO: 4
INSERTION SORT
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>

void insert(int a[], int n)

int i, j, temp;

for (i = 1; i < n; i++)

temp = a[i];

j = i - 1;

while(j>=0 && temp <= a[j])

a[j+1] = a[j];

j = j-1;

a[j+1] = temp;

void printArr(int a[], int n)

int i;

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

printf("%d ", a[i]);

int main()

int a[] = { 12, 31, 25, 8, 32, 17 };

int n = sizeof(a) / sizeof(a[0]);

printf("Before sorting array elements are - \n");

printArr(a, n);

insert(a, n);
 printf("\nAfter sorting array elements are - \n");

printArr(a, n);

return 0;

OUTPUT :

RESULT :
EX NO: 5
HEAP SORT
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>

void heapify(int a[], int n, int i)

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && a[left] > a[largest])

largest = left;

if (right < n && a[right] > a[largest])

largest = right;

if (largest != i)

int temp = a[i];

a[i] = a[largest];

a[largest] = temp;

heapify(a, n, largest);

void heapSort(int a[], int n)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(a, n, i);

for (int i = n - 1; i >= 0; i--)

int temp = a[0];

a[0] = a[i];

a[i] = temp;

heapify(a, i, 0);

}
}

void printArr(int arr[], int n)

for (int i = 0; i < n; ++i)

printf("%d", arr[i]);

printf(" ");

int main()

int a[] = {48, 10, 23, 43, 28, 26, 1};

int n = sizeof(a) / sizeof(a[0]);

printf("Before sorting array elements are - \n");

printArr(a, n);

heapSort(a, n);

printf("\nAfter sorting array elements are - \n");

printArr(a, n);

return 0;

}
OUTPUT :

RESULT :
EX NO: 6
BREADTH FIRST SEARCH
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>

int n, i, j, visited[10], queue[10], front = -1, rear = -1;

int adj[10][10];

void bfs(int v)

for (i = 1; i <= n; i++)

if (adj[v][i] && !visited[i])

queue[++rear] = i;

if (front <= rear)

visited[queue[front]] = 1;

bfs(queue[front++]);

void main()

int v;

printf("Enter the number of vertices: ");

scanf("%d", &n);

for (i = 1; i <= n; i++)

queue[i] = 0;

visited[i] = 0;

printf("Enter graph data in matrix form: \n");

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

scanf("%d", &adj[i][j]);

printf("Enter the starting vertex: ");

 scanf("%d", &v);

bfs(v);

printf("The node which are reachable are: \n");

for (i = 1; i <= n; i++)

if (visited[i])

printf("%d\t", i);

else

printf("BFS is not possible. Not all nodes are reachable");

return 0;

OUTPUT :
Enter the number of vertices: 4
Enter graph data in matrixform:
0110
1001
1001
0110
Enter the starting vertex: 2
The node which are reachable are:
1 2 3 4

RESULT :
EX NO: 7
DEPTH FIRST SEARCH
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>

#include <stdlib.h>

/* ADJACENCY MATRIX */

int source,V,E,time,visited[20],G[20][20];

void DFS(int i)

int j;

visited[i]=1;

printf(" %d->",i+1);

for(j=0;j<V;j++)

if(G[i][j]==1&&visited[j]==0)

DFS(j);

int main()

int i,j,v1,v2;

printf("\t\t\tGraphs\n");

printf("Enter the no of edges:");

scanf("%d",&E);

printf("Enter the no of vertices:");

scanf("%d",&V);

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

for(j=0;j<V;j++)

G[i][j]=0;

for(i=0;i<E;i++)
 {

printf("Enter the edges (format: V1 V2) : ");

scanf("%d%d",&v1,&v2);

G[v1-1][v2-1]=1;

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

for(j=0;j<V;j++)

printf(" %d ",G[i][j]);

printf("\n");

printf("Enter the source: ");

scanf("%d",&source);

DFS(source-1);

return 0;

}
OUTPUT :

RESULT :
EX NO: 8
DIJKSTRA’S ALGORITHM
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h>

#define infinity 999

void dij(int n, int v,int cost[20][20], int dist[])

int i,u,count,w,flag[20],min;

for(i=1;i<=n;i++)

flag[i]=0, dist[i]=cost[v][i];

count=2;

while(count<=n)

min=99;

for(w=1;w<=n;w++)

if(dist[w]<min && !flag[w])

flag[u]=1;count++;

for(w=1;w<=n;w++)

if((dist[u]+cost[u][w]<dist[w]) && !flag[w])

dist[w]=dist[u]+cost[u][w];

min=dist[w]; u=w;

int main(){

int n,v,i,j,cost[20][20],dist[20];

printf("enter the number of nodes:");

scanf("%d",&n);

printf("\n enter the cost matrix:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)
{

scanf("%d",&cost[i][j]);if(cost[i][j] == 0)

cost[i][j]=infinity;

printf("\n enter the source matrix:");

scanf("%d",&v);

dij(n,v,cost,dist);

printf("\n shortest path : \n");

for(i=1;i<=n;i++)

if(i!=v)

printf("%d->%d,cost=%d\n",v,i,dist[i]);

OUTPUT :

RESULT :
EX NO: 9
MINIMUM COST SPANNING TREE
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h>

inta,b,u,v,n,i,j,ne=1;

int visited[10]={0},min,mincost=0,cost[10][10];

void main()

printf("\n Enter the number of nodes:");

scanf("%d",&n);

printf("\n Enter the adjacency matrix:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%d",&cost[i][j]);

if(cost[i][j]==0)

cost[i][j]=999;

visited[1]=1;

printf("\n");

while(ne<n)

for(i=1,min=999;i<=n;i++)

for(j=1;j<=n;j++)

if(cost[i][j]<min)

if(visited[i]!=0)

min=cost[i][j];

a=u=i;

b=v=j;

if(visited[u]==0 || visited[v]==0)

{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);

mincost+=min;

visited[b]=1;

cost[a][b]=cost[b][a]=999;

printf("\n Minimun cost=%d",mincost);

OUTPUT :

RESULT :
EX NO: 10
ALL-PAIRS- SHORTEST-PATHS PROBLEM
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.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]);

main()

int min(inta,int b)

if(a<b) return(a); else return(b);

int p[10][10],w,n,e,u,v,i,j;

printf("\n Enter the number of vertices:");

scanf("%d",&n);

printf("\n Enter the number of edges:\n");

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("\n Enter the end vertices of edge%d with its weight \n",i);

scanf("%d%d%d",&u,&v,&w);

p[u][v]=w;

printf("\n 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("\n Transitive closure:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

printf("%d \t",p[i][j]);

printf("\n");

printf("\n The 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]);

}
OUTPUT :

RESULT :
EX NO: 11
WARSHALL'S ALGORITHM
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>

int n,a[10][10],p[10][10];

void path()

int i,j,k;

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

for(j=0;j<n;j++)

p[i][j]=a[i][j];

for(k=0;k<n;k++)

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

for(j=0;j<n;j++)

if(p[i][k]==1&&p[k][j]==1)p[i][j]=1;

void main()

int i,j;

printf("Enter the number of nodes:");

scanf("%d",&n);

printf("\nEnter the adjacency matrix:\n");

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

for(j=0;j<n;j++)

scanf("%d",&a[i][j]);

path();

printf("\nThe path matrix is shown below\n");

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

for(j=0;j<n;j++)

printf("%d ",p[i][j]);

printf("\n");
}

OUTPUT :

RESULT :
EX NO: 12
MAXIMUM AND MINIMUM NUMBERS
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h
>
#include<stdio.h
>int max, min;
int a[100];
void maxmin(int i, int j)
{
int max1, min1,
mid;if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1)
{
if(a[i] <a[j])
{
max = a[j];
min = a[i];
}
else
{
max = a[i];
min = a[j];

}
}
else
{
mid = (i+j)/2;
maxmin(i, mid);
max1 = max; min1 =
min;maxmin(mid+1, j);
if(max <max1)
max = max1;
if(min > min1)
min = min1;
}
}
}
int main ()
{
int i, num;
printf ("\nEnter the total number of numbers : ");
scanf ("%d",&num);
printf ("Enter the numbers :
\n");for (i=1;i<=num;i++)
scanf ("%d",&a[i]);

max = a[0];
min = a[0];
 maxmin(1, num);
printf ("Minimum element in an array : %d\n", min);
printf ("Maximum element in an array : %d\n",
max);return 0;
}

OUTPUT :
Enter the total number of numbers :
5Enter the numbers :
29
21
64
27
20
Minimum element in an array : 20
Maximum element in an array : 64

RESULT :
EX NO: 13
MERGE SORT
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays
*/int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into
arr[l..r]*/i = 0; // Initial index of first
subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {

}
else {

} k++;
}

arr[k] = L[i];
i++;
arr[k] = R[j];
j++;
/* Copy the remaining elements of L[], if there are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there are any */

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
 mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

void printArray(int A[], int size)

{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

OUTPUT :

Given array is
12 11 13 5 6 7
Sorted array
is5 6 7 11 12
13

RESULT :
EX NO: 14
QUICK SORT
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include <stdio.h>
int partition (int a[], int start, int end)
{
int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++)
{
if (a[j] < pivot)
{

i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}

void quick(int a[], int start, int end)

{
if (start < end)
{
int p = partition(a, start, end); //p is the partitioning index
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}
/* function to print an array */
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 24, 9, 29, 14, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
OUTPUT :

RESULT :
EX NO: 15
N QUEENS PROBLEM
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h>
#include<math.h>
int a[30],count=0;
int place(int pos)
{
int i;
for(i=1;i<pos;i++)
{
if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
return 0;
}
return 1;
}
void print_sol(int n)
{
int i,j;
count++;
printf("\n\nSolution #%d:\n",count);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i]==j)
printf("Q\t");
else

printf("*\t");
}
printf("\n");
}
}
void queen(int n)
{
int k=1;
a[k]=0;
while(k!=0)
{
a[k]=a[k]+1; while((a[k]<=n)&&!place(k))
a[k]++;
if(a[k]<=n)
{
if(k==n)
print_sol(n);
else
{
k++;
a[k]=0;
}
}
else
k--;

}
}
void main()
{
int i,n;
printf("Enter the number of Queens\n");
scanf("%d",&n);
queen(n);
printf("\nTotal solutions=%d",count);
}

OUTPUT :

RESULT :
EX NO: 16
TRAVELING SALESPERSON PROBLEM
DATE:

AIM :

ALGORITHM :
PROGRAM :
#include<stdio.h>
int s,c[100][100],ver;
float optimum=999,sum;
/* function to swap array elements */
void swap(int v[], int i, int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}
/* recursive function to generate permutations */
Void brute_force(int v[], int n, int i)
{
int j,sum1,k;

if (i == n)
{
if(v[0]==s)
{
for (j=0; j<n; j++)
printf ("%d ", v[j]);
sum1=0;
for( k=0;k<n-1;k++)
{
sum1=sum1+c[v[k]][v[k+1]];
}
sum1=sum1+c[v[n-1]][s];
printf("sum = %d\n",sum1);
if (sum1<optimum)
optimum=sum1;

}
}
else
for (j=i; j<n; j++)
{
swap (v, i, j);
brute_force (v, n, i+1);
swap (v, i, j);
}
}
void nearest_neighbour(intver)
{
int min,p,i,j,vis[20],from;
for(i=1;i<=ver;i++)
vis[i]=0;
vis[s]=1;
from=s;
sum=0;
for(j=1;j<ver;j++)
{
min=999;
for(i=1;i<=ver;i++)
if(vis[i] !=1 &&c[from][i]<min && c[from][i] !=0 )
{
min= c[from][i];
p=i;
}

vis[p]=1;
from=p;
sum=sum+min;
}
sum=sum+c[from][s];
}

void main ()
{
int ver,v[100],i,j;
printf("Enter n : ");
scanf("%d",&ver);
for (i=0; i<ver; i++)
v[i] = i+1;
printf("Enter cost matrix\n");
for(i=1;i<=ver;i++)
for(j=1;j<=ver;j++)
scanf("%d",&c[i][j]);
printf("\nEnter source : ");
scanf("%d",&s);
brute_force (v, ver, 0);
printf("\nOptimum solution with brute force technique is=%f\n",optimum);
nearest_neighbour(ver);
printf("\nSolution with nearest neighbour technique is=%f\n",sum);
printf("The approximation val is=%f",((sum/optimum)-1)*100);
printf(" % ");
}
OUTPUT :

RESULT :