Ir ungattukottai, Chennai Banglore

Highway
Sriperumbudur Taluk, Kancheepuram Dist., Chennai-
602117.

Nam :
e
Register No.
:
Lab :

Branc :
h
Year :

Semeste :
r
 P. B. College of
Engineering
Irrungattukottai, Chennai Banglore
Highway

Sriperumbudur Taluk, Kancheepuram Dist., Chennai-

602117.

Registration No. :

Certificate
Certified that this is a bonafide record of the practical work done by
Mr./Ms……………………………………………………………………………………………

of B.E./[Link]/M.E. (… ...................................................................... )
………………………… Department during the academic year 20 - 20
in the .................................................................................. Laboratory

Staff - in – charge Head of Department

Submitted for the University Practical Examination held on……………

Internal Examiner External Examiner

 CONTENTS

Date Date
S.N of Name of the Page of Remark
o Experime Experiments No. Submissio s
nt n
 CONTENTS

Date Date
[Link] of Name of the Page of Remark
Experime Experiments No. Submissio s
nt n
Ex. No. LINEAR SEARCH
1
Date
:

Aim
To Implement Linear Search and calculate the time required
for an to search
element.

Algorith
m 1. Step 1: set pos
2. = -1
Step 2: set i
3. =1
Step 3: repeat step 4 while i
4. <= n
Step 4: if a[i] ==
5. val
set pos
6. =i
print
7. pos
go to step
8. 6
[end of
9. if]
set ii = i
10 +1
[end of
.11 loop]
Step 5: if pos =
.
12 -1
print "value is not present in the
.13 array "
[end of
14.
. if]
Step 6:
exit

4
 Progra
m

// Online C compiler to run C program

#include<stdio.h>
online
#include<time.h>
#include<stdlib.h>
#define max 20
int pos;
int linsearch (int,int[],int);
void main()
{ int ch=1; double t; int n,i,a [max],k,op,low,high,pos;
clock_t begin,end,ctime;
double cpu_time_used;
begin=clock();
end=clock();
while(ch)
{
printf("\n.......MENU. \n [Link] search \n [Link] \n");
printf("\n enter your choice\n");
scanf("%d",&op);
switch(op)
{

case 1: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);
ctime=(end-begin)/cpu_time_used;
printf("\n Time taken is %ld CPU cycles \n",ctime);
break;

default:printf("Invalid choice entered \n");

exit(0);
}
printf("\n Do you wish to run again(1/0) \n");
scanf("%d",&ch);
}
5
}

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

Sample
output:

Resul
t
Thus the program to execute the linear Search was executed successfully.

6
 EX RECCURSIVE BINARY
DATE NO:2 SEARCH
:

AIM:
To Implement the recursive binary search and calculate the CPU running time
of the algorithm.

ALGORITHM
1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half
subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.

PROGRAM
CODE:
#include<stdio.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;
long tick1,tick2;
long elapsed=tick2-tick1;
double elapsed_time = ((double)elapsed/CLOCKS_PER_SEC);

while(ch)
{
printf("\n.......MENU \n [Link] \n [Link] search \n [Link] \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;
tick1=clock();
7
pos=binsearch(n,a,k,low,high);
tick2=clock(); if(pos==-1)
printf("\n\nUnsuccessful search");
else
printf("\n element %d is found at position %d",k,pos+1);

printf("Time taken by the CPU is %lf seconds \n",elapsed_time);

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);
tick1=clock();
pos=linsearch(n,a,k);
tick2=clock();
if(pos==-1)
printf("\n\n Unsuccessful search");
else
printf("element %d is found at position %d",k,pos+1);
printf("Time taken by the CPU is %lf seconds \n",elapsed_time);
break;
default:printf("Invalid choice entered \n");
exit(0);
}
printf("\n Do you wish to run again(1/0) \n");
scanf("%d",&ch);
}

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

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

SAMPLE OUTPU T

RESULT
Thus the program to implement the recursive binary search was executed successfully.

9
 EX NAÏVE PATTERN SEARCH
DATE: NO :3

AIM:
To perform 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 [ ].

ALGORITHM:
1. n ← length [T]
2. m ← length [P]
3. fOr s ← 0 tO n -m
4. do if P [1.....m] = T [s + 1 s + m]
5. then print "Pattern occurs with shift"

PROGRAM CODE:

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

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

10
SAMPLE OUTPUT

Result
:

Thus the naïve pattern matching algorithm was implemented

successfully

11
EX INSERTION SORT
NO :4a
DATE:

AIM
To Sort a given set of elements using the Insertion sort method and determine the time
required to sort the elements.

ALGORITHM
1. Iterate from arr[1] to arr[N] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare it to the elements
before. Move the greater elements one position up to make space for the
swapped element.

PROGRAM
#include <math.h>
#include <stdio.h>
#include <time.h>
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
sleep(4);
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{

12
 long tick1,tick2;
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
tick1 = clock();
insertionSort(arr, n);
tick2 = clock();
long elapsed = tick2-tick1;
double elapsed_time = ((double)elapsed/CLOCKS_PER_SEC);
printArray(arr, n);
printf("Time taken by the CPU is %lf seconds \n",elapsed_time);
return 0;
}

SAMPLE OUTPUT

RESULT
Thus the program to Sort a given set of elements using the Insertion sort method and
determine the time required to sort the elements

13
EX HEAP
NO
D A T:E4 b SORT
:

AI
M To Sort a given set of elements using the Heap sort method and determine the time
required to sort the elements.

ALGORIT
HM
1. First convert the array into heap data structure using heapify, then one by one delete the
root node of the Max-heap and replace it with the last node in the heap and then heapify
the root of the heap. Repeat this process until size of heap is greater than 1.
2. Build a heap from the given input array.
3. Repeat the following steps until the heap contains only one element:
a. Swap the root element of the heap (which is the largest element)
with the last element of the heap
b. Remove the last element of the heap (which is now in the correct
position).
c. Heapify the remaining elements of the heap.
4. The sorted array is obtained by reversing the order of the elements in the input array.

PRO G RA
M
#include <stdio.h>
#include<time.h>

void main()
{
int heap[10], num, i, j, c, rootElement,
tempVar; long tick1,tick2;

printf("\n Enter num of elements :");

scanf("%d", &num);
printf("\n Enter the nums : ");
for (i = 0; i < num; i++)
scanf("%d", &heap[i]);
for (i = 1; i < num; i++)
{
c = i;
do
{
rootElement = (c - 1) / 2;
if (heap[rootElement] < heap[c]) /* to create MAX heap array */

14
 {
tempVar = heap[rootElement];
heap[rootElement] = heap[c];
heap[c] = tempVar;
}
c = rootElement;
} while (c != 0);
}
tick1=clock();
printf("Heap array : ");
for (i = 0; i < num;
i++)
printf("%d\t ", heap[i]);
for (j = num - 1; j >= 0; j--)
{
tempVar = heap[0];
heap[0] = heap[j];
heap[j] = tempVar;
rootElement = 0;
do
{
c = 2 * rootElement + 1;
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[rootElement]<heap[c] && c<j) {
tempVar = heap[rootElement];
heap[rootElement] = heap[c];
heap[c] = tempVar;
}
rootElement = c;
} while (c < j);
}
printf("\n The sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d",
heap[i]); tick2-clock();
long elapsed = tick2-tick1;
double elapsed_time = ((double)elapsed/CLOCKS_PER_SEC);
printf("Time taken by the CPU is %lf seconds \n",elapsed_time);

15
 SAMPLE OUTPUT

RESULT
Thus the program to implement heap sort was executed successfully

16
EX BREADTH FIRST
NO :5
DATE:

AIM:
To Develop a program to implement graph traversal using Breadth First Search

ALGORITHM

Start by putting any one of the graph's vertices at the back of a queue.

Take the front item of the queue and add it to the visited list.

Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited
list to the back of the queue.

Keep repeating steps 2 and 3 until the queue is empty.

PROGRAM

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue {
int items[SIZE];
int front;
int rear;
};

struct queue* createQueue();

void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node {
int vertex;
struct node* next;
};

struct node* createNode(int);

17
struct Graph {
int numVertices;
struct node**
adjLists; int* visited;
};

// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();

graph->visited[startVertex] = 1;
enqueue(q, startVertex);

while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
struct node* temp = graph-
>adjLists[currentVertex]; while (temp) {
int adjVertex = temp->vertex;

if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}

// Creating a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct
node)); newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// Creating a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct
Graph)); graph->numVertices = vertices;

18
 graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));

int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}

return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode =
createNode(dest); newNode->next =
graph->adjLists[src]; graph->adjLists[src]
= newNode;

// Add edge from dest to src

newNode = createNode(src);
newNode->next = graph-
>adjLists[dest]; graph->adjLists[dest] =
newNode;
}

// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}

// Check if the queue is empty

int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}

// Adding elements into queue

void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");

19
 else {if (q->front == -1) q-
>front = 0;
q- >rear++;
q->items[q->rear] = value;
}
}

// Removing elements from queue

int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is
empty"); item = -1;
} else {
item = q->items[q-
>front]; q->front++;
if (q->front > q->rear) {
printf("Resetting queue
"); q->front = q->rear = -
1;
}
}
return item;
}

// Print the queue

void printQueue(struct queue* q) {
int i = q->front;

if (isEmpty(q)) {
printf("Queue is
empty");
} else {
printf("\nQueue contains \n");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}

int main() {
struct Graph* graph =
createGraph(6); addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);

20
 addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);

bfs(graph, 0);

return 0;
}

SAMPLE OUTPUT:

RESULT:

Thus the program to implement the breadth first search was executed successfully.

21
EX DEPTH FIRST
NO :6
DATE:

AIM
To Implement the Graph traversal using depth first search.

ALGORITHM

Start by putting any one of the graph's vertices on top of a stack.

Take the top item of the stack and add it to the visited list.
Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the top of the stack.
Keep repeating steps 2 and 3 until the stack is empty.

PROGRAM

#include <stdio.h>
#include <stdlib.h>
// Globally declared visited array
int vis[100];
// Graph structure to store number
// of vertices and edges and
// Adjacency matrix
struct Graph {
int V;
int E;
int** Adj;
};
// Function to input data of graph
struct Graph* adjMatrix()
{
struct Graph* G = (struct Graph*)
malloc(sizeof(struct Graph));
if (!G) {
printf("Memory Error\n");
return NULL;
}
G->V = 7;
G->E = 7;

G->Adj = (int**)malloc((G->V) * sizeof(int*));

for (int k = 0; k < G->V; k++) {

22
 G->Adj[k] = (int*)malloc((G->V) * sizeof(int));
}

for (int u = 0; u < G->V; u++) {

for (int v = 0; v < G->V; v++) {
G->Adj[u][v] = 0;
}
}
G->Adj[0][1] = G->Adj[1][0] = 1;
G->Adj[0][2] = G->Adj[2][0] = 3;
G->Adj[1][3] = G->Adj[3][1] = 1;
G->Adj[1][4] = G->Adj[4][1] = 4;
G->Adj[1][5] = G->Adj[5][1] = 1;
G->Adj[1][6] = G->Adj[6][1] = 6;
G->Adj[6][2] = G->Adj[2][6] = 1;

return G;
}// DFS function to print DFS traversal of graph
void DFS(struct Graph* G, int u)
{
vis[u] = 1;
printf("%d ", u);
for (int v = 0; v < G->V; v++) {
if (!vis[v] && G->Adj[u][v]) {
DFS(G, v);
}
}
}
// Function for DFS traversal
void DFStraversal(struct Graph* G)
{
for (int i = 0; i < 100; i++) {
vis[i] = 0;
}
for (int i = 0; i < G->V; i++) {
if (!vis[i]) {
DFS(G, i);
}}}
// Driver code
void main()
{
struct Graph* G;
G = adjMatrix();
DFStraversal(G)
;
23
SAMPLE OUTPUT:

RESULT:

Thus the program to implement the graph traversal using depth first search was
completed successfully.

24
EX DIJIKSTRA’S
NO :7
DATE:

AIM
To implement a program to find the shortest paths to other vertices using Dijkstra’s
algorithm.

ALGORITHM

1. Set all vertices distances = infinity except for the source vertex, set the source distance
= 0.
2. Push the source vertex in a min-priority queue in the form (distance , vertex), as the
comparison in the min-priority queue will be according to vertices distances.
3. Pop the vertex with the minimum distance from the priority queue (at first the
popped vertex = source).
4. Update the distances of the connected vertices to the popped vertex in case of "current
vertex distance + edge weight < next vertex distance", then push the vertex with the
new distance to the priority queue.
5. If the popped vertex is visited before, just continue without using it.
6. Apply the same algorithm again until the priority queue is empty.

PROGRAM:

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the

graph #define V 9

// A utility function to find the vertex with minimum

// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <=
min) min = dist[v], min_index =
v;

25
 return min_index;}

void printSolution(int dist[])

{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t\t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source

// shortest path algorithm for a graph represented using
// adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the
// shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is

// included in shortest
// path tree or shortest distance from src to i is
// finalized

// Initialize all distances as INFINITE and stpSet[] as

// false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always

0 dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the

// picked vertex.
for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet,

// there is an edge from u to v, and total
// weight of path from src to v through u is
26
 // smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v]&&
dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array

printSolution(dist);
}

// driver's code
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

// Function call
dijkstra(graph, 0);

return 0;
}

27
SAMPLE OUTPUT:

RESULT

Thus the program to implement the shortest paths to other vertices using Dijkstra’s
algorithm was executed successfully.

28
EX PRIM’S ALGORITHM
NO :8
DATE:

AIM
To implement the minimum cost spanning tree of a given undirected graph 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 <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 5
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] <
min) min = key[v], min_index =
v;

return min_index;
}

int printMST(int parent[], int graph[V][V])

{
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i,
graph[i][parent[i]]);
}

void primMST(int graph[V][V])

29
{
// Array to store constructed MSTint parent[V];
// Key values used to pick minimum weight edge in
cut int key[V];
// To represent set of vertices included in
MST bool mstSet[V];

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first
// vertex.
key[0] = 0;

// First node is always root of MST

parent[0] = -1;

// The MST will have V vertices

for (int count = 0; count < V - 1; count++) {

// Pick the minimum key vertex from the

// set of vertices not yet included in MST
int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (int v = 0; v < V;
v++)

// graph[u][v] is non zero only for adjacent

// vertices of m mstSet[v] is false for vertices
// not yet included in MST Update the key only
// if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false
&& graph[u][v] < key[v])
parent[v] = u, key[v] =
graph[u][v];
}

// print the constructed MST

30
 printMST(parent, graph);
}

// Driver's code
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;
}

SAMPLE OUTPUT:

RESULT

This the program to implement the minimum cost spanning tree of a given undirected
graph using Prim’s algorithm.

31
EX FLOYD’S
NO :9
DATE:

AIM:

To implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem

ALGORITHM:

1. Initialize the solution matrix same as the input graph matrix as a first step.
2. Then update the solution matrix by considering all vertices as an intermediate vertex.
3. The 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.
4. When we pick vertex number k as an intermediate vertex, we already have considered
vertices {0, 1, 2, .. k-1} as intermediate vertices.
5. For every pair (i, j) of the source and destination vertices respectively, there are two
possible cases.
o k is not an intermediate vertex in shortest path from i to j. We keep the
value of dist[i][j] as it is.
o k is an intermediate vertex in shortest path from i to j. We 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:

// C Program for Floyd Warshall Algorithm

#include <stdio.h>

// Number of vertices in the

graph #define V 4

/* Define Infinite as a large enough

value. This value will be used
for vertices not connected to each other */
#define INF 99999

// A function to print the solution matrix

void printSolution(int dist[][V]);

// Solves the all-pairs shortest path

// problem using Floyd Warshall algorithm
void floydWarshall(int dist[][V])
{
int i, j, k;

32
 /* Add all vertices one by one to
the set of intermediate vertices.-
--> Before start of an iteration,
we have shortest distances
between all pairs of vertices
such that the shortest distances
consider only the
vertices in set {0, 1, 2, .. k-1} as
intermediate vertices.
----> After the end of an iteration,
vertex no. k is added to the set of
intermediate vertices and the set
becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of
// dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix

printSolution(dist);
}

/* A utility function to print solution

*/ void printSolution(int dist[][V])
{
printf(
"The following
matrix shows the
shortest
distances" "
between every
pair of vertices
\n");

33
 for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] ==
INF)
printf("%7s", "INF");

else

}
printf("%7d", dist[i][j]);
printf("\n");
}
}// driver's code int main()
{
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };

// Function call
floydWarshall(graph);
return 0;
}

SAMPLE OUTPUT:

RESULT

Thus the program to implement Floyd’s algorithm for the All-Pairs- Shortest-Paths
problem was executed successfully.

34
EX WARSHALL’S ALGORITHM
NO :10
DATE
:

AIM
To implement the transitive closure of a given directed graph using Warshall's algorithm

ALG OR I TH
M
1. Warshall(A[1...n, 1...n]) // A is the adjacency matrix
2. R(0) ← A
3. fOr k ← 1 tO n dO
4. fOr i ← 1 tO n dO
5. fOr j ← tO n dO
6. R(k)[i, j] ← R(k-1)[i, j] Or (R(k-1)[i, k] and R(k-1)[k, j])
7. return R(n)
PROGRAM

#include<stdio.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;
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++) {
35
 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");
}
}

36
 SAMPLE OUTPUT:

RESULT:
Thus the the transitive closure of a given directed graph using Warshall's algorithm
Was executed successfully.

37
EX FINDING MAXIMUM AND MINIMUM NUMBERS
NO :11 IN A ARRAY
DATE:

AIM:
To implement a program to find out the maximum and minimum numbers in a given list
of n numbers using the divide and conquer technique.

ALGORITHM:
1. Create two intermediate variables max and min to store the maximum and
minimum element of the array.
2. Assume the first array element as maximum and minimum both, say max = arr[0]
and min = arr[0].
3. Traverse the given array arr[].
4. If the current element is smaller than min, then update the min as the current element.
5. If the current element is greater than the max, then update the max as the
current element.
6. Repeat the above two steps 4 and 5 for the element in the array.

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
{
38
 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;
}

39
SAMPLE OUTPUT

RESULT
Thus the program to find out the maximum and minimum numbers in a given list of n
numbers using the divide and conquer technique was executed successfully.

40
EX MERGE SORT
NO :12A
DATE:

AIM:
To Implement merge sort methods to sort an array of elements and determine the time
required to sort.

ALGORITHM:
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop
PROGRAM:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

// Merges two subarrays of arr[].

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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

41
// into arr[l..r]
// Initial index of first subarray
i = 0;

// Initial index of second subarray

j = 0;

// Initial index of merged subarray

k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

// 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++;
}
}

// l is for left index and r is

// right index of the sub-array
// of arr to be sorted
void mergeSort(int arr[],
int l, int r)
{
42
if (l < r)
{
// Same as (l+r)/2, but avoids
// overflow for large l and h
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

// Driver code
int main()
{
long tick1,tick2;
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);
tick1=clock();
mergeSort(arr, 0, arr_size - 1);
tick2=clock();
long elapsed=tick2-tick1;
printf("\nSorted array is \n");
double elapsed_time = ((double)elapsed/CLOCKS_PER_SEC);

printArray(arr, arr_size);
printf("Time taken by the CPU is %lf seconds \n",elapsed_time);
return 0;
}

43
 SAMPLE OUTPUT

RESULT
Thus to Implement merge sort methods to sort an array of elements and determine the
time required to sort was executed successfully.

44
EX QUICK SORT
NO :12B
DATE:

AIM
To Implement Quick sort methods to sort an array of elements and determine the time
required to sort.

ALGORITHM
Step 1 − Pick an element from an array, call it
as pivot element. Step 2 − Divide an unsorted
array element into two arrays.
Step 3 − If the value less than pivot element come under first
sub array, the remaining elements with value greater than
pivot come in second sub array.

PROGRAM

#include<stdio.h>
#include <time.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
sleep(10);
if(first<last)
{ pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-
1);
45
 quicksort(number,j+1,last)
;
}
}
int main(){
int i, count, number[25];
long tick1,tick2;

printf("How many elements are u going to enter?: ");

scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
tick1=clock();
quicksort(number,0,count-1);
tick2=clock();
long elapsed =tick2-tick1;
double elapsed_time = ((double)elapsed/CLOCKS_PER_SEC);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
printf("Time taken by the CPU is %lf seconds \n",elapsed_time);
return 0;
}

SAMPLE OUTPUT:

RESULT:
Thus to Implement Quick sort methods to sort an array of elements and determine the
time required to sort was executed successfully.

46
EX N-QUEENS PROBLEM
NO :13
DATE:

AIM
To Implement N Queens problem using Backtracking

ALGORITHM:
1. Initialize an empty chessboard of size NxN.
2. Start with the leftmost column and place a queen in the first row of that column.
3. Move to the next column and place a queen in the first row of that column.
4. Repeat 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.
5. If all N queens have been placed, print the solution.
6. If it is not possible to place a queen in the current column without violating the rules of
the problem, backtrack to the previous column.
7. Remove the queen from the previous column and move it down one row.
8. Repeat steps 4-7 until all possible configurations have been tried.

PROGRAM:

#define N 4
#include <stdbool.h>
#include <stdio.h>

void printSolution(int board[N][N])

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

bool isSafe(int board[N][N], int row, int col)

{
int i, j;

/* Check this row on left side */

for (i = 0; i < col; i++)
if (board[row][i])
return false;

/* Check upper diagonal on left side */

for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
47
 return false;

/* Check lower diagonal on left side */

for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;

return true;
}

/* A recursive utility function to solve N

Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;

/* Consider this column and try

placing this queen in all rows one by
one */
for (int i = 0; i < N; i++) {
/* Check if the queen can be placed on
board[i][col] */
if (isSafe(board, i, col)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;

/* recur to place rest of the queens

*/ if (solveNQUtil(board, col + 1))
return true;

/* If placing queen in board[i][col]

doesn't lead to a solution, then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}

/* If the queen cannot be placed in any row in

this column col then return false */
return false;
}

bool solveNQ()
{
48
 int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };

if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}

printSolution(board);
return true;
}

// driver program to test above function

int main()
{
solveNQ();
return 0;
}

SAMPLE OUTPUT

RESULT
Thus to Implement N Queens problem using Backtracking was executed successfully.

49
EX TRAVELLING SALESPERSON PROBLEM
NO :14
DATE:

AIM
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.

ALGORITHM
1 . Start on an arbitrary vertex as current vertex.
2 . Find out the shortest edge connecting current vertex and an unvisited vertex V.
3 . Set current vertex to V.
4 . Mark V as visited.
5 . If all the vertices in domain are visited, then terminate.
6 . Go to step 2.
7 . The sequence of the visited vertices is the output of the algorithm.

PROGRAM
#include<stdio.h>
int a[10][10],n,visit[10];
int cost_opt=0,cost_apr=0;
int least_apr(int c);
int least_opt(int c);

void mincost_opt(int city)

{
int i,ncity;
visit[city]=1;
printf("%d-->",city);
ncity=least_opt(city);
if(ncity==999)
{
ncity=1;
printf("%d",ncity);
cost_opt+=a[city][ncity];
return;
}
mincost_opt(ncity);
}
void mincost_apr(int city)
{
int i,ncity;
visit[city]=1;
printf("%d-->",city);
ncity=least_apr(city);
if(ncity==999)
{
ncity=1;
printf("%d",ncity);

50
 cost_apr+=a[city][ncity];
return;
}
mincost_apr(ncity);
}

int least_opt(int c)
{
int i,nc=999;
int min=999,kmin=999;
for(i=1;i<=n;i++)
{
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<min)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost_opt+=kmin;
return nc;
}

int least_apr(int c)
{
int i,nc=999;
int min=999,kmin=999;
for(i=1;i<=n;i++)
{
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<kmin)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost_apr+=kmin;
return nc;
}
void main()
{
int i,j;
printf("Enter No. of cities:\n");
scanf("%d",&n);

printf("Enter the cost matrix\n");

for(i=1;i<=n;i++)
{
printf("Enter elements of row:%d\n",i );

51
 for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
visit[i]=0;
}
printf("The cost list is \n");
for(i=1;i<=n;i++)
{
printf("\n\n");
for(j=1;j<=n;j++)
printf("\t%d",a[i][j]);
}
printf("\n\n Optimal Solution :\n");
printf("\n The path is :\n");
mincost_opt(1);
printf("\n Minimum cost:");
printf("%d",cost_opt);

printf("\n\n Approximated Solution :\n");

for(i=1;i<=n;i++)
visit[i]=0;
printf("\n The path is :\n");
mincost_apr(1);
printf("\nMinimum cost:");
printf("%d",cost_apr);
printf("\n\nError in approximation is approximated solution/optimal solution=%f",
(float)cost_apr/cost_opt);
}

52
 SAMPLE OUTPUT

RESULT
Thus 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.

53
EX FINDING THE K th SMALLEST NUMBER
NO :15
DATE:

AIM
To implement randomized algorithms for finding the kth smallest number.

ALGORITHM
1. check if k>0&& k<=r-l+1:

● declare pos as randomPartition(arr,l,r).

● check if pos-1==k-1 than return arr[pos].
● check if pos-1>k-1 than recursively call kthsmallest(arr,l,pos-1,k).
● return recursively call kthsmallest(arr,pos+1,r,k-pos+l-1).
2. return INT_MAX.
PROGRAM

#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using

// QuickSort based method. ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);

// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);

// Else recur for right subarray

return kthSmallest(arr, pos+1, r, k-pos+l-1);
}

54
 // If k is more than the number of elements in the
array return INT_MAX;
}

void swap(int *a, int *b)

{
int temp = *a;
*a = *b;
*b = temp;
}

// Standard partition process of QuickSort(). It considers the last

// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]);
return i;
}

// Picks a random pivot element between l and r and partitions

// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return partition(arr, l, r);
}

// Driver program to test above methods

int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;

55
 cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}

SAMPLE OUTPUT

RESULT

Thus the program to implement randomized algorithms for finding the kth smallest
number was executed successfully.

56