CHERAN COLLEGE OF TECHNOLOGY

(Approved by AICTE NewDelhi and affiliated to Anna University ,Chennai)

Cheran Nagar, Thittuparai,Kangeyam,TiruppurDistrict–638701

04257 243311 cherantech@[Link]

DEPARTMENT OF COMPUTER
SCIENCE AND ENGINEERING

CS3401 ALGORITHM
LABORATORY RECORD

ACADAMIC YEAR 2025-2026

Name_______________________________________________________________

Register No________________________ Roll No_____________________

Branch_______________________________________________________

Semester_________________________________________________________
Subject______________________________________________________________
Subject code__________________________________________________________
 CHERAN COLLEGE OF TECHNOLOGY
(Approved by AICTE NewDelhi and affiliated to Anna University ,Chennai)

Cheran Nagar, Thittuparai, Kangeyam, TiruppurDistrict–638701

BONAFIDE CERTIFICATE
LABORATORY RECORD
ACADEMIC YEAR 2025-2026

Certified to be the bonafide record work done by______________________

Register No: _____________in __________________________________(Sub
code& Name) of Cheran College of Technology, Kangeyam during the academic
year 2025-2026

Signature of Signature of
Faculty in-charge Head of the Department

Submitted for Anna University, Chennai Practical Examination held on

________________/_________ at__________________________________

Internal Examiner External Examiner

 INDEX

Ex. Staff
Date Name of the Experiment Marks Page No
No Signature
2
 lOMoARcPSD|65785340

[Link]: 1 LINEAR SEARCH

DATE:

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

ALGORITHM:

Step 1: Set i to 0 // i is the index of an array which starts from

0 Step 2: if i > n then go to step 7 // n is the number of elements in array
Step 3: if Arr[i] = a then go to step 6
Step 4: Set i to i + 1
Step 5: Goto step 2
Step 6: Print element a found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

PROGRAM:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int main()
{
int array[50],i,target,num;
printf("How many elements do you want in the array");
scanf("%d",&num);
printf("Enter array elements:");
for(i=0;i<num;++i)
scanf("%d",&array[i]);
printf("Enter element to
search:"); scanf("%d",&target);
for(i=0;i<num;++i)
if(array[i]==target)
break;
if(i<num)
printf("Target element found at location %d",i);
else
printf("Target element not found in an array");
return 0;
}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:
Thus the C program for implementation of Linear search algorithm was done and executed
successfully.
 lOMoARcPSD|65785340

[Link] BINARY SEARCH

DATE:

AIM:
To implement recursive Binary Search. Determine the time required to search an
element. Repeat the experiment for different values of n, the number of elements in the list to
be searched and plot a graph of the time taken versus n.

ALGORITHM:

Step 1: binarySearch (arr, x, low, high)

If low> high
Return false
Step 2:Find the middle element of array. using middle = initial_value + end_value / 2 ;
Step 3: If middle = element, return ‘element found’ and index.
Step 4: if middle > element, call the function with end_value = middle - 1 .
Step 5: if middle < element, call the function with start_value = middle + 1 .
Step 6: exit.

PROGRAM:

#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100];
printf("Enter number of elements");
scanf("%d",&n);
printf("Enter %d integers", n);
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Enter value to find");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high) {
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key) {
printf("%d found at location %d", key, mid+1);
break;
}
 lOMoARcPSD|65785340

else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("Not found! %d isn't present in the list", key);
return 0;
}

OUTPUT:

RESULT:
Thus the C program for implementation of Binary search algorithm was done and executed
successfully.
 lOMoARcPSD|65785340

[Link]: 3 STRING MATCHING ALGORITHM

DATE:

AIM:

To write a function search (char pat [ ], char txt [ ]) that prints all occurrences of pat [ ]
in txt [ ] for given a text txt [0...n-1] and a pattern pat [0...m-1],. You may assume that n >
m.

ALGORITHM:

Step 1: NAVE_STRING_MATCHING (T, P)

Step 2: for i←0 to n-m do
Step 3: Check if P[1......m] == T[i+1.....i+m] then
print "Match Found"
Step 3: End

PROGRAM:

#include<stdio.h>
#include<conio.h>
#include<string.h>
int match(char st[100], char pat[100]);
int main(int argc, char **argv) {
char st[100], pat[100];
int status;
printf("*** Naive String Matching Algorithm ***\n");
printf("Enter the String.\n");
gets(st);
printf("Enter the pattern to match.\n");
gets(pat);
status = match(st, pat);
if (status == -1)
printf("\nNo match found");
ese
printf("Match has been found on %d position.", status);
return 0;
}
int match(char st[100], char pat[100]) {
int n, m, i, j, count = 0, temp = 0;
n = strlen(st);
m = strlen(pat);
for (i = 0; i <= n - m; i++) {
 lOMoARcPSD|65785340

temp++;
for (j = 0; j < m; j++) {
if (st[i + j] == pat[j])
count++;
}
if (count == m)
return temp;
count = 0;
}
return -1;
}

OUTPUT:
Enter the String. [Link]@[Link]
Enter the pattern to match. Dharm

Match has been found on 6 position.

RESULT:
Thus, the C program for implementation of String pattern matching algorithm was
done and executed successfully.
 lOMoARcPSD|65785340

[Link]-A INSERTION SORT

DATE:

AIM:
To Sort a given set of elements using the Insertion sort methods and determine the
time required to sort the elements. Repeat the experiment for different values of n, the
number of elements in the list to be sorted and plot a graph of the time taken versus n.

ALGORITHM:

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to
the next element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.

PROGRAM:

#include <stdio.h>

void insert(int a[], int n) /* function to sort an aay with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;

while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one positio
n ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */

{
int i;
 lOMoARcPSD|65785340

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

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

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);

return 0;
}

OUTPUT:

RESULT:
Thus the program for Insertion sort has been implemented and executed successfully
 lOMoARcPSD|65785340

[Link]-B HEAP SORT

DATE:

AIM:
To Sort a given set of elements using the Heap sort methods and determine the time
required to sort the elements. Repeat the experiment for different values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n.

ALGORITHM:

Step 1: HeapSort(arr)
Step 2: BuildMaxHeap(arr)
Step 3: for i = length(arr) to 2
Step 4: swap arr[1] with
arr[i]
Step 5: heap_size[arr] = heap_size[arr] ? 1
Step 6 : MaxHeapify(arr,1)
End
BuildMaxHeap(arr)

1. BuildMaxHeap(arr)
2. heap_size(arr) = length(arr)
3. for i = length(arr)/2 to 1
4. MaxHeapify(arr,i)
5. End

MaxHeapify(arr,i)

1. MaxHeapify(arr,i)
2. L = left(i)
3. R = right(i)
4. if L? heap_size[arr] and arr[L] > arr[i]
5. largest = L
6. else
7. largest = i
8. if R? heap_size[arr] and arr[R] > arr[largest]
9. largest = R
10. if largest != i
11. swap arr[i] with arr[largest]
12. MaxHeapify(arr,largest)
13. End
 lOMoARcPSD|65785340

PROGRAM:

#include <stdio.h>
void heapify(int a[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
if (left < n && a[left] >
a[largest])
largest = left;
if (right < n && a[right] > a[largest])
largest = right;

if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}

/*Function to implement the heap sort*/

void heapSort(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0;
i--) heapify(a, n, i);
// One by one extract an element from
heap for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}

/* function to print the array elements */

void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d", arr[i]);
printf(" ");
}

}
 lOMoARcPSD|65785340

int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
heapSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}

OUTPUT:

RESULT:
Thus, the program for Heap sort method has been implemented and executed
successfully.
 lOMoARcPSD|65785340

[Link] BREADTH FIRST SEARCH

DATE :
AIM:

To develop a program to implement graph traversal using breadth First Search

ALGORITHM:

Step 1: Declare a queue and insert the starting vertex.

Step 2: Initialize a visited array and mark the starting vertex as visited.
Step 3: Remove the first vertex of the queue.
Step 4: Mark that vertex as visited.
Step 5: Insert all the unvisited neighbours’ of the vertex into the queue.

PROGRAM

#include <stdio.h>
int n, i, j, visited[10], queue[10], front = -1, rear = -1;
int adj[10][10];
void bfs(int v)
{
for (i = 1; i <= n; i++)
if (adj[v][i] && !visited[i])
queue[++rear] = i;
if (front <= rear)
{
visited[queue[front]] = 1;
bfs(queue[front++]);
}
}

void main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
queue[i] = 0;
visited[i] = 0;
}
printf("Enter graph data in matrix form: \n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
 lOMoARcPSD|65785340

scanf("%d", &adj[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &v);
bfs(v);
printf("The node which are reachable are: \n");
for (i = 1; i <= n; i++)
if (visited[i])
printf("%d\t", i);
else
printf("BFS is not possible. Not all nodes are reachable");
return 0;
}

OUTPUT:

Enter the number of vertices: 4

Enter graph data in matrix
form:
0110
1001
1001
0110
Enter the starting vertex: 2
The node which are reachable are:
1 2 3 4

RESULT:
Thus, the program for Breadth first search algorithm has been implemented and
executed successfully.
 lOMoARcPSD|65785340

[Link] DEPTH FIRST SEARCH

DATE:

AIM:

To develop a program to implement graph traversal using Depth First Search

ALGORITHM:

Step 1: Create a stack with the total number of vertices in the graph as the size.
Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that vertex and
add it to the stack.
Step 3 - Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of
the stack.
Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the
top of the stack.
Step 5 - If there are no new vertices to visit, go back and pop one from the stack using
backtracking.
Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.
Step 7 - When the stack is entirely unoccupied, create the final spanning tree by deleting the
graph's unused edges.

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
/* ADJACENCY MATRIX */
int source,V,E,time,visited[20],G[20][20];
void DFS(int i)
{
int j;
visited[i]=1;
printf(" %d->",i+1);
for(j=0;j<V;j++)
{
if(G[i][j]==1&&visited[j]==0)
DFS(j);
}
}
int main()
{
int i,j,v1,v2; printf("\t\t\tGraphs\
n"); printf("Enter the no of
edges:"); scanf("%d",&E);
 lOMoARcPSD|65785340

printf("Enter the no of
vertices:"); scanf("%d",&V);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
G[i][j]=0;
}
/* creating edges :P */
for(i=0;i<E;i++)
{
printf("Enter the edges (format: V1 V2) : ");
scanf("%d%d",&v1,&v2);
G[v1-1][v2-1]=1;

for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
printf(" %d ",G[i]
[j]);
printf("\n");
}
printf("Enter the source: ");
scanf("%d",&source);
DFS(source-1);
return 0;
}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:

Thus, the program for Depth first search algorithm has been implemented and
executed successfully.
 lOMoARcPSD|65785340

[Link] DIJKSTRA’S ALGORITHM

DATE:

AIM:

To develop a program to find the shortest paths from a given vertex in a weighted
connected graph to other vertices using Dijkstra’s algorithm.

ALGORITHM:
Step 1: Create a set S that keeps track of vertices included in shortest path tree, i.e.,
whose minimum distance from source is calculated and finalized. Initially, this set is
empty.
Step 2: Assign a distance value to all vertices in the input graph. Initialize all distance
values as INFINITE and Assign distance value as 0 for the source vertex so that it is
picked first.
Step 3: While S doesn’t include all vertices
 Pick a Vertex u which is not there in S and has minimum distance value.
 Include u to S.
 Update distance value of all adjacent vertices of u.
Step 4: To update the distance values, iterate through all adjacent vertices. For every adjacent
vertex v, ifsum of distance value of u (from source) and weight of edge u-v, is less than the
distance value of v, then update the distance value of v.

PROGRAM:
#include<stdio.h>
#define infinity
999
void dij(int n, int v,int cost[20][20], int dist[])
{
int i,u,count,w,flag[20],min;
for(i=1;i<=n;i++)
flag[i]=0, dist[i]=cost[v][i];
count=2;
while(count<=n){
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !
flag[w])
{
flag[u]=1;count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
 lOMoARcPSD|65785340

}
min=dist[w];
u=w;
}
}
int main(){
int n,v,i,j,cost[20][20],dist[20];
printf("enter the number of
nodes:"); scanf("%d",&n);
printf("\n enter the cost matrix:\
n"); for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&cost[i][j]);if(cost[i][j] ==
0) cost[i][j]=infinity;
}
printf("\n enter the source
matrix:"); scanf("%d",&v);
dij(n,v,cost,dist);
printf("\n shortest path : \
n"); for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d\n",v,i,dist[i]);
}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:

Thus, the program for finding shortest path using Dijkstra’s algorithm has been
implemented and executed successfully.
 lOMoARcPSD|65785340

[Link] MINIMUM COST SPANNING TREE

DATE:
AIM:

To develop a program to find the minimum cost spanning tree of a given undirected graph
using Prim’s algorithm.

ALGORITHM:
Step 1: Create a set Sthat keeps track of vertices already included in MST.
Step 2: Assign a key value to all vertices in the input graph. Initialize all key values as
[Link] key value as 0 for the first vertex so that it is picked first.
Step 3: While S doesn’t include all vertices.
 Pick a vertex u which is not there in Sand has minimum key value.
 Include u to S.
 Update key value of all adjacent vertices of u.

To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if
weight of edge u-v is less than the previous key value of v, update the key value as weight of
u-v

The idea of using key values is to pick the minimum weight edge from cut. The key values
are usedonly for vertices which are not yet included in MST, the key value for these vertices
indicate the minimum weight edges connecting them to the set of vertices included in MST.

PROGRAM:

#include<stdio.h>
inta,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];void main()
{
printf("\n Enter the number ofnodes:"); 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;
 lOMoARcPSD|65785340

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

OUTPUT:

RESULT:

Thus, the program for finding shortest path using Prim’s algorithm has been
implemented and executed successfully.
 lOMoARcPSD|65785340

[Link] ALL-PAIRS- SHORTEST-PATHS PROBLEM

DATE :
AIM:

To Implement a Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.

ALGORITHM:
Step 1: Initialize the solution matrix same as the input graph matrix as a first step.
Then we update the solution matrix by considering all vertices as an intermediate
vertex. The ideas is to one by one pick all vertices and update all shortest paths which
include the picked vertex as an intermediate vertex in the shortest path.
Step 2: When we pick vertex number k as an intermediate vertex, we already have considered
vertices {0, 1, 2, .. k-1} as intermediate vertices.
Step 3: For every pair (i, j) of source and destination vertices respectively, there are two
possible cases.
 k is not an intermediate vertex in shortest path from i to j. We keep the value
of dist[i][j] as it is.
 k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j]
asdist[i][k] + dist[k][j].

PROGRAM:

#include<stdio.h>

int min(int,int);

void 昀氀oyds(int p[10][10],int n)

Int i,j,k; for(k=1;k<=n;k++)

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
p[i][j]=0;
else
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(inta,int b){
if(a<b)
return(a);
else
return(b);
}
main(){
int p[10][10],w,n,e,u,v,i,j;
printf("\n Enter the number of
vertices:"); scanf("%d",&n);
printf("\n Enter the number of edges:\n");
 lOMoARcPSD|65785340

scanf("%d",&e);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
p[i][j]=999;
}
for(i=1;i<=e;i++){
printf("\n Enter the end vertices of edge%d with its weight \n",i); scanf("%d%d
%d",&u,&v,&w);
p[u][v]=w;
}
printf("\n Matrix of input data:\
n"); for(i=1;i<=n;i++) {
for(j=1;j<=n;j++)
printf("%d \t",p[i][j]);
printf("\n");
}
floyds(p,n);
printf("\n Transitive closure:\n");
for(i=1;i<=n;i++){ for(j=1;j<=n;j+
+)
printf("%d \t",p[i][j]);
printf("\n");
}
printf("\n The shortest paths are:\n"); for(i=1;i<=n;i+
+)
for(j=1;j<=n;j++)
{
if(i!
=j) printf("\n <%d,%d>=%d",i,j,p[i][j]);
}

}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:

Thus, the program for finding All-Pairs- Shortest-Paths using Floyd’s algorithm has
been implemented and executed successfully.
 lOMoARcPSD|65785340

[Link] WARSHALL'S ALGORITHM

DATE:

AIM:
To implement program for transitive closure of a given directed graph using
Warshall's algorithm.

ALGORITHM:

Step 1: Warshall (A[1...n, 1...n]) // A is the adjacency matrix

Step 2: R(0) ← A
Step 3: for k ← 1 to n do
for i ← 1 to n do
for j ← to n do
Step 4: Compute R(k)[i, j] ← R(k-1)[i, j] or (R(k-1)[i, k] and R(k-1)[k, j])
return R(n)

PROGRAM:

#include <stdio.h>

int n,a[10][10],p[10][10];
void path()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=a[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(p[i][k]==1&&p[k][j]==1)p[i][j]=1;
}
void main()
{
int i,j;
printf("Enter the number of
nodes:"); scanf("%d",&n);
printf("\nEnter the adjacency matrix:\
n"); for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
path();
 lOMoARcPSD|65785340

printf("\nThe path matrix is shown below\n"); for(i=0;i<n;i+

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

OUTPUT:

RESULT:

Thus, the program for finding All-Pairs- Shortest-Paths using Floyd’s algorithm has
been implemented and executed successfully.
 lOMoARcPSD|65785340

[Link] MAXIMUM AND MINIMUM NUMBERS

DATE:

AIM:

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

ALGORITHM:

Step 1: Algorithm: Max-Min-Element (numbers[])

max := numbers[1]
min := numbers[1]
Step 2: for i = 2 to n do
if numbers[i] > max then
max := numbers[i]
if numbers[i] < min then
min := numbers[i]
Step 3: return (max, min)

PROGRAM:

#include<stdio.h>
#include<stdio.h>
int max, min;
int a[100];
void maxmin(int i, int j)
{
int max1, min1, mid;
if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1)
{
if(a[i] <a[j])
{
max = a[j];
min = a[i];
}
else
{
max = a[i];
min = a[j];
 lOMoARcPSD|65785340

}
}
else
{
mid = (i+j)/2;
maxmin(i, mid);
max1 = max; min1 =
min; maxmin(mid+1, j);
if(max <max1)
max = max1;
if(min > min1)
min = min1;
}
}
}
int main ()
{
int i, num;
printf ("\nEnter the total number of numbers : ");
scanf ("%d",&num);
printf ("Enter the numbers : \n");
for (i=1;i<=num;i++)
scanf ("%d",&a[i]);

max = a[0];
min = a[0];
maxmin(1, num);
printf ("Minimum element in an array : %d\n", min);
printf ("Maximum element in an array : %d\n", max);
return 0;
}

OUTPUT:

Enter the total number of numbers : 5

Enter the numbers :
29
21
64
27
20
Minimum element in an array : 20
Maximum element in an array : 64

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 has been implemented and executed
successfully.
 lOMoARcPSD|65785340

[Link]-A MERGE SORT

DATE:

AIM:
To implement Merge sort method to sort an array of elements and determine the time
required to sort. Repeat the experiment for different values of n, the number of elements in
the list to be sorted and plot a graph of the time taken versus n.

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 <stdlib.h>
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 into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
 lOMoARcPSD|65785340

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++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

void printArray(int A[], int size)

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

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
 lOMoARcPSD|65785340

printf("Given array is \n");

printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

OUTPUT:

Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13

RESULT:
Thus, the C program for implementation of Merge sort algorithm was done and
executed successfully.
 lOMoARcPSD|65785340

[Link]: 12-B QUICK SORT

DATE:

AIM:

To implement Quick sort method to sort an array of elements and determine the time
required to sort. Repeat the experiment for different values of n, the number of elements in
the list to be sorted and plot a graph of the time taken versus n.

ALGORITHM:

Step 1:QUICKSORT (array A, start, end)

Step 2: Check if (start < end)
Step 3: p = partition(A, start, end)
Step 4: QUICKSORT (A, start, p - 1)
Step 5: QUICKSORT (A, p + 1, end)
Partition Algorithm:
Step 1: PARTITION (array A, start, end)
Step 2: Set pivot is first value of an
array. Step 3: i = start-1
Step 4: for j = start to end -1
Step 5: if (A[j] < pivot) then i = i + 1
Step 6: swap A[i] with A[j]
Step 7: swap A[i+1] with A[end]
Step 8: return i+1
Step 9: Stop

PROGRAM:

#include <stdio.h>
int partition (int a[], int start, int end)
{ int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++)
{
if (a[j] < pivot)
{
 lOMoARcPSD|65785340

i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}

void quick(int a[], int start, int end)

{
if (start < end)
{
int p = partition(a, start, end); //p is the partitioning index
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}
/* function to print an array */
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 24, 9, 29, 14, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:

Thus, the C program for implementation of Quick sort algorithm was done and
executed successfully.
 lOMoARcPSD|65785340

[Link] N QUEENS PROBLEM

DATE:

AIM:
To Implement N Queens problem using Backtracking.

ALGORITHM:

Step 1: Start in the leftmost column

Step 2: If all queens are placed return true
Step 3: Try all rows in the current column. Do following for every tried row.
 If the queen can be placed safely in this row then mark this [row,
column] as part of thesolution and recursively check if placing
queen here leads to a solution.
 If placing queen in [row, column] leads to a solution then return true.
 If placing queen doesn't lead to a solution then unmark this [row,
column] (Backtrack) and goto step (a) to try other rows.
Step 4: If all rows have been tried and nothing worked, return false to trigger Backtracking.

PROGRAM:

#include<stdio.h>

#include<math.h>

int a[30],count=0;

int place(int pos)

int i;

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

if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
return 0;
}
return 1;
}
void print_sol(int n)
{
int i,j;
count++;
printf("\n\nSolution #%d:\n",count);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
{
if(a[i]==j)
printf("Q\t");
else
 lOMoARcPSD|65785340

printf("*\t");
}
printf("\n");
}
}
void queen(int n){
int k=1;
a[k]=0;
while(k!=0){
a[k]=a[k]+1;
while((a[k]<=n)&&!place(k))
a[k]++;
if(a[k]<=n){
if(k==n)
print_sol(n);
else
{
k++;
a[k]=0;
}
}
else
k--;
}
}
void main(){
int i,n;
printf("Enter the number of Queens\
n"); scanf("%d",&n);
queen(n);
printf("\nTotal solutions=%d",count);
}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:
Thus, the implementation of N Queens problem using Backtracking method was done
and executed successfully.
 lOMoARcPSD|65785340

[Link] TRAVELING SALESPERSON PROBLEM

DATE:

AIM:
Implement any scheme to find the optimal solution for the Traveling Salesperson
problem and then solve the same problem instance using any approximation algorithm and
determine the error in the approximation.

ALGORITHM:
Step 1: Start
Step 2: Check for the disconnection between the current city and the next
city Step 2: Check whether the travelling sales person has visited all the
cities Step 3: Find the next city to be visited
Step 4: Find the solution and terminate
Step 5: End
PROGRAM:
#include<stdio.h>

int s,c[100][100],ver;

昀氀oat op琀椀mum=999,sum;

/* func琀椀on to swap array elements */

void swap(int v[], int i, int j)

int t;
t = v[i];

v[i] = v[j];

v[j] = t;

}
/* recursive func琀椀on to generate permuta琀椀ons */

Void brute_force(int v[], int n, int i)

// this func琀椀on generates the permuta琀椀ons of the array from element i to element n-1

int j,sum1,k;

//if we are at the end of the array, we have one permuta琀椀on

 lOMoARcPSD|65785340

if (i == n) {

if(v[0]==s)
{
for (j=0; j<n; j++)
prin琀昀 ("%d ", v[j]);

sum1=0;
for( k=0;k<n-1;k++)
{
sum1=sum1+c[v[k]][v[k+1]];
}

sum1=sum1+c[v[n-1]][s];
printf("sum = %d\
n",sum1); if
(sum1<optimum)
optimum=sum1;

}
}
else
// recursively explore the permuta琀椀ons star琀椀ng at index i going through index n-1*/

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

swap (v, i, j);

brute_force (v, n, i+1);

/* swap them back the way they were */

swap (v, i, j);
}
}
void nearest_neighbour(intver)

Int min,p,i,j,vis[20],from;

for(i=1;i<=ver;i++)
vis[i]=0;
vis[s]=1;

from=s;

sum=0;

for(j=1;j<ver;j++)
{
min=999;
for(i=1;i<=ver;i++)
if(vis[i] !=1 &&c[from][i]<min && c[from][i] !=0 )
 lOMoARcPSD|65785340

min= c[from][i];
p=i;
}

vis[p]=1;
from=p;
sum=sum+min;
}
sum=sum+c[from][s];
}
void main ()
{
Int ver,v[100],i,j;
printf("Enter n : ");
scanf("%d",&ver);
for (i=0; i<ver; i+
+) v[i] = i+1;
printf("Enter cost matrix\
n"); for(i=1;i<=ver;i++)
for(j=1;j<=ver;j++)
scanf("%d",&c[i][j]);
printf("\nEnter source : ");
scanf("%d",&s);
brute_force (v, ver, 0);
printf("\nOptimum solution with brute force technique is=%f\n",optimum);
nearest_neighbour(ver);
prin琀昀("\nSolu琀椀on with nearest neighbour technique is=%f\n",sum);

prin琀昀("The approxima琀椀on val is=%f",((sum/op琀椀mum)-1)*100);

prin琀昀(" % ");

}
 lOMoARcPSD|65785340

OUTPUT:

RESULT:
Thus, the implementation of Travelling Salesman problem was done and executed
successfully.