CHRISTIAN COLLEGE OF ENGIINERING

AND TECHNOLOGY
ODDANCHATRAM – 624 619
DINDIGUL DT, TAMILNADU.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS3401 - ALGORITHMS LABORATORY

NAME :

REGISTER NO. :

BRANCH :
CHRISTIAN COLLEGE OF ENGINEERING AND
TECHNOLOGY
ODDANCHATRAM – 624 619
DINDIGUL DT, TAMILNADU.

BONAFIDE CERTIFICATE

This is to certify that this is a bonafide record of work done by

Mr./Ms. ______________________________________________________________________ in

____________________________________________________Laboratory during the Academic year

2023– 2024.

Register No:

STAFF IN CHARGE HEAD OF THE DEPARTMENT

Submitted for the University Practical Examination held on

INTERNAL EXAMINER EXTERNAL EXAMINER

Page Marks
Ex. No Date Name of the Experiment SIGNATURE
No. Awarded

1. Linear Search

2.
Recursive Binary Search
3.
Pattern Search – Naïve String
4.
Insertion sort and Heap sort
5.
Graph traversal using Breadth First Search

6.
Graph traversal using Depth First Search

7.
Dijkstra’s algorithm
8.
Prim’s algorithm
9.
Floyd’s algorithm

10. Warshall's algorithm.

11. Finding Maximum and minimum

numbers (Divide and conquer
technique).
12.
Merge sort and Quick sort
13.
N Queens problem using Backtracking
14.
Traveling Salesperson problem using
Approximation Algorithm
15.
Randomized algorithms for finding the
kth smallest number
Ex. No: 1
Date:
Linear Search

Aim
To create an array with the number of elements and search an element linearly.

Algorithm
Linear_Search ( Array X, Value i)
Step 1: Set j to 1
Step 2: If j > n, jump to step 7
Step 3: If X[j] == i, jump to step 6
Step 4: Then, increment j by 1 i.e. j = j+1
Step 5: Go back to step 2
Step 6: Display the element i which is found at particular index i, then jump to step 8
Step 7: Display element not found in the set of input elements.
Step 8: Exit/End

Program:

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int LINEAR_SEARCH(int inp_arr[], int size, int val)
{
for (int i = 0; i < size; i++)
if (inp_arr[i] == val)
return i;
return -1;
}
int main(void)
{
int arr[] = { 10, 20, 30, 40, 50, 100, 0 };
int key = 100;
int size = 10;
double time_spent = 0.0;
clock_t begin = clock();
int res = LINEAR_SEARCH(arr, size, key);
clock_t end = clock();
if (res == -1)
printf("ELEMENT NOT FOUND!!");
else
printf("Item is present at index %d", res);
time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
printf("The elapsed time is %f seconds", time_spent);
return 0;
}
Result:

Thus a C-Program for linear search was written, executed and verified successfully using
Turbo-C Compiler.
Ex. No: 2
Date:

Aim RECURSIVE BINARY SEARCH

To implement a recursive Binary Search and determine the time required to search an element.

Algorithm
Algorithm binary_search(nums, key):
return binary_search_helper(nums, key, 0, len(nums))

Algorithm binary_search_helper(nums, key, start_idx, end_idx):

middle_idx = (start_idx + end_idx) // 2
if start_idx == end_idx:
return None
if nums[middle_idx] > key:
return binary_search_helper(nums, key, start_idx, middle_idx)
elif nums[middle_idx] < key:
return binary_search_helper(nums, key, middle_idx + 1, end_idx)
else:
return middle_idx

Program:
#include <stdio.h>
#include <time.h>
int b_search(int num[], int Left, int Right, int key)
{
int Middle = 0;
while (Left <= Right) {
Middle = Left + (Right - Left) / 2;
if (num[Middle] == key) {
return Middle;
}
if (num[Middle] > key) {
return b_search(num, Left, Middle-1, key);
}
else {
return b_search(num, Middle+1, Right, key);
}
}
return -1;
}
int main()
{
int size = 0, key = 0, found = 0;
char ch = 'y';
printf("Enter the size of the array: ");
scanf("%d", & size);
int num[size];
printf("Enter the elements of the array in ascending order: ");
for (int i = 0; i < size; i++) {
scanf("%d", & num[i]);
}
while (ch == 'y' || ch == 'Y') {
printf("Enter the element to be searched: ");
scanf("%d", & key);
clock_t start = clock();
found = b_search(num, 0, size - 1, key);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
if (found == -1) {
printf("Element is not present in the array");
} else {
printf("Element found at index %d", found);
}
printf("\nTime taken: %f seconds\n", time_taken);
printf("Do you want to search for another key? (y/n): ");
scanf(" %c", &ch);
} return 0;}
Result:
Thus a C-Program for recursive binary search to search an element with time required
was written,executed and verified successfully
Ex. No: 3
Date:
PATTERN SEARCH

Aim
To Print all occurrences of pattern in a given text using Naive string pattern approach

Algorithm

Naive_algorithm(pattern, text)

Input − The text and the pattern

Output − locations, where the pattern is present in the text

Start
pat_len := pattern Size
str_len := string size
for i := 0 to (str_len - pat_len), do
for j := 0 to pat_len, do
if text[i+j] ≠ pattern[j], then
break
if j == patLen, then
display the position i, as there pattern found
End

Program

#include<stdio.h>
#include<string.h>
#include<time.h>
void search(char *pat, char *txt)
{
int i = 0;
int M = strlen(pat);
int N = strlen(txt);
for (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("\nPattern found at index %d \n\n", i);
}
}
int main()
{
float total;
char txt[100];
char pat[50];
printf("Please enter the text/string: ");
gets(txt);

printf("\nPlease enter the pattern: ");

gets(pat)
clock_t start=clock(); search(pat, txt);
clock_t stop= clock();
total+=(double)(stop-start)/CLOCKS_PER_SEC;
printf("The elapsed time is %f seconds",total);
return 0;
}

Result
Thus a pattern Occurrences matches with text will be printed using Naive String approach
successfully in Turbo C Compiler.
Ex. No: 4
Date:
INSERTION SORT AND HEAP SORT

Aim:
To implement a C-Program to sort a given set of elements using the Insertion sort and Heap sort
methods and determine the time required to sort the elements.

Algorithm:
Algorithm insertionSort(A: list of sortable items)
n = length(A)
for i = 1 to n - 1 do
j=i
while j > 0 and A[j-1] > A[j] do
swap(A[j], A[j-1])
j=j-1
end while
end for
end
Algorithm HeapSort(arr)

BuildMaxHeap(arr)

for i = length(arr) to 2

swap arr[1] with arr[i]

heap_size[arr] = heap_size[arr] ? 1

MaxHeapify(arr,1)

End

Algorithm BuildMaxHeap(arr)

heap_size(arr) = length(arr)

for i = length(arr)/2 to 1

MaxHeapify(arr,i)

End

Algorithm MaxHeapify(arr,i)

L = left(i)

R = right(i)

if L ? heap_size[arr] and arr[L] > arr[i]

largest = L

else
largest = i

if R ? heap_size[arr] and arr[R] > arr[largest]

largest = R

if largest != i

swap arr[i] with arr[largest]

MaxHeapify(arr,largest)

End

Program:
Insertion Sort:

#include <stdio.h>
#include<time.h>
int main(void)
{
int n, i, j, temp;
int arr[64];
float total;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
time_t start=clock();
for (i = 1; i < n; i++)
{
j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++)
{
printf("%d\n", arr[i]);
}
time_t stop=clock();
total=(double)(stop-start)/CLOCKS_PER_SEC;
pd("The elapsed time is%f seconds",total);
return 0;
}

Heap Sort:

#include <stdio.h>
#include<time.h>
void main()
{
int heap[10], num, i, j, c, rootElement, tempVar;
float total;
printf("\n Enter num of elements :");
scanf("%d", &num);
printf("\n Enter the nums : ");
for (i = 0; i < num; i++)
scanf("%d", &heap[i]);
time_t start=clock();
for (i = 1; i < num; i++)
{
c = i;
do
{
rootElement = (c - 1) / 2;
if (heap[rootElement] < heap[c]) /* to create MAX heap array */
{
tempVar = heap[rootElement];
heap[rootElement] = heap[c];
heap[c] = tempVar;
}
c = rootElement;
} while (c != 0);
}
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]);
time_t stop=clock();
total=(double)(stop-start)/CLOCKS_PER_SEC;
printf("The elapsed time is%f seconds",total);
}
Result:
Thus a C-Program to sort an element using insertion sort and Heap sort
algorithm was implemented successfully using Turbo C Compiler.
Ex. No: 5
Date:

GRAPH TRAVERSAL USING BREADTH FIRST SEARCH

Aim:
To write a C- program to traverse a tree and implement the array with visited node vertex using
Breadth first search.

PROCEDURE

Step 1: Consider the graph you want to navigate.

Step 2: Select any vertex in your graph (say v1), from which you want to traverse the graph.

Step 3: Utilize the following two data structures for traversing the graph.

Visited array(size of the graph)

Queue data structure

Step 4: Add the starting vertex to the visited array, and afterward, you add v1’s adjacent vertices to
the queue data structure.

Step 5: Now using the FIFO concept, remove the first element from the queue, put it into the visited
array, and then add the adjacent vertices of the removed element to the queue.

Step 6: Repeat step 5 until the queue is not empty and no vertex is left to be visited.

ALGORITHM:

BFS(start):
create a queue Q
mark start as visited and enqueue it onto Q
while Q is not empty:
dequeue a vertex v from Q
process v (e.g., print its value)
for each neighbor u of v
if u has not been visited:
mark u as visited and enqueue it onto Q
Program:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 5

struct Vertex {

char label;

bool visited;

};

//queue variables

int queue[MAX];

int rear = -1;

int front = 0;

intqueueItemCount = 0;

//graph variables

//array of vertices

struct Vertex* lstVertices[MAX];

//adjacency matrix

intadjMatrix[MAX][MAX];

//vertex count

intvertexCount = 0;

//queue functions

void insert(int data) {

queue[++rear] = data;

queueItemCount++;

}
intremoveData() {

queueItemCount--;

return queue[front++];

boolisQueueEmpty() {

returnqueueItemCount == 0;

//graph functions

//add vertex to the vertex list

voidaddVertex(char label) {

struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));

vertex->label = label;

vertex->visited = false;

lstVertices[vertexCount++] = vertex;

//add edge to edge array

voidaddEdge(intstart,int end) {

adjMatrix[start][end] = 1;

adjMatrix[end][start] = 1;

//display the vertex

voiddisplayVertex(intvertexIndex) {

printf("%c ",lstVertices[vertexIndex]->label);

//get the adjacent unvisited vertex

intgetAdjUnvisitedVertex(intvertexIndex) {

inti;

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

if(adjMatrix[vertexIndex][i] == 1 &&lstVertices[i]->visited == false)

returni;

return -1;

voidbreadthFirstSearch() {

inti;

//mark first node as visited

lstVertices[0]->visited = true;

//display the vertex

displayVertex(0);

//insert vertex index in queue

insert(0);

intunvisitedVertex;

while(!isQueueEmpty()) {

//get the unvisited vertex of vertex which is at front of the queue

inttempVertex = removeData();

//no adjacent vertex found

while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {

lstVertices[unvisitedVertex]->visited = true;

displayVertex(unvisitedVertex);

insert(unvisitedVertex);

}
}

//queue is empty, search is complete, reset the visited flag

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

lstVertices[i]->visited = false;

int main() {

inti, j;

for(i = 0; i<MAX; i++) { // set adjacency

for(j = 0; j<MAX; j++) // matrix to 0

adjMatrix[i][j] = 0;

addVertex('S'); // 0

addVertex('A'); // 1

addVertex('B'); // 2

addVertex('C'); // 3

addVertex('D'); // 4

addEdge(0, 1); // S - A

addEdge(0, 2); // S - B

addEdge(0, 3); // S - C

addEdge(1, 4); // A - D

addEdge(2, 4); // B - D

addEdge(3, 4); // C - D

printf("\nBreadth First Search: ");

breadthFirstSearch();
return 0;
}
Result:
Thus a C-Program was written to traverse the tree using Breadth first search algorithm was
implemented successfully.
Ex.No: 6
Date:

Graph traversal using Depth First Search

Aim
To write a C- program to traverse a tree and implement the array with visited node vertex using Depth
first search.

Procedure:

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

2. Take the top item of the stack and add it to the visited list.
3. 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.
4. Keep repeating steps 2 and 3 until the stack is empty.

Algorithm:

DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)

init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u)
}

Program

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#define MAX 5

structVertex{

char label;

bool visited;

};
//stack variables

int stack[MAX];

int top =-1;

//graph variables

//array of vertices

structVertex*lstVertices[MAX];

//adjacency matrix

intadjMatrix[MAX][MAX];

//vertex count

intvertexCount=0;

//stack functions

voidpush(int item){

stack[++top]= item;

intpop(){

return stack[top--];

intpeek(){

return stack[top];

boolisStackEmpty(){

return top ==-1;

//graph functions

//add vertex to the vertex list

voidaddVertex(char label){

structVertex* vertex =(structVertex*)malloc(sizeof(structVertex));

vertex->label = label;
vertex->visited = false;

lstVertices[vertexCount++]= vertex;

//add edge to edge array

voidaddEdge(intstart,int end){

adjMatrix[start][end]=1;

adjMatrix[end][start]=1;

//display the vertex

voiddisplayVertex(intvertexIndex){

printf("%c ",lstVertices[vertexIndex]->label);

//get the adjacent unvisited vertex

intgetAdjUnvisitedVertex(intvertexIndex){

inti;

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

if(adjMatrix[vertexIndex][i]==1&&lstVertices[i]->visited == false){

returni;

return-1;

voiddepthFirstSearch(){

inti;

//mark first node as visited

lstVertices[0]->visited = true;

//display the vertex

displayVertex(0);
//push vertex index in stack

push(0);

while(!isStackEmpty()){

//get the unvisited vertex of vertex which is at top of the stack

intunvisitedVertex=getAdjUnvisitedVertex(peek());

//no adjacent vertex found

if(unvisitedVertex==-1){

pop();

}else{

lstVertices[unvisitedVertex]->visited = true;

displayVertex(unvisitedVertex);

push(unvisitedVertex);

//stack is empty, search is complete, reset the visited flag

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

lstVertices[i]->visited = false;

intmain(){

inti, j;

for(i=0;i< MAX;i++){// set adjacency

for(j =0; j < MAX;j++)// matrix to 0

adjMatrix[i][j]=0;

addVertex('S');// 0

addVertex('A');// 1

addVertex('B');// 2
addVertex('C');// 3

addVertex('D');// 4

addEdge(0,1);// S - A

addEdge(0,2);// S - B

addEdge(0,3);// S - C

addEdge(1,4);// A - D

addEdge(2,4);// B - D

addEdge(3,4);// C - D

printf("Depth First Search: ");

depthFirstSearch();

return0;

}
Result:
Thus a C-Program was written to traverse the tree using Depth first search algorithm was
implemented successfully.
Ex.No: 7
Date:

Dijkstra’s algorithm

Aim:
To write a C- program to find the shortest paths to other vertices in a weighted connected graph using
Dijkstra’s algorithm.

Algorithm:
Algorithm dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0

while Q IS NOT EMPTY

U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]

Program:

#include <stdio.h>
#define INFINITY 9999
#define MAX 10
void Dijkstra(int Graph[MAX][MAX], int n, int start);
void Dijkstra(int Graph[MAX][MAX], int n, int start) {
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i, j;

// Creating cost matrix

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (Graph[i][j] == 0)
cost[i][j] = INFINITY;
else
cost[i][j] = Graph[i][j];

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

distance[i] = cost[start][i];
pred[i] = start;
visited[i] = 0;
}
distance[start] = 0;
visited[start] = 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++;
}

// Printing the distance

for (i = 0; i < n; i++)
if (i != start) {
printf("\nDistance from source to %d: %d", i, distance[i]);
}
}
int main() {
int Graph[MAX][MAX], i, j, n, u;
n = 7;

Graph[0][0] = 0;
Graph[0][1] = 0;
Graph[0][2] = 1;
Graph[0][3] = 2;
Graph[0][4] = 0;
Graph[0][5] = 0;
Graph[0][6] = 0;

Graph[1][0] = 0;
Graph[1][1] = 0;
Graph[1][2] = 2;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 3;
Graph[1][6] = 0;

Graph[2][0] = 1;
Graph[2][1] = 2;
Graph[2][2] = 0;
Graph[2][3] = 1;
Graph[2][4] = 3;
Graph[2][5] = 0;
Graph[2][6] = 0;
Graph[3][0] = 2;
Graph[3][1] = 0;
Graph[3][2] = 1;
Graph[3][3] = 0;
Graph[3][4] = 0;
Graph[3][5] = 0;
Graph[3][6] = 1;

Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 3;
Graph[4][3] = 0;
Graph[4][4] = 0;
Graph[4][5] = 2;
Graph[4][6] = 0;

Graph[5][0] = 0;
Graph[5][1] = 3;
Graph[5][2] = 0;
Graph[5][3] = 0;
Graph[5][4] = 2;
Graph[5][5] = 0;
Graph[5][6] = 1;

Graph[6][0] = 0;
Graph[6][1] = 0;
Graph[6][2] = 0;
Graph[6][3] = 1;
Graph[6][4] = 0;
Graph[6][5] = 1;
Graph[6][6] = 0;

u = 0;
Dijkstra(Graph, n, u);

return 0;
}
RESULT
Thus a C-Program to find the shortest path in a weighted connected graph using Dijkstra’s
Algorithm was implemented successfully.
Ex.No: 8
Date:

Prim’s algorithm
Aim:
To write a C-Program which finds the minimum cost spanning tree of a given undirected graph
using Prim’s algorithm.

Procedure:

Step 1: Initialize the minimum spanning tree with a vertex chosen at random.
Step 2: Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
Step 3: Keep repeating step 2 until we get a minimum spanning tree

Algorithm:

Algorithm Prims()
{
T = ∅;
U = { 1 };
while (U ≠ V)
let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U;
T = T ∪ {(u, v)}
U = U ∪ {v}
}
Program:
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]= {
0
}
,min,mincost=0,cost[10][10];
void main() {
clrscr();
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);
getch();
}
Result:

Thus a C-Program was written to find the minimum shortest path in an undirected graph using Prims
algorithm implemented successfully
Ex.No: 9
Date:

Floyd algorithm
Aim:

To implement a Floyd algorithm to find out a minimum shortest path in a weighted connected graph.

Algorithm:
Algorithm Floyd-Shortest_path(W[][],n)
n ← rows [W]
D0 ← W
for k ← 1 to n
do for i ← 1 to n
do for j ← 1 to n
do dij(k) ← min (dij(k-1),dik(k-1)+dkj(k-1) )
return D(n)
Program:
#include <stdio.h>
void main()
{
int wt[10][10],n,i,j;
void Floyd_shortest_path(int matrix[10][10],int n);
printf("\n Create a graph using adjacency matrix");
printf("\n How many vertices are there");
scanf(“%d”,&n);
printf("\n Enter the Elements");
printf("Enter 999 as infinity value");
for(i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
printf ("\nwt[%d][%d]",i,j);
scanf("%d",&wt[i][j]);
}
}
printf("\n Computing all pair shortest path\n");
Floyd_shortest_path(wt,n);
}
void Floyd_shortest_path(int wt[10][10],int n)
{
int D[5][10][10],i,j,k;
int min(int,int);
for(i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
D[0][i][j]=wt[i][j];
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)

{
for (j=1;j<=n;j++)
{
D[k][i][j]=min(D[k-1][i][j],(D[k-1][i][k]+D[k-1][k][j]));
}
}
}
for(k=0;k<=n;k++)
{
printf("R(%d)=\n",k);
for(i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
printf("%d",D[k][i][j]);
}
printf("\n");
}
}
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
Result:

Thus a Floyd algorithm was implemented successfully to find out the minimum shortest path in a weighted
connected graph using C-Compiler.
Ex.No: 10
Date:
Warshall’s Algorithm
Aim:

To develop a C-Program to Compute the transitive closure of a given directed graph using
Warshall's algorithm.

Algorithm:
Algorithm Warshall(V[G],n)
n ← |V[G]|
for i ← 1 to n
do for j ← 1 to n
do if i = j or (i, j) ∈ E [G]

then ←1
else ←0
for k ← 1 to n
do for i ← 1 to n
do for j ← 1 to n

dod ij(k) ←
Return T(n).

Program:

#include <stdio.h>
void main()
{
int matrix[10][10],n,i,j;
void Warshall(int matrix[10][10],int n);
printf("\n Create a graph using adjacency matrix");
printf("\n How many vertices are there");
scanf(“%d”,&n);
printf("\n Enter the Elements");
for(i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
printf ("\nmatrix[%d][%d]",i,j);
scanf("%d",&matrix[i][j]);
}
}
printf("\n Computing Transitive closure ….\n");
Warshall(matrix,n);
}
void Warshall(int matrix[10][10],int n)
{
int R[5][10][10],i,j,k;

for(i=1;i<=n;i++){
for (j=1;j<=n;j++)
{
R[0][i][j]=matrix[i][j];
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
R[k][i][j]=R[k-1][i][j]||(R[k-1][i][k]&&R[k-1][k][j]);
}
}
}
for(k=1;k<=n;k++)
{
printf("R(%d)=\n",k);
for(i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
printf("%d",R[k][i][j]);
}
printf("\n");
}
}
}
Result:

Thus a C-Program to compute the transitive closure of a given directed graph using Warshall's
algorithm was implemented Sucessfully.
Ex.No: 11
Date:
Finding Maximum and minimum numbers

(Divide and conquer technique)

Aim:

To write a C-program to find out the maximum and minimum numbers in a given list
of ‘n’ numbersusing the divide and conquer technique.

Algorithm:

Pseudo code:

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

struct Pair {
int min;
int max;
};

struct Pair getMinMax(int arr[], int low, int high) {

struct Pair minmax, left, right;
int mid;

// If there is only one element

if (low == high) {
minmax.max = arr[low];
minmax.min = arr[low];

return minmax;
}

// If there are two elements

if (high == low + 1) {
if (arr[low] > arr[high]) {
minmax.max = arr[low];
minmax.min = arr[high];
} else {
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}

// If there are more than two elements

mid = (low + high) / 2;
left = getMinMax(arr, low, mid);
right = getMinMax(arr, mid+1, high);

// Compare minimums of two parts

if (left.min < right.min) {
minmax.min = left.min;
} else {
minmax.min = right.min;
}

// Compare maximums of two parts

if (left.max > right.max) {
minmax.max = left.max;
} else {
minmax.max = right.max;
}

return minmax;
}

int main() {
int n, arr[1000], i;
struct Pair minmax;

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

scanf("%d", &n);

printf("Enter %d elements:\n", n);

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

minmax = getMinMax(arr, 0, n-1);

printf("Minimum element is %d\n", minmax.min);

printf("Maximum element is %d\n", minmax.max);

return 0;
}
Result:
Thus a C-program to find out the maximum and minimum numbers in a given list of
‘n’ numbers Using the divide and conquer technique was written and implemented
successfully.
Ex.No: 12
Date:

Merge sort and Quick sort

Aim:

To Implement a Merge sort and Quick sort methods to sort an array of elements and determine the time
required to sort using C-Program.

Algorithm:

Algorithm MergeSort(arr[],left,right,n)

if left > right

return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)

Algorithm QuickSort:
QUICKSORT (array A, start, end)
{
if (start < end)
{
p = partition(A, start, end)
QUICKSORT (A, start, p - 1)
QUICKSORT (A, p + 1, end)
}
}
PARTITION (array A, start, end)
{
pivot ? A[end]
i ? start-1
for j ? start to end -1 {
do if (A[j] < pivot) {
then i ? i + 1
swap A[i] with A[j]
}}
swap A[i+1] with A[end]
return i+1
}
Program:
Merge sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int left, int middle, int right) {
int i, j, k;
int n1 = middle - left + 1;
int n2 = right - middle;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[middle + 1 + j];
}
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void merge_sort(int arr[], int left, int right) {

if (left < right) {
int middle = left + (right - left) / 2;
merge_sort(arr, left, middle);
merge_sort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}

int main() {
int n, i;
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
int arr[n];
for (i = 0; i < n; i++) {
printf("Enter element %d: ", i + 1);
scanf("%d", &arr[i]);
}
clock_t t = clock();
merge_sort(arr, 0, n - 1);
t = clock() - t;
printf("Sorted array");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\nTime taken: %f seconds\n", ((double)t)/CLOCKS_PER_SEC);
return 0;
}

Quick Sort:

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

#define MAX 100000

// Function to swap two elements

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to partition the array

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // choose the last element as pivot
int i = low - 1; // index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

// Function to perform quicksort

void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
int n, i;
int arr[MAX];
clock_t start, end;
double time_taken;

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

scanf("%d", &n);

// Fill the array with random numbers

printf("Enter elements:");

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

{
scanf("%d",&arr[i]);
}

// Display the unsorted array

printf("\nUnsorted Array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

// Sort the array using Quick Sort

start = clock();
quickSort(arr, 0, n - 1);
end = clock();
time_taken = ((double) (end - start)) / CLOCKS_PER_SEC;

// Display the sorted array

printf("\n\nSorted Array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

// Display the time taken to sort the array

printf("\n\nTime taken: %f seconds\n", time_taken);

return 0;
}
Result:

Thus a C-Program to Implement a Merge sort and Quick sort methods to sort an array of elements and
determine the time required to sort was written and executed successfully.
Ex.No: 13
Date:
N Queens problem using Backtracking

Aim:

To write a C-Program to implement N-Queens problem using Backtracking

technique.

Procedure:
Step 1: If two queens are placed at position (i, j) and (k, l).
Step 2: Then they are on same diagonal only if (i - j) = k - l or i + j = k + l.
Step 3: The first equation implies that j - l = i - k.
Step 4: The second equation implies that j - l = k - i.
Step 5: Therefore, two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|
Algorithm:

Algorithm Place (k, i)

{
For j ← 1 to k - 1
do if (x [j] = i)
or (Abs x [j]) - i) = (Abs (j - k))
then return false;
return true;
}
Algorithm N - Queens (k, n)
{
For i ← 1 to n
do if Place (k, i) then
{
x [k] ← i;
if (k ==n) then
write (x [1. .. n));
else
N - Queens (k + 1, n);
}
}

Program:
include<stdio.h>
#include<math.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;
}
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)
{

if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}

return 1;
}

void queen(int row,int n)

{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column;
if(row==n)
print(n);

else
queen(row+1,n);}}}
Result:
Thus a C-Program to implement N-Queens Problem using Backtracking Techniques was written and
executed successfully.
Ex.No: 14
Date:

Traveling Salesperson problem usingApproximation Algorithm

Aim:
To write a C-Program to find out the optimal solution for the Traveling Salesperson problem and thensolve
the same problem instance using an approximation algorithm.
Procedure:
Step 1) We are considering our journey starting at city 1, visit other cities once and return to city 1.

Step 2) S is the subset of cities. According to our algorithm, for all |S| > 1, we will set the distance cost(i, S,
1) = ∝. Here cost(i, S, j) means we are starting at city i, visiting the cities of S once, and now we are at city j.
We set this path cost as infinity because we do not know the distance yet. So the values will be the
following:

Cost (2, {3, 4}, 1) = ∝ ; the notation denotes we are starting at city 2, going through cities 3, 4, and reaching
1. And the path cost is infinity. Similarly-

cost(3, {2, 4}, 1) = ∝

cost(4, {2, 3}, 1) = ∝

Step 3) Now, for all subsets of S, we need to find the following:

cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j), where j∈S and i≠j

That means the minimum cost path for starting at i, going through the subset of cities once, and returning to
city j. Considering that the journey starts at city 1, the optimal path cost would be= cost(1, {other cities}, 1).

Algorithm:
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, … , n} of size s
Cost (s, S, 1) = Infinity
for all i Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)

Program:
#include <stdio.h>
const int MAX=10;
int path[10];
static int k=0;
int count=0;
int perm[120][7];
int costoftour[120];
void swap(int *x,int *y)
{

int temp;
temp=*x;
*x=*y;
*y=temp;
}
void DFS(int current,int visited[10],int graph[10][10],int n)
{
int i;
visited[current] = 1;
path[k++]=current;
for(i=0;i<n;i++)
if(graph[current][i] && !visited[i])
DFS(i,visited,graph,n);
}
void permute(int *a,int i,int n)
{
int j,k;
if(i == n)
{
for(k=0;k<=n;k++)
{
perm[count][k+1]=a[k];
}
count++;
}
else
{
for(j=i;j<=n;j++)
{
swap((a+i),(a+j));
permute(a,i+1,n);
swap((a+i),(a+j));
}
}
}
int Approximate(int n,int cost[10][10])

{
int i,j,u,v,min,ApproxCost=0;
int sum,k,t[10][2],p[10],d[10],s[10],tree[10][10];
int source,count;
int visited[10];
for(i=0;i<n;i++)
visited[i]=0;
min=9999;
source=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(cost[i][j]!=0 && cost[i][j]<=min)
{
min=cost[i][j];
source=i;
}
}
}
for(i=0;i<n;i++)
{
d[i]=cost[source][i];
s[i]=0;
p[i]=source;
}
s[source]=1;
sum=0;
k=0;
count=0;
while(count != (n-1))
{
min=9999;
u = -1;
for(j=0;j<n;j++)
{
if(s[j] == 0)

{
if(d[j]<=min)
{
min=d[j];
u=j;
}
}
}
t[k][0]=u;
t[k][1]=p[u];
k++;
count++;
sum+=cost[u][p[u]];
s[u]=1;
for(v=0;v<n;v++)
{
if(s[v] == 0 && (cost[u][v]<d[v]))
{
d[v]=cost[u][v];
p[v]=u;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
tree[i][j]=0;
}
}
if(sum >= 9999)
printf("\n Spanning tree does not exist");
else
{
for(i=0;i<k;i++)

{
tree[t[i][0]][t[i][1]]=tree[t[i][1]][t[i][0]]=1;

}
DFS(0,visited,tree,n);
printf("\n The Approximate path is \n");
for(i=0;i<=k;i++)
{
printf("%d",path[i]);
printf("->");
ApproxCost+=cost[path[i]][path[i+1]];
}
printf("%d",path[0]);
ApproxCost+=cost[path[i]][path[0]];
printf("\n The Approximate minimum cost of the tour is:%d",ApproxCost);
return ApproxCost;
}
int main()
{
int graph[10][10]={{0,4,8,9,12},
{4,0,6,8,9},
{8,6,0,10,11},
{9,8,10,0,7},
{12,9,11,7,0}};
int Numofcity=5;
int intercities=4,i,j;
int optimal_cost=999,opt_cost_index,Approx_cost;
int city[4]={1,2,3,4};
permute(city,0,intercities-1);
for(i=0;i<24;i++)
{
for(j=0;j<5;j++)
{
costoftour[i]+=graph[perm[i][j]][perm[i][j+1]];
}
if(optimal_cost > costoftour[i])

{
optimal_cost=costoftour[i];

opt_cost_index=i;
}
}
printf("\n The optimal path ...");
for(i=0;i<Numofcity;i++)
{
printf("%d",perm[opt_cost_index][i]);
printf("->");
}
printf("%d",perm[opt_cost_index][i]);
printf("\n The optimal cost of the tour is:%d",optimal_cost);
Approx_cost=Approximate(Numofcity,graph);
printf("\nThe Error in Approximation is %d units",Approx_cost);
return 0;
}
Result:
Thus a C-program was written to find the optimal solution for traveling salesperson problem and also
determine the approximation error in the path executed successfully.
Ex.No: 15
Date:
Randomized algorithms for finding thekth smallest number

Aim:

To write a C-program to implement a randomized algorithms for finding the kth smallest number in a given
array.

Procedure:

Step 1:Select a random element from a array as a pivot.

Step 2:Then partition to the array around the pivot, its help to all the smaller element were placed before
in the pivot and all greater element are placed after the pivot.
Step 3:Then Check the position of the pivot. If it is the kth element then return it.
Step 4:If it is the less than the kth element then repeat the process of the subarray.
Step 5:If it is the greater then the kth element then repeat the process of the left subarray.

Algorithm:

int kthSmallest(int A[], int left, int right, int K)

{
if (left == right)
return A[left]
int pos = partition(A, left, right)
count = pos - left + 1
if ( count == K )
return A[pos]
else if ( count > K )
return kthSmallest(A, left, pos-1, K)
else
return kthSmallest(A, pos+1, right, K-i)
}
int partition(int A[], int l, int r)
{
int x = A[r]
int i = l-1
for ( j = l to r-1 )
{
if (A[j] <= x)
{
i=i+1
swap(A[i], A[j])
}
}
swap(A[i+1], A[r])
return i+1
}

Program:
#include<stdio.h>
#include<stdlib.h>
#define infinity 9999
int partition(int arr[],int low,int high);
int kthsmallest(int arr[],int low,int high,int K)
{
if (K>0 && K<= high-low + 1)
{
int pos=partition(arr,low,high);
if(pos-low == K-1)
return arr[pos];
if((pos-low) > (K-1))
return kthsmallest(arr,low,pos-1,K);
return kthsmallest(arr,pos+1,high,K-pos+low-1);
}
return infinity;
}
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[],int low,int high)
{
int range =(high-low)+1;
int rand_index=(rand() % range)+low;
swap(&arr[rand_index],&arr[high]);
int pivot_element = arr[high],i=low;
for(int j=low;j<=high-1;j++)
{
if(arr[j]<= pivot_element)
{
swap(&arr[i],&arr[j]);
i++;
}
}
swap(&arr[i],&arr[high]);
return i;
}
int main()
{
int arr[]={4,8,2,1,10,12};
int N = sizeof(arr) / sizeof(arr[0]);
int K;
printf("Enter the value of K:");
scanf("%d",&K);
printf("Kth Smallest element is ");
printf("%d",kthsmallest(arr,0,N-1,K));
return 0;
}
Result:

Thus a C-program to find the Kth smallest number using randomized algorithm was written and executed

successfully.