DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING LAB MANUAL

ACADEMIC YEAR 2022

2022-2023

(REGULATION-2021)

PROGRAMME:UG

SEMESTER:IV

COURSE CODE:CS3401

COURSE NAME:ALGORITHM LABORATORY

BY,

Dr. I. SOFIYA M.E,PHD,

(ASSISTANT PROFESSOR/CSE)

EINSTEIN COLLEGE OF ENGINEERING

SIR C.V RAMAN NAGAR, TIRUNELVELI
TIRUNELVELI- 627 012
 LIST OF EXPERIMENTS
PRACTICAL EXERCISES: PERIODS:30

Searching and Sorting Algorithms

1. 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 agraph of the time taken versus n.
2. Implement recursive Binary Search. 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.
3. 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.
4. 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.

Graph Algorithms
1. Develop a program to implement graph traversal using Breadth First Search
2. Develop a program to implement graph traversal using Depth First Search
3. From a given vertex in a weighted connected graph, develop a program to find the
shortest pathsto other vertices using Dijkstra’s algorithm.
4. Find the minimum cost spanning tree of a given undirected graph using Prim’s
algorithm.
5. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
6. Compute the transitive closure of a given directed graph using Warshall's algorithm.

Algorithm Design Techniques

1. Develop a program to find out the maximum and minimum numbers in a given list
of n numbersusing the divide and conquer technique.

State Space Search Algorithms

1. Implement N Queens problem using Backtracking.

Approximation Algorithms Randomized Algorithms

1. 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.
th
2. Implement randomized algorithms for finding the k smallest number.
EX NO: 1 LINEAR SEARCH
DATE:

Aim:
To write a c program to implement linear search.

Algorithm:
1. Create an array with n elements stored in it.
2. An element to be searched is obtained as input
3. The element is searched sequentially from position o.
4. The consecutive positions are searched one by one until the element is found in the array.

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:
1
2
3
Enter element to search:4
 Element not found

Result:
Thus the c program to implement of linear search is executedsuccessfully and
the output is verified.
EX NO:2 BINARY SEARCH
DATE:

Aim:
To write a C program to implement binary search.

Algorithm:
1. Create an array with n elements stored in it.
2. Sort the elements in the array in ascending order .
3. An element to be searched is obtained as input(x).
4. Find the mid position of the array.
 If x=mid ,return mid at output.
 If x<mid ,search for x in the left side of the array.
 If x>mid, search for x in the right side of the array.

Program:
#include<stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = n -
1;
middle = (first+last)/2;
while (first <= last)
{
if (array[middle] < search)
first = middle+1;
else
if (array[middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
{
 printf("Not found! %d isn't present in the list.\n", search);
return 0;
}

OUTPUT
Enter number of
elements3
Enter 3 integers
1
2
3
Enter value to
find4
Not found! 4 isn't present in the list.

Result:
Thus the c program to implementation of binary search is executedsuccessfully and
the output is verified.
EX NO:3 PATTERN SEARCHING ALGORITHM
DATE:

AIM:

To write a c program to implement Naive Pattern Searching algorithm.

ALGORITHM:

1. Create an array with n Characters stored in it.

2. An Pattern to be searched is obtained as input(x).
3. Find the length of string pattern.
4. Find the length of string Text.
a. It compares first character of pattern with searchable [Link] match is
found, pointers in both strings are advanced.
b. If match not found, pointer of text is incremented and pointer of
patternis reset. This process is repeated until the end of the text.
5. It does not require any pre-processing.
6. It directly starts comparing both strings character bycharacter.
Input: txt[] = “THIS IS A TEST TEXT”,

Pat[] = “TEST”
Output: Pattern found at index 10

PROGRAM:

#include
<stdio.h>
#include
<string.h>
void search(char* pattern, char* text) {
int m = strlen(pattern);
int n = strlen(text);
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i+j] !=pattern[j])
break;}
if (j == m)
printf("Pattern found at index %d\n", i); }}
int main() {
char text[] = "EINSTEIN";
char pattern[] = "N";
search(pattern, text);
return 0;

}
OUTPUT:
Pattern found at
index: 2Pattern
found at index :7

Result:
Thus the c program to implementation of Pattern Searching is executed
successfully and the output is verified.
EX NO:4(A) INSERTION SORT
DATE:

Aim:
To write a c program to implement insertion sort.

Algorithm:
1. Read n elements in an array.
2. The first element is considered and inserted at zeroth position in thearray.
3. The second element is considered and compare with the elements in the zeroth position.
4. The smallest element is inserted in its appropriate position in thearray.
5. Similarly the entire list of elements are compared and inserted in their appropriate
position in array.
6. Print the sorted list of elements.

Program:

#include<stdio.h>
#include<conio.h>
void main()
{
Int total_count,counter1,counter2,minimum,
temp_value;
int a[20];
printf("\n Enter the Number of Elements: ");
scanf("%d",&total_count);
printf("\n Enter %d Elements: ",total_count);
for(counter1=0;counter1<total_count; counter1++)
{
scanf("%d",&a[counter1]);
}
for(counter1=0;
counter1<total_count-1;counter1++)
{
minimum=counter1;
for(counter2=counter1+1;
counter2<total_count;counter2++)
{
if(a[minimum]>a[counter2])
minimum=counter2;
}
if(minimum!=counter1)
{
temp_value=a[counter
1];
a[counter1]=a[minimu
m];
 a[minimum]=temp_va
lue;
}
}
printf("\n The Sorted array in ascending order: ");
for(counter1=0;counter1<total_count;
counter1++
{
printf("%d ",a[counter1]);
}
getch();
}

OUTPUT:
Please enter the total count of the elements that you want to sort: 5
Please input the elements that has to be sorted: 5
4
3
2
1
Output generated after using insertion sort1 2 3 4
5

Result:
Thus a c program to implementation of insertion sort is executed successfully and the output is
verified.
EX NO:4(B) HEAP SORT

DATE:

Aim:

To write a c program to implement Heap sort.

Algorithm:

[Link] n elements in an array.

[Link] a max-heap from the array to be sorted.

[Link] with the last non-leaf node(i.e.,the parent of the last element) and

perform heapify operation for each node in reverse level order until the root is reached.

[Link] extract the maximum element from the heap and move it to the end of the array.

[Link] the first (maximum) element with the last element, decrease the heap size by one,and

perform heapify operation on the root to maintain the heap property.

[Link] this step until all elements have been extracted from the heap and moved

to the end of the array.

[Link] array is now sorted in ascending order

Program:

#include <stdio.h>

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

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

largest = left;

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

largest = right;
if (largest != i) {

int temp = arr[i];

arr[i] = arr[largest];

arr[largest] = temp;

heapify(arr, n, largest);

void heapSort(int arr[], int n) {

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

heapify(arr, n, i);

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

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);
}

void printArray(int arr[], int n) {

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

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

printf("\n");

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

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

printf("Original array:\n");
printArray(arr, n);

heapSort(arr, n);

printf("Sorted array:\n");

printArray(arr, n);

return 0;

OUTPUT:

Original array:

12 11 13 5 6 7

Sorted array:

5 6 7 11 12 13

Result:

Thus a c program to implementation of heap sort is executed successfully and the

output is verified.
EX NO:5 BFS(breadth-first search)
DATE:

Aim:
To write a c program to implementation of BFS(breadth first search).

Algorithm:
1. Create an undirected graph and set the value for visited array as 0 for all the vertices in
the graph.
2. Read a vertex from which you want to traverse the graph.
3. Mark the read vertex as 1 in visited array and insert it into queue.
4. Find the adjacent matrix for the vertex inside the queue, mark as visited and insert
into the queue.
5. Delete the vertex in the front of the queue.
6. Repeat steps 4 and 5 until the graph is completely traversed.

Program:

#include<stdio.h>
int q[20],top=-1,front=-1,
rear=-1,a[20][20],vis[20],stack[20];int delete();
void add(int item);
void bfs(int s,int n);
void main()
{
int n,i,s,ch,j;
printf("ENTER THE NUMBER VERTICES ");
scanf
("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 :",i,j);
scanf("%d",&a[i][j]);
}
}
printf("THE ADJACENCY MATRIX IS\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n");
}
for(i=1;i<=n;i++)
vis[i]=0;
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);
}
void bfs(int s,int n)
{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf(" %d",p);
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}
p=delete();
if(p!=0)
printf(" %d ",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}
void add(int item)
{
if(rear==19)
printf("QUEUEFULL");
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}
int delete()
{
int k; if((front>rear)||(front==1))
return(0);
else
{
k=q[front++];
return(k);
}
}

Output:

ENTER THE NUMBER VERTICES 3

ENTER 1 IF 1 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 1 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 1 HAS A NODE WITH 3 ELSE 0 1
ENTER 1 IF 2 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 2 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 2 HAS A NODE WITH 3 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 3 ELSE 0 1
THE ADJACENCY MATRIX IS
110
101
011
ENTER THE SOURCE
VERTEX : 22 1 3
Result:
Thus the c program to implementation of breadth first search isexecuted successfully
and the output is verified.

EX NO:6 DFS(depth first search)

DATE:
Aim:
To write a c program to implement the DFS(depth first search).

Algorithm:
1. Create an undirected graph and set the value for visited array as 0 for all the vertices in
the graph.
2. Read a vertex from which you want to traverse the graph.
3. Mark the read vertex as 1 in visited array and insert it into thestack.
4. Find one adjacent vertex mark it ass visited and insert it into thestack.
5. Delete the vertex in the top of the stack and find its adjacent vertex.
6. Repeat 4 and 5 until all the vertex traverse back and search for unvisited vertex.

Program:

#include<stdio.h>
int q[20],top=-1,front=-1,
rear=-1,a[20][20],vis[20],stack[20];
void dfs(int s,int n);
void push(int item);
int pop();
void main()
{
int n,i,s,ch,j;
printf("ENTER THE NUMBER VERTICES ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("THE ADJACENCY MATRIX IS\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n");
}
for(i=1;i<=n;i++)
vis[i]=0;
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);
dfs(s,n);
}

void dfs(int s,int n)

{
int i,k;
push(s);
vis[s]=1;
k=pop();
if(k!=0)
printf(" %d ",k);
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0)&&(vis[i]==0))
{
push(i);
vis[i]=1;
}
k=pop();
if(k!=0)
printf(" %d ",k);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}
void push(int item)
{
if(top==19)
printf("Stack overflow ");
else
stack[++top]=item;
}
int pop()
{
int k;
if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}

Output:

ENTER THE NUMBER VERTICES 3

ENTER 1 IF 1 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 1 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 1 HAS A NODE WITH 3 ELSE 0 0
ENTER 1 IF 2 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 2 HAS A NODE WITH 2 ELSE 0 0
ENTER 1 IF 2 HAS A NODE WITH 3 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 1 ELSE 0 0
ENTER 1 IF 3 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 3
ELSE 0 1THE ADJACENCY MATRIX IS
110
101
011
ENTER YOUR SOURCE
VERTEX : 22 3 1
Result:
Thus the c program to implement the DFS is executed successfullyand the
output is verified.
[Link] DIJKSTRA’S ALGORITHM
DATE :

AIM:
To write a C program to implement Dijkstra’s algorithm.

ALGORITHM:
1. Start.
2. Define INFINITY as 9999.
3. Get the vertices and adjacency matrix to find the distance and path.
4. Get the starting node where the process starts.
5. If G [i][j] = 0 then declare cost [i][j] as infinity.
6. Else cost [i][j] = G [i][j].
7. For each node distance will be the cost [startnode][i].
8. Visited status will be 0 initially for all nodes.
9. Let minimum distance be infinity.
10. If (distance [i] < mindistance and not visited [i] then mindistance = distance [i].
11. For each not visited node if mindistance + cost [nextnode][i] < distance [i] then distance [i] =
mindistance + cost [nextnode][i].
12. Print distance of each node and path.
13. Stop.

PROGRAM:
/* Implementation of shortest path using Dijkstra’s algorithm */
#include <stdio>
#define INFINITY 9999
#define MAX 10
void dijkstra(int G [MAX][MAX],int n,int startnode);
int main ()
{
int G [MAX][MAX], i, j, n, u;
clrscr ();
printf ("Enter no. of vertices:");
scanf (<%d=, &n);
printf ("\nEnter the adjacency matrix:\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf ("%d", &G [i][j]);
printf ("\nEnter the starting node:");
scanf ("%d", &u);
dijkstra (G, n, u);
return 0;
}
void dijkstra (int G [MAX][MAX], int n, int startnode)
{
int cost [MAX][MAX],distance [MAX], pred [MAX];
int visited [MAX], count, mindistance, nextnode, i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (G [i][j] == 0)
cost [i][j] = INFINITY;
else cost [i][j] = G[i][j];
}
for (i = 0; i < n; i++)
{
distance [i] = cost [startnode][i];
pred [i] = startnode;
visited [i] = 0;
}
distance [startnode] = 0;
visited [startnode] = 1;
count = 1;
while (count < n-1)
{
mindistance = INFINITY;
for (i = 0; i < n; i++)
if (distance [i] < mindistance &&! visited [i])
{
mindistance = distance [i];
nextnode = i;
}
visited [nextnode] = 1;
for (i = 0; i < n; i++)
if (!visited [i])
if (mindistance + cost [nextnode][i] < distance [i])
{
distance [i] = mindistance + cost [nextnode][i];
pred [i]= nextnode;
}
count++;
}
for (i = 0; i < n; i++)
if (i != startnode)
OUTPUT:
Enter the no. of vertices:4
Enter the adjacency matrix:
0111
1010
1100
1010
Enter the starting node:1
Distance of 0 = 1
Path = 0 <-1
Distance of 2=1
Path = 2<-1
Distance of 3 = 2
Path = 3 < -0 < -1

RESULT:
Thus, the implementation of Dijkstra’s algorithm was executed successfully.
EX NO:8 PRIM’S ALGORITHM

DATE:

Aim :

To write a program to find minimum cost spanning tree using Prim's Algorithm.

Algorithm :

Step 1: Determine an arbitrary vertex as the starting vertex of the MST.

Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as fringe
vertex).

Step 3: Find edges connecting any tree vertex with the fringe vertices.

Step 4: Find the minimum among these edges.

Step 5: Add the chosen edge to the MST if it does not form any cycle.

Step 6: Return the MST and exit

Program :

#include<stdio.h>

#include<conio.h>

int n,cost[10][10],temp,nears[10];

void readv();

void primsalg();

void readv()

{
int i,j;

printf("\n Enter the No of nodes or vertices:");

scanf("%d",&n);

printf("\n Enter the Cost Adjacency matrix of the given graph:");

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

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

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

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

cost[i][j]=999;

void primsalg()

int k,l,min,a,t[10][10],u,i,j,mincost=0;

min=999;

for(i=1;i<=n;i++) //To Find the Minimum Edge E(k,l)

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

if(i!=u)

{
if(cost[i][u]<min)

min=cost[i][u];

k=i;

l=u;

t[1][1]=k;

t[1][2]=l;

printf("\n The Minimum Cost Spanning tree is...");

printf("\n(%d,%d)-->%d",k,l,min);

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

if(i!=k)

if(cost[i][l]<cost[i][k])

nears[i]=l;

else

nears[i]=k;

}
}

nears[k]=nears[l]=0;

mincost=min;

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

j = findnextindex(cost,nears);

t[i][1]=j;

t[i][2]=nears[j];

printf("\n(%d,%d)-->%d",t[i][1],t[i][2],cost[j][nears[j]]);

mincost=mincost+cost[j][nears[j]];

nears[j]=0;

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

if(nears[k]!=0 && cost[k][nears[k]]>cost[k][j])

nears[k]=j;

printf("\n The Required Mincost of the Spanning Tree is:%d",mincost);

int findnextindex(int cost[10][10],int nears[10])

int min=999,a,k,p;

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

{
p=nears[a];

if(p!=0) {

if(cost[a][p]<min)

min=cost[a][p];

k=a;

return k;

void main()

clrscr();

readv();

primsalg();

getch();

OUTPUT :

Enter the no of nodes or vertices?

Enter the cost Adjacency matrix of the given:0 28 0 0 0 10 0

28 0 16 0 0 0 14

0 16 0 12 0 0 0

0 0 12 0 22 0 18

0 0 0 22 0 25 24

10 0 0 0 25 0 0
0 14 0 0 24 0 0

The Minimum Cost Spanning tree is...

(1,6)-->10

(5,6)-->25

(4,5)-->22

(3,4)--->12

(2,3)-->16

(7,2)-->14

The requriedMincost of Spanning tree is :99

RESULT:

Thus the c program to implementation of Prim's Algorithm is executed successfully and the output is
verified.
EX NO:9 Floyd’s Algorithm
DATE:

Aim:
To write a c program to implement Floyd’s Algorithm.

Algorithm:
1 Create a matrix A0 of dimension n*n where n is the number of vertices.
a)The row and the column are indexed as i and j respectively.
b)i and j are the vertices of the graph.
2. Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex.
If there is no path from ith vertex to jth vertex, the cell is left as infinity.
3. Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex.
If there is no path from ith vertex to jth vertex, the cell is left as infinity.
[Link] is, if the direct distance from the source to the destination is greater than the path through the
vertex k, then the cell is filled with A[i][k] + A[k][j].
[Link], A2 is created using A1. The elements in the second column and the second row are left
as they are.
a)In this step, k is the second vertex (i.e. vertex 2).
b)The remaining steps are the same as in step 2.
6. A4 gives the shortest path between each pair of vertices.

PROGRAM:

#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); }
int main() {
int p[10][10],w,n,e,u,v,i,j;
clrscr();
 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]);}
getch();
}

OUTPUT:

Enter the number of vertices:3

Enter the number of edges: 2
Enter the end vertices of edge1 with its weight
125
Enter the end vertices of edge2 with its weight
486
Matrix of input data:
999 5 999
999 999 999
999 999 999
Transitive closure:
0 5 999
999 0 999
999 999 0

The shortest paths are:

<1,2>=5
<1,3>=999
<2,1>=999
<2,3>=999
<3,1>=999
<3,2>=999

Result:
 Thus the c program to implementation of Floyd’s Algorithm is executed successfully and the
output is verified.

EX NO:10 WARSHALL’S ALGORITHM

DATE:

Aim:

To write a c program to implement Warshall's Algorithm.

Algorithm:

[Link] the solution matrix same as the input graph matrix as a first step.

[Link] update the solution matrix by considering all vertices as an intermediate vertex.

[Link] idea is to one by one pick all vertices and updates all shortest

paths which include the picked vertex as an intermediate vertex in the shortest path.

[Link] we pick vertex number k as an intermediate vertex,we already have considered vertices {0, 1,
2, .. k-1} as intermediate vertices.

[Link] every pair (i, j) of the source and destination vertices respectively, there are two possible cases.

6.k is not an intermediate vertex in shortest path from i to j.

[Link] keep the value of dist[i][j] as it is.

8.k is an intermediate vertex in shortest path from i to j.

[Link] update the value of dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j].

PROGRAM:

#include<stdio.h>

#include<conio.h>

#include<math.h>

int max(int,int);
void warshal(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++)

p[i][j]=max(p[i][j],p[i][k]&&p[k][j]);

int max(int a,int b) {

if(a>b)

return(a);

else

return(b);

void main() {

int p[10][10]= {0},n,e,u,v,i,j ;

clrscr();

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

scanf("%d",&n);

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

scanf("%d",&e);

for (i=1;i<=e;i++) {

printf("\n Enter the end vertices of edge %d:",i);

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

p[u][v]=1;

}
 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");

warshal(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");

getch();

Output:

Enter the number of vertices:4

Enter the number of edges:4

Enter the end vertices of edge 1:2

Enter the end vertices of edge 2:3

3
Enter the end vertices of edge 3:1

Enter the end vertices of edge 4:4

Matrix of input data:

0 1 0 0

0 0 1 0

0 0 1 0

0 1 0 0

Transitive closure:

0 1 1 0

0 0 1 0

0 0 1 0

0 1 1 0

Result:
 Thus the c program to implementation of Warshall's Algorithm is executed successfully and
the output is verified.

EX NO:11 Divide and Conquer Algorithm

DATE:
Aim:

To write a c program to implement Maximum and Minimum using Divide and Conquer.

Algorithm:

1. Write a function called divide_and_conquer that takes the following parameters:

a) arr: The array to be searched

b) left: The index of the left end of the subarray to be searched

c) right: The index of the right end of the subarray to be searched

2. Check for the base cases:

a)If there is only one element in the subarray, set the maximum and minimum values to that
element and return the MaxMin struct.

b)If there are two elements in the subarray, compare them and set the maximum and minimum
values accordingly. Return the MaxMin struct.

c)If the base cases are not met, divide the subarray in half and recursively call divide_and_conquer
on each half:

[Link] mid equal to the index halfway between left and [Link] divide_and_conquer(arr, left, mid) to
find the maximum and minimum values in the left half of the subarray.

Call divide_and_conquer(arr, mid+1, right) .

[Link] the maximum and minimum values in the right half of the subarray.

[Link] the results of the left and right halves to find the maximum and minimum values of the entire
subarray:

[Link] the maximum value of the entire subarray equal to the larger of the maximum values of the left
and right halves.
Set the minimum value of the entire subarrayequal to the smaller of the minimum values of the left
and right halves.

[Link] the MaxMin struct with the maximum and minimum values of the entire subarray.

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 : 5

Enter the numbers :

10 20 30 40 50

Minimum element in an array : 10

Maximum element in an array : 50

Result:

Thus a c program to implementation of Divide and conquer is executed successfully

and the output is verified.

EX NO:12 N-Queens problem using Backtracking

DATE:

Aim:

To write a c program to Implement N Queens problem using Backtracking.

Algorithm:

[Link] an empty chessboard of size NxN.

[Link] with the leftmost column and place a queen in the first row of that column.

[Link] to the next column and place a queen in the first row of that column.

[Link] step 3 until either all N queens have been placed or it is impossible to place a queen in the
current column without violating the rules of the problem.

[Link] all N queens have been placed, print the solution.

[Link] it is not possible to place a queen in the current column without violating the rules of the problem,
backtrack to the previous column.

[Link] the queen from the previous column and move it down one row.

[Link] steps 4-7 until all possible configurations have been tried.

[Link] the program.

Program:

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

int board[20],count;

int main(){
int n,i,j;

void queen(int row,int n);

printf("N Queens Problem Using Backtracking");

printf("\n\nEnter number of Queens:");

scanf("%d",&n);

queen(1,n);

return 0;

} //function for printing the solution

void print(int n)

int i,j;

printf("\n\nSolution %d:\n\n",++count);

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

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

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

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

for(j=1;j<=n;++j) //for nxn board

if(board[i]==j)

printf("\tQ"); //queen at i,j position

else

printf("\t-"); //empty slot

}}

int place(int row,int column)

{

int i;

for(i=1;i<=row-1;++i)

//checking column and digonal conflicts

if(board[i]==column)

return 0;

else

if(abs(board[i]-column)==abs(i-row))

return 0;}

return 1; }//no conflicts

//function to check for proper positioning of queen

void queen(int row,int n)

int column;

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

if(place(row,column))

board[row]=column; //no conflicts so place queen

if(row==n) //dead end

print(n); //printing the board configuration

else //try queen with next position

queen(row+1,n);

}}
Output:

N Queens Problem Using Backtracking

Enter number of Queens:4

Solution 1:

1 2 3 4

1 - Q - -

2 - - - Q

3 Q - - -

4 - - Q -

Solution 2:

1 2 3 4

1 - - Q -

2 Q - - -

3 - - - Q

4 - Q - -

Result:
 Thus the c program to implement of N Queens problem using Backtracking is executed
successfully and the output is verified.

EX NO:13 TRAVELING SALESPERSON ALGORITHM

DATE:

AIM:

To write a C program to find the optimal solution for using the Traveling Salesperson
Algorithm

ALGORITHM:

1: Travelling salesman problem takes a graph G {V, E} as an input and declare another graph as the
output (say G’)

which will record the path the salesman is going to take from one node to another.

2: The algorithm begins by sorting all the edges in the input graph G from the least distance to the
largest distance.

3: The first edge selected is the edge with least distance, and one of the two vertices (say A and B)
being the origin node (say A).

4: Then among the adjacent edges of the node other than the origin node (B), find the least cost edge
and add it onto the output graph.

5: Continue the process with further nodes making sure there are no cycles in the output graph and
the path reaches back to the origin node A.

6: However, if the origin is mentioned in the given problem, then the solution must always start from
that node only.

Let us look at some example problems to understand this better.

PROGRAM:

#include <stdio.h>
int tsp_g[10][10] = {

{12, 30, 33, 10, 45},

{56, 22, 9, 15, 18},

{29, 13, 8, 5, 12},

{33, 28, 16, 10, 3},

{1, 4, 30, 24, 20}

};

int visited[10], n, cost = 0;

void travellingsalesman(int c){

int k, adj_vertex = 999;

int min = 999;

visited[c] = 1;

printf("%d ", c + 1);

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

if((tsp_g[c][k] != 0) && (visited[k] == 0)) {

if(tsp_g[c][k] < min) {

min = tsp_g[c][k]; }

adj_vertex = k; } }

if(min != 999) {

cost = cost + min;}

if(adj_vertex == 999) {

adj_vertex = 0;

printf("%d", adj_vertex + 1);

cost = cost + tsp_g[c][adj_vertex];

return; }

travellingsalesman(adj_vertex);}
int main(){

int i, j;

n = 5;

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

visited[i] = 0;}

printf("\n\nShortest Path:\t");

travellingsalesman(0);

printf("\nMinimum Cost: \t");

printf("%d\n", cost);

return 0;

OUTPUT:

Shortest Path: 154321

Minimum Cost: 99

RESULT:
 Thus the c program to implementation of Traveling Salesperson Algorithm

is executed successfully and the output is verified.

EX NO:14 ALGORITHM FOR FINDING Kth SMALLEST NUMBER

DATE:

AIM:

To write a C program to find randomized algorithms for finding the kth smallest

number.

ALGORITHM:

1: Define an array A of n distinct integers.

2: Choose a random pivot element p from A.

3: Partition A into two subarrays, L and R, such that L contains all elements less than p, and R
contains all elements greater than p.

4: If k <= |L|, then recursively apply the algorithm to the subarray L.

5: If k = |L| + 1, return p as the kth smallest element.

6: If k > |L| + 1, then recursively apply the algorithm to the subarray R with the kth smallest element
being the (k - |L| - 1)th smallest element in R.

PROGRAM:

#include<stdio.h>

#include<math.h>

#include<time.h>

#include<stdlib.h>
int N = 10;

int A[20];

void swap(int dex1, int dex2)

int temp = A[dex1];

A[dex1] = A[dex2];

A[dex2] = temp; }

int partition(int start, int end)

int i = start + 1;

int j = i;

int pivot = start;

for (; i< end; i++)

if (A[i] < A[pivot])

swap(i, j);

j++;} }

if (j <= end)

swap(pivot, (j - 1));

return j - 1; }

void quick_sort(int start, int end, int K)

int part;

if (start < end)

{
 part = partition(start, end);

if (part == K - 1)

printf("Kth smallest element : %d ", A[part]);

if (part > K - 1)

quick_sort(start, part, K);

else

quick_sort(part + 1, end, K);

return;

int main(int argc, char **argv)

int i;

time_t seconds;

time(&seconds);

srand((unsigned int) seconds);

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

A[i] = rand() % (100 - 1 + 1) + 1;

printf("The original sequence is: ");

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

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

printf("\nEnter the Kth smallest you want to find:");

int k;

scanf("%d", &k);

quick_sort(0, N, k);

}
OUTPUT:

The original sequence is: 74 8 74 28 61 10 31 82 29 8

Enter the Kth smallest you want to find:3

Kth smallest element : 10

RESULT:
 Thus the c program to find randomized algorithms for finding the kth smallest

number is executed successfully and the output is verified.