EX.NO.1.

Searching and Sorting Algorithms

1.a.Implement Linear Search. Determine the time required to search for an element. Repeat
the experiment for different values of n, the number of elements in the list to be searched and
plot a graph of the time taken versus n.

Program:
#include<stdio.h>
int main()
{
int a[20],i,x,n;
printf("How many elements?");
scanf("%d",&n);

printf("Enter array elements:n");

for(i=0;i<n;++i)
scanf("%d",&a[i]);

printf("nEnter element to search:");

scanf("%d",&x);

for(i=0;i<n;++i)
if(a[i]==x)
break;

if(i<n)
printf("Element found at index %d",i);
else
printf("Element not found");

return 0;
}

OUTPUT:

How many elements?3

Enter array elements:n4 6 5
nEnter element to search:4
Element found at index 0
1b. Implement Recursive Binary search and Linear search and determine the time required to
search an element. Repeat the experiment for different values of n, the number of elements in
the list to be searched and plot a graph of the time taken versus n.
Program:
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
#define max 20
int pos;
int binsearch (int,int[],int,int,int);
int linsearch (int,int[],int);
void main()
{ int ch=1; double t; int n,i,a [max],k,op,low,high,pos, begin,end;
while(ch)
{
printf("\n.......MENU \n 1.BinarySearch \n 2.Linear search \n 3.Exit \n");
printf("\n enter your choice\n");
scanf("%d",&op);
switch(op)
{
case 1:printf("\n enter the number of elments\n"); scanf("%d",&n);
printf("\n enter the number of an array in the order \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n enter the elements to be searched \n");
scanf("%d",&k); low=0;high=n-1; begin=clock();
pos=binsearch(n,a,k,low,high);
end=clock()
; if(pos==-
1)
printf("\n\nUnsuccessful search");
else
printf("\n element %d is found at position %d",k,pos+1);
printf("\n Time Taken is %lf CPU1 cycles
\n",(end-begin)/CLK_TCK); getch();
break;
case 2:printf("\n enter the number of elements \n");
scanf("%d",&n);
printf("\n enter the elements of an array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n enter the element to be searched \n");
scanf("%d",&k);
begin=clock();
pos=linsearch(n,a,k);
end=clock();
if(pos==-1)
printf("\n\n Unsuccessful search");
else
printf("element %d is found at position %d",k,pos+1);
printf("\n Time taken is %lf CPU cycles \n",(end-begin)/CLK_TCK);
getch(); break;
default:printf("Invalid choice entered \n");
exit(0);
}
printf("\n Do you wish to run again(1/0) \n");
scanf("%d",&ch);
}
getch();
}
int binsearch(int n,int a[],int k,int low,int high)
{
int mid;
mid=(low+high)/2;
if(low>high)
return -1;
if(k==a[mid])
return(mid);
else
if(k<a[mid])
return binsearch(n,a,k,low,mid-1);
else
return binsearch(n,a,k,mid+1,high);
}
int linsearch(int n,int a[],int k)
{
if(n<0) return -1;
if(k==a[n-1])
return (n-1);
else
return linsearch(n-1,a,k);
}
OUTPUT:

.......MENU.......
1.BinarySearch
2.Linear search
3.Exit

enter your choice

2

enter the number of elements

3

enter the elements of an array

369

enter the element to be searched

3
element 3 is found at position 0
Time taken is 0.000000 CPU
cycles

Do you wish to run again(1/0)

1

.......MENU.......
1.BinarySearch
2.Linear search
3.Exit

enter your choice

1

enter the number of elments

3

enter the number of an array in the order

472

enter the elements to be searched

2

Unsuccessful search
Time Taken is 0.000000 CPU1 cycles

Do you wish to run again(1/0)

0
1c.Given a text txt [0...n-1] and a pattern pat [0...m-1], write a function search (char pat [ ],
char txt [ ]) that prints all occurrences of pat [ ]in txt [ ]. You may assume that n > m.
Program:
#include <stdio.h>
#include <string.h>
int match(char [], char []);
int main() {
char a[100], b[100];
int position;
printf("Enter some text\n");
gets(a);
printf("Enter a string to find\n");
gets(b);
position = match(a, b);
if (position != -1) {
printf("Found at location: %d\n", position + 1);
}
else {
printf("Not found.\n");
}
return 0;
}
int match(char text[], char pattern[]) {
int c, d, e, text_length, pattern_length, position = -1;
text_length = strlen(text);
pattern_length = strlen(pattern);
if (pattern_length > text_length) {
return -1;
}
for (c = 0; c <= text_length - pattern_length; c++) {
position = e = c;
for (d = 0; d < pattern_length; d++) {
if (pattern[d] == text[e]) {
e++;
}
else {
break;
}
}
if (d == pattern_length) {
return position;
}
}
return -1;
}
OUTPUT:

Enter some text

life without
Enter a string to find
life
Found at location: 1
1d.Sort a given set of elements using the Insertion sort and Heap sort methods and determine
the time required to sort the elements. Repeat the experiment for different values of n, the
number of elements in the list to be sorted and plot a graph of the time taken versus n.

#Insertion sort for any given list of numbers.

Program:
#include<stdio.h>
#include<conio.h>
void inssort(int[],int);
void display(int[],int);
int main()
{
int a[20],n,i;
clrscr();
printf("\n Enter the number of elements in array are:");
scanf("%d",&n);
printf("\n Enter %d elements in the array:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
inssort(a,n);
printf("\n The sorted elements in the array are:");
display(a,n);
getch();
return 0;
}
void inssort(int a[],int n)
{
int i,j,index=0;
for(i=1;i<n;i++)
{
index=a[i];
j=i;
while((j>0)&&(a[j-1]>index))
{
a[j]=a[j-
1]; j--;
}
a[j]=index;
}
}
void display(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
OUTPUT:

Enter the number of elements in array are:4

Enter 4 elements in the array:9 2 7 4

The sorted elements in the array are:2 4 7 9

 Ex.No.2.Graph Algorithms
2a.Develop a program to implement graph traversal using Breadth First
Search Program:
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=-1,r=0;
voidbfs(int v){
q[++r]=v;
visited[v]=1;
while(f<=r) {
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i]){
visited[i]=1;
q[++r]=i;
}
f++;
v=q[f];
}
}
void main(){
int v;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++){
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
40 | P a g e
printf("\n The node which are reachable are:\n");
for(i=1;i<=n;i++)
if(visited[i])
printf("%d\t",q[i]);
else
printf("\n Bfs is not possible");
}
OUTPUT:

Enter the number of vertices:4

Enter graph data in matrix form:

0111
1010
1100
1000

Enter the starting vertex:4

The node which are reachable are:

4 1 2 3
2b.Develop a program to implement graph traversal using Depth First Search
//Checking whether a given graph is connected or not using DFS
method Program:
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v){
int i; reach[v]=1;
for(i=1;i<=n;i++) if(a[v]
[i] && !reach[i]) {
printf("\n %d->%d",v,i);
dfs(i);
}
}
void main(){
int i,j,count=0;
printf("\n Enter number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++){
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for(i=1;i<=n;i++){
if(reach[i]) count+
+;
}
if(count==n)
printf("\n Graph is connected");
else
printf("\n Graph is not connected");
}
OUTPUT:

Enter number of vertices:4

Enter the adjacency matrix:
0011
1010
1001
1100

1->3
3->4
4->2

Graph is connected
2c. From a given vertex in a weighted connected graph, develop a program to find the shortest
paths to other vertices using Dijkstra’s algorithm.
Program:
#include<stdio.h>
#define infinity 999
void dij(int n, int v,int cost[20][20], int dist[])
{ 27 | P a g e
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]) {
min=dist[w];
u=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];
}
}
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:

enter the number of nodes:4

enter the cost matrix:

0110
1001
1100
1010

enter the source matrix:1

shortest path :
1->2,cost=1
1->3,cost=1
1->4,cost=2
2d.Find Minimum Cost Spanning Tree of a given undirected graph using Prims algorithm.

Program:
#include<stdio.h>
#include<conio.h>
void main()
{
int cost[20][20],t[20][20],near1[20],a[20];
int i,j,n,min,minimum,k,l,mincost,c,b;
clrscr();
printf("\n enter the number of nodes\n");
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]);
minimum=cost[1][1];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(minimum>=cost[i][j])
{
minimum=cost[i][j];
k=i;
l=j;
}
}
mincost=minimum;
t[1][1]=k;
t[1][2]=l;
for(i=1;i<=n;i++)
{
if(cost[i][l]<cost[i][k])
near1[i]=l;
else
near1[i]=k;
}
near1[k]=near1[l]=0;
for(i=2;i<=n-1;i++)
{
min=999;
for(j=1;j<=n;j++)
{
if(near1[j]!=0)
{
a[j]=cost[j][near1[j]];
{
min=a[j];
c=near1[j];
b=j;
printf("\n");
}
}
}
mincost=mincost+cost[b][c];
near1[b]=0; for(k=1;k<=n;k+
+) if((near1[k]!=0) &&
(cost[k][near1[k]]>cost[k][b]))
near1[k]=b;
}
printf("\n\ the cost of minimum spanning tree is=%d",mincost);
getch();
}
OUTPUT:

enter the number of nodes

4

enter the adjacency matrix

0350
2024
1506
2300

N the cost of minimum spanning tree is=8

2e. Implement Floyd's algorithm for the All-pairs-Shortest-Path problem.

Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],a[10][10];
void all_paths(int[10][10],int[10][10],int);
int min1(int,int);
void main()
{
int i,j,n;
clrscr();
printf("\n enter the number of vertices\n");
scanf("%d",&n);
printf("enter the adjacency matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
all_paths(cost,a,n);
printf("\n shortest path obtained is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("\t%d",a[i][j]);
printf("\n");
}
getch();
}
void all_paths(int cost[10][10],int a[10][10],int n)
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=cost[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=min1(a[i][j],a[i][k]+a[k][j]);
}
int min1(int a,int b)
{
return(a<b)?a:b;
}
OUTPUT:

enter the number of vertices

4
enter the adjacency matrix0 8 3 4
4084
1503
3530

shortest path obtained is

0 8 3 4
4 0 7 4
1 5 0 3
3 5 3 0
2f. Compute the transitive closure of a given directed graph using Warshall's 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(){
inti,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:
Enter the number of nodes:4

Enter the adjacency matrix:

0141
1045
2305
2580

The path matrix is shown below

1141
1141
2305
2580
 Ex no.3.Algorithm Design Techniques
3a.Develop a program to find out the maximum and minimum numbers in a given list of n
numbers using the divide and conquer technique.
Program:

#include<stdio.h>
#include<conio.h>
void minmax(int,int,int,int);
int i,j,a[50],n,fmax,fmin;
int main()
{
clrscr();
printf("\n Enter the number of elements in array are:");
scanf("%d",&n);
printf("\n Enter %d elements in the array:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n The Elements in the array are:");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
//fmax=fmin=a[0];
minmax(0,n-1,a[0],a[0]);
printf("\n The minimum Element of the list of elements is:%d",fmin);
printf("\n The maximum Element of the list of elements is:%d",fmax);
getch();
return 0;
}
void minmax(int i,int j,int max,int min)
{
int gmax,gmin,hmax,hmin;
gmax=hmax=max;
gmin=hmin=min;
if(i==j)
{
fmax=fmin=a[i];
}
else if(i==(j-1))
{
if(a[i]>a[j])
{
fmax=a[i];
fmin=a[j];
}
else
{
fmax=a[j];
fmin=a[i];
}
}
else
{
int mid=(i+j)/2;
 minmax(i,mid,a[i],a[i]);
gmax=fmax;
gmin=fmin;
minmax(mid+1,j,a[mid+1],a[mid+1]);
hmax=fmax;
hmin=fmin;
if(gmax>hmax)
{
fmax=gmax;
}
else
{
fmax=hmax;
}
if(gmin>hmin)
{
fmin=hmin;
}
else
{
fmin=gmin;
}
}
}
OUTPUT:
Enter the number of elements in array are:4

Enter 4 elements in the array:4 5 6 7

The Elements in the array are:4

5
6
7

The minimum Element of the list of elements is:4

The maximum Element of the list of elements is:7
3b. Implement Merge sort and Quick sort methods to sort an array of elements and determine
the time required to sort. Repeat the experiment for different values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n.

Quick Sort
Program:
#include <stdio.h>
#include <time.h>
void Exch(int *p, int *q){
int temp = *p;
*p = *q;
*q = temp;
}
void QuickSort(int a[], int low, int high){
int i, j, key, k;
if(low>=high)
return;
key=low;
i=low+1;
j=high;
while(i<=j){
while ( a[i] <= a[key] )
i=i+1;
while ( a[j] > a[key] )
j=j -1;
if(i<j)
Exch(&a[i], &a[j]);
}
Exch(&a[j], &a[key]);
QuickSort(a, low, j-1);
QuickSort(a, j+1,
high);
}
void main(){
int n, a[1000],k;
int clock_tst,et,st ;
double ts;
printf("\n Enter How many Numbers: ");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for(k=1; k<=n; k++){
a[k]=rand();
printf("%d\t",a[k]);
}
st=clock();
QuickSort(a, 1, n);
et=clock();
ts=(double)(et-st)/CLOCKS_PER_SEC;
printf("\nSorted Numbers are: \n ");
for(k=1; k<=n; k++)
printf("%d\t", a[k]);
printf("\nThe time taken is %e",ts);}
OUTPUT:
Enter How many Numbers: 5

The Random Numbers are:

41 18467 6334 26500 19169
Sorted Numbers are:
41 6334 18467 19169 26500
The time taken is 0.000000e+000
Merge Sort:
Program:
#include <stdio.h>
#include<time.h>
int b[50000];
void Merge(int a[], int low, int mid, int high){
int i, j, k;
i=low; j=mid+1; k=low;
while ( i<=mid && j<=high ) {
if( a[i] <= a[j] )
b[k++] = a[i++] ;
else
b[k++] = a[j++] ;
}
while (i<=mid)
b[k++] = a[i++] ;
while (j<=high)
b[k++] = a[j++] ;
for(k=low; k<=high; k++)
a[k] = b[k];
}
voidMergeSort(int a[], int low, int high){
int mid;
if(low >= high)
return;
mid = (low+high)/2 ;
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
Merge(a, low, mid, high);
}
void main(){
int n, a[50000],k;
clock_tst,et;
doublets;
printf("\n Enter How many Numbers:");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for(k=1; k<=n; k++) {
a[k]=rand();
printf("%d\t", a[k]);
}
st=clock();
MergeSort(a, 1, n);
et=clock();
ts=(double)(et-st)/CLOCKS_PER_SEC;
printf("\n Sorted Numbers are : \n ");
for(k=1; k<=n; k++)
printf("%d\t", a[k]);
printf("\nThe time taken is %e",ts);
}
OUTPUT:

Enter How many Numbers:5

The Random Numbers are:

41 18467 6334 26500 19169
Sorted Numbers are :
41 6334 18467 19169 26500
The time taken is 0.000000e+000
 Ex.No.4.State Space Search Algorithms
4a.Implement N Queens problem using Backtracking.
Program:
#include<stdio.h>
#include<conio.h>
#include<math.h>
int x[20],count=1;
void queens(int,int);
int place(int,int);
void main()
{
int n,k=1;
clrscr();
printf("\n enter the number of queens to be placed\n");
scanf("%d",&n);
queens(k,n);
}
void queens(int k,int n)
{
int i,j;
for(j=1;j<=n;j++)
{
if(place(k,j))
{
x[k]=j;
if(k==n)
{
printf("\n %d solution",count);
count++;
for(i=1;i<=n;i++)
printf("\n \t %d row <---> %d
column",i,x[i]);
getch();
}
else
queens(k+1,n);
}
}}
int place(int k,int j)
{
int i;
for(i=1;i<k;i++)
if((x[i]==j) || (abs(x[i]-j))==abs(i-k))
return 0;
return 1;
}
OUTPUT:
enter the number of queens to be placed
1

1 solution
1 row <---> 1column
 Ex.No.5.Approximation Algorithms Randomized Algorithms

5a.Implement any scheme to find the optimal solution for the Traveling Salesperson problem
and then solve the same problem instance using any approximation algorithm and determine
the error in the approximation.
Program:
#include<stdio.h>
ints,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 */
voidbrute_force(int v[], int n, int i) {
// this function generates the permutations of the array from element i to element n-1
int j,sum1,k;
//if we are at the end of the array, we have one
permutation 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
// recursively explore the permutations starting at index i going through index n-1*/
for (j=i; j<n; j++) { /* try the array with i and j switched */
swap (v, i, j);
brute_force (v, n, i+1);
/* swap them back the way they were */
swap (v, i, j);
}
}
voidnearest_neighbour(intver) {
intmin,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 () {
intver,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);
47 | P a g e
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:
Enter n : 4
Enter cost matrix
0345
2053
2404
3110

Enter source : 1
1 2 3 4 sum = 15
1 2 4 3 sum = 9
1 3 2 4 sum = 14
1 3 4 2 sum = 11
1 4 3 2 sum = 12
1 4 2 3 sum = 13

Optimum solution with brute force technique is=9.000000

Solution with nearest neighbour technique is=0.000000

The approximation val is=-100.000000
 5b.Implement randomized algorithms for finding the kth smallest number.

Program:
#include <stdio.h>
#include <stdlib.h>

// Compare function for qsort

int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}

// Function to return K'th smallest

// element in a given array
int kthSmallest(int arr[], int N, int K)
{
// Sort the given array
qsort(arr, N, sizeof(int), cmpfunc);

// Return k'th element in the sorted

array return arr[K - 1];
}

// Driver's
code int
main()
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]), K = 2;

// Function call
printf("K'th smallest element is
%d", kthSmallest(arr, N,
K));
return 0;
}

OUTPUT:

K'th smallest element is 5