ANNAI VEILANKANNI’S COLLEGE OF ENGINEERING

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS3401- ALGORITHMS LABORATORY

Name of the :

Register :

Semester :
 ANNAI VEILANKANNI’S COLLEGE OF
ENGINEERING
Approved by AICTE-New Delhi & Affiliated to Anna University, Chennai
NO: 33, Gandhi Road, Nedungundrum, Chennai-127Tel: 044-22790022, 22790033,
2279004

BONAFIDE CERTIFICATE

Name :
Register no :

Certified that this is a bonafide record of work done by

the candidate in the……………………………..semester of

B.E/[Link]

………………………….. In the laboratory

during the year…………………………………

Staff In-charge Head of the Department

This record is submitted for Anna University practical examination held

on………….
Internal Examiner External Examiner
 INDEX

PA
S.N DATE TIT MARK SIGN
G
O LE S
E
N
O

.
 PA
S.N DATE TIT MARK SIGN
G
O LE S
E
N
O

.
 PA
S.N DATE TIT MARK SIGN
G
O LE S
E
N
O

.
 Ex. No. 1 Implementation of Linear Search

Date.

Aim :

Algorithm :

1. Start

2. Read number of array elements n

3. Read array elements Ai, i = 0,1,2,…n–1

4. Read search value

5. Assign 0 to found

6. Check each array element against

search If Ai = search then

found = 1

Print "Element

found" Print position

Stop

7. If found = 0 then

print "Element not found"

8. Stop
 Program :

/* Linear search on a sorted

array */ #include <stdio.h>

#include <conio.h>

main()

int a[50],i, n, val,

found; clrscr();

printf("Enter number of elements : "); scanf("%d",

&n); printf("Enter Array Elements : \n");

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

+) scanf("%d",

&a[i]);

printf("Enter element to locate :

"); scanf("%d", &val);

found = 0;

for(i=0; i<n;

i++)

if (a[i] == val)

printf("Element found at position

%d", i); found = 1;

break;

if (found == 0)

printf("\n Element not found");

getch();

}
 Output :

Enter number of elements

: 7 Enter Array Elements :

23 6 12 5 0 32 10

Enter element to locate :

5 Element found at

position 3

Result :
 Ex. No. 2 Implementation of binary search Using Divide

and Conquer Date.

Aim :

Algorithm :

1. Start.

2. Read the array elements arr[].

3. Read search value x.

4. To search a array using Binary search

i) Compare x with the middle element.

ii) If x matches with the middle element, we return the mid index.

iii) Else If x is greater than the mid element, then x can only lie in
right half subarray after the mid element. So we traverse the
search in the right half.

iv) Else (x is smaller) we can search in the left half.

5. If the value is present in the array show "Element is present at index

(index of the element)".

6. If the value is not present in the element show "Element is not

present in the array".

7. stop.

Program :

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x)

if (r >= l)

int mid = l + (r - l)/2;

// If the element is present at the middle itself

if (arr[mid] == x) return mid;

// If element is smaller than mid, then it can only be present

// in left subarray

if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right

subarray return binarySearch(arr, mid+1, r, x);

// We reach here when element is not present in

array return -1;

int main(void)

int arr[] = {2, 3, 4, 10, 40};

int n = sizeof(arr)/

sizeof(arr[0]); int x = 10;

int result = binarySearch(arr, 0, n-

1, x); IF(result == -1)

printf("Element is not present in

array") else

printf("Element is present at index %d",

result); return 0;

Output :

Element is present at index 3

Result:
 Ex. No. 3 Implementation of Naive algorithm for pattern

Matching Date.

Aim :

Algorithm :

1. Start.

2. Read the pattern and text as pat[], txt[].

3. To match the pattern using a naive algorithm.

i) It compares the first character of the pattern with searchable text.

ii) If match is found, show "pattern found at index (index of the

element)". iii)If match not found, pointer of text is incremented and

pointer of pattern is reset's.

iv) This process is repeated until the end of the text.

4. It does not require any pre-processing. It directly starts comparing

both strings character by character.

5. pseudocode:

Algorithm-NAVE_STRING_MATCHING (T, P)

for i←0 to n-m do

if P[1......m] == T[i+1 i+m] then

print "Match

Found" end

6. stop.
 Program :

#include <stdio.h>

#include <string.h>

void search(char* pat, char* txt)

int M =

strlen(pat); int N

= strlen(txt);

/* A loop to slide pat[] one by

one */ for (int i = 0; i <= N - M;

i++) {

int j;

/* For current index i, check for pattern

match */ for (j = 0; j < M; j++)

if (txt[i + j] !=

pat[j]) break;

if (j

== M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]

printf("Pattern found at index %d \n", i);

// Driver's

code int

main()

char txt[] = "AABAACAADAABAAABAA";

char pat[] = "AABA";

 // Function

call

search(pat,

txt);
 return 0;

Output :

Pattern found at index

0 Pattern found at

index 9 Pattern found

at index 13

Result :
 Ex. No.4 Implementation of Sorting - Insertion Sort

Date.

Aim :

Algorithm :

1. Start

2. Read number of array elements n

3. Read array elements Ai

4. Sort the elements using insertion sort

In pass p, move the element in position p left until its

correct place is found among the first p + 1 elements.

Element at position p is saved in temp, and all larger

elements (prior to position p) are moved one spot to

the right. Then temp is placed in the correct spot.

5. Stop

Program :

#include

<stdio.h> void

main()

int i, j, k, n, temp, a[20], p=0;

printf("Enter total elements: ");

scanf("%d",&n);

printf("Enter array elements:");

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

scanf("%d",

&a[i]); for(i=1;

i<n; i++)
{

temp =

a[i]; j = i -

1;

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

a[j+1]

=a[j]; j = j

- 1;

a[j+1] =

temp; p++;

printf("\n After Pass %d: ",

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

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

printf("\n Sorted List :

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

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

Output :

Enter total elements: 6

Enter array elements: 34 8 64 51 32 21

After Pass 1: 8 34 64 51 32 21

After Pass 2: 8 34 64 51 32 21

After Pass 3: 8 34 51 64 32 21

After Pass 4: 8 32 34 51 64 21

After Pass 5: 8 21 32 34 51 64

Sorted List : 8 21 32 34 51 64

Result :
 Ex. No.5 Implementation of Sorting - Heap sort

Date.

Aim :

Algorithm :

1. Start.

2. First convert the array into heap data structure using heapify.

3. 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 the
size of the heap is greater than 1.

4. Repeat the following steps until the heap contains only one element:

i) Swap the root element of the heap (which is the largest element)
with the last element of the heap.

ii) Remove the last element of the heap (which is now in the correct

position). iii)Heapify the remaining elements of the heap.

5. The sorted array is obtained by reversing the order of the elements in

the input array.

6. Follow the steps to solve the problem in heap sort:

i) Build a max heap from the input data.

ii) At this point, the maximum element is stored at the root of the heap.
Replace it

with the last item of the heap followed by reducing the size of the

heap by 1. Finally, heapify the root of the tree.

iii) Repeat step 2 while the size of the heap is greater than 1.

7. Stop.
 Program :

#include <stdio.h>

// Function to swap the position of two

elements void swap(int* a, int* b)

int temp = *a;

*a = *b;

*b = temp;

// To heapify a subtree rooted with node i

// which is an index in arr[].

// n is size of heap

void heapify(int arr[], int N, int i)

// Find largest among root, left child and right child

// Initialize largest as

root int largest = i;

// left = 2*i + 1

int left = 2 * i

+ 1;

// right = 2*i + 2

int right = 2 * i

+ 2;

// If left child is larger than root

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

 largest = left;

// If right child is larger than largest

// so far

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

largest = right;

// Swap and continue heapifying if root is not largest

// If largest is not

root if (largest != i)

swap(&arr[i], &arr[largest]);

// Recursively heapify the affected

// sub-tree

heapify(arr, N, largest);

// Main function to do heap

sort void heapSort(int arr[],

int N)

// Build max heap

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

heapify(arr, N, i);

// Heap sort
 for (int i = N - 1; i >= 0; i--) {

swap(&arr[0], &arr[i]);

// Heapify root element to get highest element at

// root again

heapify(arr, i,

0);

// A utility function to print array of

size n void printArray(int arr[], int N)

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

printf("%d ",

arr[i]); printf("\n");

// Driver's

code int

main()

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

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

// Function call

heapSort(arr, N);

printf("Sorted array is\

n"); printArray(arr, N);

}
 Output :

Sorted array

is

5,6,7,11,12,1

Result :

.
 [Link].6 Implementation of Graph Traversal Using Breadth First Search

Date .

Aim :

Algorithm :

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting

state) Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

Step 5: Enqueue all the neighbors of N that are in the ready state (whose
STATUS = 1) and set

their STATUS =

2 (waiting

state) [END OF

LOOP] Step 6:

EXIT

Program :

#include

<stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#define MAX_VERTICES 50

// This structure represents a directed graph using

// adjacency list representation

typedef struct Graph_t {

int V; // No. of vertices

bool adj[MAX_VERTICES][MAX_VERTICES];
} Graph;

// Constructor

Graph* Graph_create(int V)

Graph* g =

malloc(sizeof(Graph)); g->V =

V;

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

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

g->adj[i][j] = false;

return g;

// Destructor

void Graph_destroy(Graph* g) { free(g); }

// function to add an edge to graph

void Graph_addEdge(Graph* g, int v, int w)

g->adj[v][w] = true; // Add w to v’s list.

// prints BFS traversal from a given source

s void Graph_BFS(Graph* g, int s)

// Mark all the vertices as not visited

bool

visited[MAX_VERTICES]; for

(int i = 0; i < g->V; i++) {

visited[i] = false;

// Create a queue for BFS

int

queue[MAX_VERTICES];

int front = 0, rear = 0;

// Mark the current node as visited and

enqueue it visited[s] = true;

queue[rear++] = s;

while (front != rear) {

// Dequeue a vertex from queue and

print it s = queue[front++];

printf("%d ", s);

// Get all adjacent vertices of the dequeued

// vertex s. If a adjacent has not been visited,

// then mark it visited and enqueue

it for (int adjacent = 0; adjacent <

g->V;

adjacent++) {

if (g->adj[s][adjacent] && !visited[adjacent]) {

visited[adjacent] = true;

queue[rear++] =

adjacent;

}
 }

}
// Driver program to test methods of graph

struct int main()

// Create a graph given in the above

diagram Graph* g = Graph_create(4);

Graph_addEdge(g, 0, 1);

Graph_addEdge(g, 0, 2);

Graph_addEdge(g, 1, 2);

Graph_addEdge(g, 2, 0);

Graph_addEdge(g, 2, 3);

Graph_addEdge(g, 3, 3);

printf("Following is Breadth First

Traversal " "(starting from vertex 2) \

n"); Graph_BFS(g, 2);

Graph_destroy(g);

return 0;

Output :

Following is Breadth First Traversal (starting from

vertex 2) 2 0 3 1

Result :
 Ex. No.7 Implementation of Sorting- Merge Sort Uses Divide

and Conquer Date.

Aim :

Algorithm :

1. Start

2. Read number of array elements n

3. Read array elements Ai

4. Divide the array into subarrays with a set of elements

5. Recursively sort the sub-arrays

6. Merge the sorted subarrays onto a single sorted array.

7. Stop

Program :

#include <stdio.h>

#include <conio.h>

void merge(int

[],int ,int ,int ); void

part(int [],int ,int );

int

size;

main()

int i, arr[30];

printf("Enter total no. of elements : "); scanf("%d",

&size); printf("Enter array elements : ");

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

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

part(arr, 0, size-1);
printf("\n Merge sorted

list : "); for(i=0; i<size; i+

+)

printf("%d

",arr[i]);

getch();

void part(int arr[], int min, int max)

int i, mid;

if(min <

max)

mid = (min + max) / 2;

part(arr, min, mid);

part(arr, mid+1, max);

merge(arr, min, mid,

max);

if (max-min == (size/2)-1)

printf("\n Half sorted

list : "); for(i=min;

i<=max; i++) printf("%d

", arr[i]);

void merge(int arr[],int min,int mid,int max)

int

tmp[30];

int i, j, k,
m; j =

min;

m = mid + 1;

for(i=min; j<=mid && m<=max; i++)

{
if(arr[j] <= arr[m])

else

tmp[i] =

arr[j]; j++;

tmp[i] =

arr[m]; m+

+;

if(j > mid)

for(k=m; k<=max; k++)

else

tmp[i] =

arr[k]; i++;

for(k=j; k<=mid; k++)

tmp[i] =

arr[k]; i++;

for(k=min; k<=max;

k++) arr[k] = tmp[k];

}
 Output :

Enter total no. of elements : 8

Enter array elements : 24 13 26 1 2 27 38 15

Half sorted list : 1 13 24 26

Half sorted list : 2 15 27 38

Merge sorted list : 1 2 13 15 24 26 27 38

Result :
 Ex. No. 8 Implementation of Prim’s Algorithm

Date.

Aim :

Algorithm :

Step 1: Select a starting vertex

Step 2: Repeat Steps 3 and 4 until there are fringe vertices

Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that
has minimum weight

Step 4: Add the selected edge and the vertex to the minimum spanning

tree T [END OF LOOP]

Step 5: EXIT

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()

printf("\nEnter the number of nodes:");

scanf("%d",&n);

printf("\nEnter 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();

}
 Output :

Result :
 Ex. No. 9 Implementation of Dijkstra’s

Algorithm Date.

Aim :

Algorithm :

Step 1. Start

Step 2. Obtain no. of vertices and adjacency matrix for the given graph

Step 3. Create cost matrix from adjacency matrix. C[i][j] is the cost of

going from vertex i to vertex j. If there is no edge between vertices i and j

then C[i][j] is infinity

Step 4. Initialize visited[] to zero

Step 5. Read source vertex and mark it as visited

Step 6. Create the distance matrix, by storing the cost of vertices from
vertex no. 0 to n-1

from the source

vertex

distance[i]=cost[0]

[i];

Choose a vertex w, such that distance[w] is minimum and visited[w] is 0.

Markvisited[w] as 1.

Step 7. Recalculate the shortest distance of remaining vertices from the

source. Step 8. Only, the vertices not marked as 1 in array visited[ ] should

be considered for recalculation of distance. i.e. for each vertex v

if(visited[v]==0)

distance[v]=min(distanc

e[v] distance[w]

+cost[w][v]) Step 9.

Stop
 Program :

/* Dijkstra’s Shortest

Path */ #include

<stdio.h>

#include <conio.h>

#define INFINITY

9999

#define MAX 10

void dijkstra(int G[MAX][MAX], int n, int startnode);main()

int G[MAX][MAX], i, j, n, u; printf("Enter no. of vertices: ");scanf("%d",

&n); printf("Enter the adjacency matrix:\n"); for(i=0; i<n; i++)for(j=0;

j<n; j++) scanf("%d", &G[i][j]);printf("Enter the starting node:

");scanf("%d", &u); dijkstra(G, n, u);

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

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

cost[i][j] = G[i][j];

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])

count++;

distance[i] = mindistance + cost[nextnode]

[i]; pred[i] = nextnode;

for(i=0; i<n;

i++) if(i !=

startnode)

printf("\nDistance to node%d = %d", i,

distance[i]); printf("\nPath = %d", i);j = i;

do

j = pred[j]; printf("<-%d", j);

} while(j != startnode);

}
 Output :

Enter no. of vertices: 5

Enter the adjacency

matrix:

0 10 0 30 100

10 0 50 0 0

0 50 0 20 10

30 0 20 0 60

100 0 0 60 0

Enter the starting node: 0 Distance to

node1 = 10 Path = 1<-0

Distance to node2 = 50 Path

= 2<-3<-0 Distance to

node3 = 30 Path = 3<-0

Distance to node4

= 60 Path = 4<-2<-3<-0

Result :
 [Link].10 Implementation of Graph Traversal Using Depth First

Search Date.

Aim :

Algorithm:

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Push the starting node A on the stack and set its STATUS = 2

(waiting state) Step 3: Repeat Steps 4 and 5 until STACK is empty

Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)

Step 5: Push on the stack all the neighbors of N that are in the ready state
(whose STATUS = 1) and set their STATUS = 2 (waiting state)

[END OF

LOOP] Step 6:

EXIT

Program :

// C code to implement above approach

#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(

"Mem

} ory

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++) {

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] = 1;

G->Adj[1][3] = G->Adj[3][1] = 1;

G->Adj[1][4] = G->Adj[4][1] = 1;

G->Adj[1][5] = G->Adj[5][1] = 1;
 G->Adj[1][6] = G->Adj[6][1] = 1;

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

);

Output :

0134562

Result :
 [Link]. 11 Implementation of Sorting - Quick Sort

Date.

Aim :

Algorithm :

quickSort(array, leftmostIndex,

rightmostIndex) if (leftmostIndex <

rightmostIndex)

pivotIndex <- partition(array,leftmostIndex,

rightmostIndex) quickSort(array, leftmostIndex,

pivotIndex - 1) quickSort(array, pivotIndex,

rightmostIndex)

partition(array, leftmostIndex,

rightmostIndex) set rightmostIndex as

pivotIndex

storeIndex <- leftmostIndex - 1

for i <- leftmostIndex + 1 to

rightmostIndex if element[i] <

pivotElement

swap element[i] and

element[storeIndex] storeIndex++

swap pivotElement and

element[storeIndex+1] return storeIndex + 1

Program :

#include <stdio.h>

// Function to swap

numbers void swap(int*

a, int* b)

int temp = *a;

 *a = *b;

*b = temp;

//Partition Function

int partition(int arr[], int low, int high)

{
i

int j; t
i

n i

i (

v l

o o

t w

= -

a 1

r )

r ;

h for (j =

i l

g o

h w

] ;

;
j f

< (

= a

h r

i [

g j

h ]

- <

; p

j v

+ o

+ t

) )

{ {

i++;

i swap(&arr[i], &arr[j]);

swap(&arr[i + 1],

&arr[high]); return (i +

1);

// Quick Sort function

void quicksort(int Arr[], int low, int high)

{

if (low < high) {

// pi = Partition index

int pi = partition(Arr, low, high);

quicksort(Arr, low, pi -

1); quicksort(Arr, pi +

1, high);

}
// Main

Function int

main()

int size = 5;

int array[size] = { 11,9,6,16,7 };

quicksort(array, 0, size - 1);

int i;

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

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

Output:

6 7 9 11 16

Result :
 Ex .No: 12 Implementation of N Queens Problem

Date.

Aim:

Algorithm:

step 1 : Place the queens column wise, start from the left most

column step 2 : If all queens are placed:

return true and print the solution

matrix. step3 : Else Try all the rows in the

current column.

step 4 : Check if queen can be placed here safely if yes mark the current
cell in solution matrix as 1 and try to solve the rest of the problem
recursively.

step 5 : If placing the queen in the above step leads to the solution return true.

step 6 : If placing the queen in the above step does not lead to the
solution , BACKTRACK, mark the current cell in the solution matrix as 0 and
return false.

step 7 : If all the rows are tried and nothing worked, return false and print
NO SOLUTION.

Program :

/* C program to solve N Queen Problem

using backtracking */

#define N 4

#include

<stdbool.h>

#include <stdio.h>

/* A utility function to print

solution */ 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])

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()
{

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;

}
Output:

..Q.
Q...
...Q
.Q..

Result :
 [Link].13 Implementation of Floyd Algorithm

Date.

Aim:

Algorithm:

step 1 : Initialize two-pointers and start traversing the

linked list. step 2 : Move the slow pointer by one position.

step 3 : Move the fast pointer by two positions.

step 4 : If both pointers meet at some point then a loop exists and if the

fast pointer meets the end position then no loop exists.

Program :

include<stdio.h>

void floyd(int a[4][4], int n)

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

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

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

if(a[i][j]>a[i][k]+a[k][j])

a[i][j]=a[i][k]+a[k][j];

}
 printf("All Pairs Shortest Path is :\

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

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

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

}
int main()

{
printf("\n");
}
}

int cost[4][4] = {{0, 3, 999, 4}, {8, 0, 2, 999}, {5, 999, 0, 1}, {2, 999, 999,
0}};

int n = 4;

floyd(cost,n);

Output

All Pairs Shortest Path is :

0354

5023

3601

2570

Result :
 [Link]. 14 Implementation of Warshall Algorithm

Date.

Aim:

Algorithm :

step 1 : Initialize the solution matrix same as the input graph matrix as a first step.

step 2 : Then update the solution matrix by considering all vertices as an

intermediate vertex.

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

step 4 : When we pick vertex number k as an intermediate vertex, we already have

considered

vertices {0, 1, 2, .. k-1} as intermediate vertices.

step 5 : For every pair (i, j) of the source and destination vertices
respectively, there are two

possible cases.

step 6 : k is not an intermediate vertex in the shortest path from i to j. We

keep the value

of dist[i][j] as it is.

step 7 : k is an intermediate vertex in shortest path from i to j. We update

the value of 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:5

Enter the end vertices of edge

1:1 2 Enter the end vertices of

edge 2:1 3 Enter the end

vertices of edge 3:2 3 Enter the

end vertices of edge 4:3 4 Enter

the end vertices of edge 5:4 1

Matrix of input data:

0 1 1 0

0 0 1 0

0 0 0 1

1 0 0 0

Transitive closure:

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

Result :
[Link] : 15 Implementation of Maximum and Minimum

Date.

Aim :

Algorithm :

step 1 : Divide array by calculating mid index i.e. mid = l + (r — l)/2

step 2 : Recursively find the maximum and minimum of left part by calling
the same function i.e. leftMinMax[2] = minMax(X, l, mid)

step 3 : Recursively find the maximum and minimum for right part by
calling the same function i.e. rightMinMax[2] = minMax(X, mid + 1, r)

step 4 : Finally, get the overall maximum and minimum by comparing the
min and max of both halves.

Program :

/* structure is used to return two values from

minMax() */ #include<stdio.h>

struct pair

int

min;

int

max;

};

struct pair getMinMax(int arr[], int n)

struct pair

minmax; int i;

/*If there is only one element then return it as min and

max both*/ if (n == 1)
 {

[Link] =

arr[0]; [Link]

= arr[0]; return

minmax;

/* If there are more than one elements, then initialize

min and max*/

if (arr[0] > arr[1])

{
r

[
}
0
else
]
{
;

} m

m i

i n

n m

m a

a x

x .

. m

m i

a n

a r
r 1

[ ]

1 ;

; m

m a

i x

n .

m m

a i

x n

m =

x a

= r

a 0

r ]

r ;

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

if (arr[i] >

[Link])

[Link] =
 arr[i];

else if (arr[i] < [Link])

[Link] = arr[i];

return minmax;

}
/* Driver program to test above

function */ int main()

int arr[] = {1000, 11, 445, 1, 330, 3000};

int arr_size = 6;

struct pair minmax = getMinMax (arr,

arr_size); printf("nMinimum element is %d",

[Link]); printf("nMaximum element is

%d", [Link]); getchar();

Output :

Minimum element is 1

Maximum element is

3000

Result :
 [Link].16 Implementation of Traveling salesman

problem Date.

Aim :

Algorithm :

Step 1 : Start at any arbitrary city.

step 2 : Repeat until all the nodes are visited : go to the nearest city(The
unvisited one) each time.

step 3 : Return to the starting city.

Program :

#include<stdio.h>

int ary[10][10],completed[10],n,cost=0;

void takeInput()

int i,j;

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

scanf("%d",&n);

printf("\nEnter the Cost Matrix\n");

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

printf("\nEnter Elements of Row: %d\n",i+1);

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

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

completed[i]=0;

printf("\n\nThe cost list is:");

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

printf("\n");

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

printf("\t%d",ary[i]

[j]);

void mincost(int city)

int i,ncity;

completed[city]=1;

printf("%d---

>",city+1);

ncity=least(city);

if(ncity==999)

ncity=0;

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

cost+=ary[city]
[ncity];
return;

mincost(ncity);

int least(int c)

int i,nc=999;

int min=999,kmin;

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

if((ary[c][i]!=0)&&(completed[i]==0))

if(ary[c][i]+ary[i][c] < min)

min=ary[i][0]+ary[c]

[i]; kmin=ary[c][i];

nc=i;

if(min!

=999)

cost+=kmi

n; return

nc;

int main()

takeInput(); printf("\n\

nThe Path is:\n");

mincost(0); //passing 0 because starting

vertex printf("\n\nMinimum cost is %d\n

",cost);

return 0;

Output :

Enter the number of

villages: 4 Enter the Cost

Matrix

Enter Elements of

Row: 1 0 4 1 3

Enter Elements of

Row: 2 4 0 2 1

Enter Elements of

Row: 3 1 2 0 5

Enter Elements of

Row: 4 3 1 5 0

The cost list is:

0413

4021

1205

3150

The Path is:

1—>3—>2—>4—>1

Minimum cost is 7

Result :
 [Link].17 Implementation of Randomized Algorithms

Date.

Aim :

Algorithm :

step 1 : Apply quick sort algorithm on the input array

step 2 : During quick sort, select a pivot element randomly from the range
of the array from low to high and move it to its correct position.

step 3 : If index of pivot is equal to k then return the value

step 4 : Else if the index of pivot is greater than k, then scan for the left
subarray recursively, else scan for the right subarray recursively.

step 5 : Repeat this process until the element at index is not found

Program :

// C program to find Kth smallest

element #include <stdio.h>

#include <stdlib.h>

// Compare function for qsort

int cmpfunc(const void* a, const void* b)

return (*(int*)a - *(int*)b);

// Function to return K'th smallest

// element in a given array

int kthSmallest(int arr[], int N, int K)

{
 // Sort the given array

qsort(arr, N, sizeof(int), cmpfunc);

// Return k'th element in the sorted array

return arr[K - 1];

// Driver's

code int

main()

int arr[] = { 12, 3, 5, 7, 19 };

int N = sizeof(arr) / sizeof(arr[0]), K = 2;

// Function call
eleme

nt is

%d",

} kthSm

allest(

Output: arr, N,

printf("K'th K));

smalle return 0;

st

K'th smallest element is 5

Result :