DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY

Course Code: 21CSEL48B

Descriptions: Design, develop, and implement the specified algorithms for the following
problems using C/C++ Language under LINUX /Windows environment.
1 Write C/C++ programs to perform Linear and Binary search of an element from a set
of n elements. Run the program for varied values of n> 5000 and record the time taken
to sort. Plot a graph of the time taken versus non graph sheet. The elements can be read
from a file or can be generated using the random number generator. Demonstrate using
C/C++ how the divide-and conquer method works along with its time complexity
analysis: worst case, average case and best case. Compare the performance of both the
algorithms.
ANS
Program 1

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

// Function to perform linear search in the given array

int linearSearch(int arr[], int n, int key) {

int i;
for ( i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1; // Key not found
}

// Function to perform binary search in the given array

int binarySearch(int arr[], int n, int key) {

int i, temp, mid, low, high;

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

for(int j = 0; j < n-i-1; j++) {
if(arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

low = 0;
high = n - 1;

1
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

while (low <= high) {

mid = (low + high) / 2;

if (arr[mid] == key) {
return mid;
}
else if (arr[mid] < key) {
low = mid + 1;
}
else {
high = mid - 1;
}
}

return -1; // Key not found

}

int main() {
int n1 = 5000, choice, key, index, i, j, n2= 5000;
int arr[10000];
clock_t start, end;
double cpu_time_used= 0.0;
FILE *fp1, *fp2;
fp1 = fopen("lin_search.txt", "w");
fp2 = fopen("bin_search.txt", "w");
srand(time(0));

for(;;) {
printf("\n---- MENU-DRIVEN ----\n");
printf("1. Linear search\n");
printf("2. Binary search\n");
printf("3. Exit\n");
printf("---------------------");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {

case 1:

for(j = 1; j<=10; j++) {

printf("\n N1 = %d\n", n1);

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

arr[i] = rand()%10000;

}
key = rand()%10000;
start = clock();

2
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

index = linearSearch(arr, n1, key);

if (index != -1) {
printf("Number found at index %d\n", index);
}
else {
printf("Number not found\n");
}
end = clock();
cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC;
fprintf (fp1, "%d\t %lf \n", i, cpu_time_used);
printf("Time taken: %.6f seconds\n", cpu_time_used);
n1 = n1 + 500;
}
fclose(fp1);
break;

case 2:

for(j = 1; j<=10; j++) {

printf("\n N2 = %d\n", n2);

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

arr[i] = rand()%10000;

}
key = rand()%10000;
start = clock();
index = binarySearch(arr, n2, key);
if (index != -1) {
printf("Number found at index %d\n", index);
} else {
printf("Number not found\n");
}

end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
fprintf (fp2, "%d\t %lf \n", i, cpu_time_used);
printf("Time taken: %.6f seconds\n", cpu_time_used);
n2 = n2 + 500;
}
fclose(fp2);
break;

case 3:
exit(0);
break;

3
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

default:
printf("Invalid choice! Please try again.\n");
break;
}
}
return 0;
}

OUTPUT
lin_search.txt bin_search.txt

5000 0.000056 5000 0.136673

5500 0.000055 5500 0.134766
6000 0.000039 6000 0.208132
6500 0.000060 6500 0.307331
7000 0.000039 7000 0.352812
7500 0.000066 7500 0.353222
8000 0.000067 8000 0.382119
8500 0.000133 8500 0.439895
9000 0.000070 9000 0.515453
9500 0.000073 9500 0.560885

Graphs For the Given Input Size and Time Taken

1. Graph For Linear Search

4
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

2. Graph For Binary Search

2. Write C/C++ programs to sort a given set of n integer elements using Quick Sort method
and compute its time Complexity. Run the program for varied values of n> 5000 and
record the time taken to sort. Plot a graph of the time taken versus non graph sheet.
The elements can be read from a file or can be generated using the random number
generator. Demonstrate using C/C++ how the divide-and-conquer method works along
with its time complexity analysis: worst case, average case and best case.
ANS Program 2

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

void quicksort(int a[], int first, int last) {

int i, pivot, temp, j;

if (first < last) {

pivot = first;
i = first;
j = last;

while (i < j) {
while (a[i] <= a[pivot] && i < last)
i++;
while (a[j] > a[pivot])
j--;
5
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

temp = a[pivot];
a[pivot] = a[j];
a[j] = temp;

quicksort(a, first, j - 1);

quicksort(a, j + 1, last);
}
}

int main() {
int first, last, a[100000], i, j;
clock_t start, end;
double cpu_time_taken;
int n = 1000;
first = 0; last = n - 1;

FILE *fp1 = fopen("quick_sort", "w");

srand(time(0));

for (j= 1; j<=10; j++) {

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

a[i] = rand() % 10000;
}

start = clock();
quicksort(a, first, last);
end = clock();
cpu_time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("%d\t \t %lf\n", n, cpu_time_taken);

fprintf(fp1, "%d\t %lf sec \n", n, cpu_time_taken);
n = n +1000;
}
fclose(fp1);
return 0;
}

6
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

OUTPUT
quick_sort

1000 0.000213 sec

2000 0.000208 sec
3000 0.000215 sec
4000 0.000226 sec
5000 0.000333 sec
6000 0.000210 sec
7000 0.000254 sec
8000 0.000210 sec
9000 0.000207 sec
10000 0.000235 sec

Graph For the Given Input Size and Time Taken

1. Quick Sort

7
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B
3 Write C/C++ programs to Sort a given set of n integer elements using Merge Sort
method and compute its time complexity. Run the program for varied values of n> 5000,
and record the time taken to sort. Plot a graph of the time taken versus non graph sheet.
The elements can be read from a file or can be generated using the random number
generator. Demonstrate using C/C++ how the divide-and-conquer method works along
with its time complexity analysis: worst case, average case and best case.
ANS Program 3

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

void merge(int arr[], int low, int mid, int high) {

int leftSize = mid - low + 1;
int rightSize = high - mid;

int left[leftSize];
int right[rightSize];

int i, j, k;

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

left[i] = arr[low + i];
}

for (j = 0; j < rightSize; j++) {

right[j] = arr[mid + 1 + j];
}

i = 0;
j = 0;
k = low;

while (i < leftSize && j < rightSize) {

if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}

while (i < leftSize) {

arr[k] = left[i];
i++;
k++;
}

while (j < rightSize) {

8
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B
arr[k] = right[j];
j++;
k++;
}
}

void mergeSort(int arr[], int low, int high) {

if (low < high) {
int mid = low + (high - low) / 2;

mergeSort(arr, low, mid);

mergeSort(arr, mid + 1, high);

merge(arr, low, mid, high);

}
}

int main() {
int size, n = 1000, j;
int arr[100000];
double cpu_time_used;
clock_t start, end;
FILE *fp1 = fopen("merge_sort.txt", "w");

srand(time(0)); // Seed the random number generator

printf("Array Size\tTime (seconds)\n");

// Perform Merge Sort for different array sizes

for (j = 1; j <= 10; j++) {

size = n;

// Generate random elements in the array

for (int i = 0; i < size; i++) {
arr[i] = rand() % 10000;

// Calculate the time required for Merge Sort

start = clock();
mergeSort(arr, 0, size - 1);
end = clock();

cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

// Print the array size and corresponding time in the terminal

printf("%d\t\t%.6f\n", n, cpu_time_used);

// Print the array size and corresponding time in the file

fprintf(fp1, "%d\t%.6f sec\n", n, cpu_time_used);
9
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

n = n + 1000;
}

fclose(fp1);
printf("\nMerge Sort results stored in 'merge_sort.txt' for X-graph.\n");

return 0;
}
OUTPUT
merge_sort.txt

1000 0.000528 sec

2000 0.000770 sec
3000 0.001343 sec
4000 0.001535 sec
5000 0.001942 sec
6000 0.002594 sec
7000 0.003437 sec
8000 0.003849 sec
9000 0.003759 sec
10000 0.005360 sec

Graph For the Given Input Size and Time Taken

1. Merge Sort

10
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B
5. From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Dijkstra's algorithm. Write the program in C/C++.
ANS
Program 4

#include<stdio.h>
#define INF 9999
#define MAX 10

void dijkstra (int G[MAX][MAX], int n, int stnode)

{
int cost[MAX][MAX], dis[MAX], pred[MAX];
int vis[MAX] = {0}, count, mindist, nextnode, i,j;

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

for(j=0; j<n; j++)
cost[i][j] = G[i][j] ? G[i][j] : INF;

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

{
dis[i] = cost[stnode][i];
pred[i] = stnode;
}
dis[stnode] = 0;
vis[stnode] = 1;
count = 1;

while(count < n)
{
mindist = INF;

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

if(dis[i] < mindist && !vis[i])
{
mindist = dis[i];
nextnode = i;
}
vis[nextnode] = 1;
for(i=0; i<n; i++)
if (!vis[i])
if(mindist + cost[nextnode][i] < dis[i])
{
dis[i] = mindist + cost[nextnode][i];
pred[i] = nextnode;
}
count++;
}

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

{

11
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

if(i != stnode)
{

printf("\n Distance of the Node %d = %d", i,dis[i]);

printf("\nPath = %d", stnode);
int temp[MAX];
int temp_count = 0;
j = i;
do {
temp[temp_count++] = j;
j = pred[j];
} while (j != stnode);

for(j = temp_count - 1; j>=0; j--)

printf(" -> %d", temp[j]);
} printf("\n");
}
}

int main()
{
int G[MAX][MAX], i, j, n ,u;
printf("\nEnter the Number of Vertices: ");
scanf("%d", &n);
printf("\nEnter the Adjacency Matrix: \n");
for(i=0; i<n; i++)
for(j=0; j<n; j++)
scanf("%d", &G[i][j]);
printf("\nEnter the Starting Node: \n");
scanf("%d", &u);
dijkstra(G, n, u);

return 0;
}

12
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

OUTPUT
Dijkstra’s Algorithm

Enter the Number of Vertices: 5

Enter the Adjacency Matrix:

03070
30420
04056
72504
00640

Enter the Starting Node:

0

Distance of the Node 1 = 3

Path = 0 -> 1

Distance of the Node 2 = 7

Path = 0 -> 1 -> 2

Distance of the Node 3 = 5

Path = 0 -> 1 -> 3

Distance of the Node 4 = 9

Path = 0 -> 1 -> 3 -> 4

6. Find Minimum Cost Spanning Tree of a given connected undirected graph using
Kruskal's algorithm. Use Union-Find algorithms in your program. Write the program
in C/C++.
ANS
Program 5

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

int parent[9];

int find(int i)
{
while (parent[i])
i = parent[i];
return i;
}

int uni (int i, int j)

{
if(i!=j)

13
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

{
parent[j] = i;
return 1;
}
return 0;
}

void kruskal (int cost[9][9], int n)

{
int i,j,k,a,b,u,v,ne=1;
int min, mincost = 0;
for(i=1; i<=n; i++)
parent[i] = 0;
printf("The edges of minimum cost Spanning tree are: \n");
while(ne < n)
{
for(i=1, min=999; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(cost[i][j] < min)
{
min = cost[i][j];
a=u=i;
b=v=j;
}
}
}
u = find(u);
v = find(v);
if(uni(u,v))
{
printf("%d edge (%d %d) = %d\n", ne++, a,b,min);
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("\n minimum Cost = %d\n", mincost);
}

int main()
{
printf("Kruskal's Algorithm.\n");
int n, i,j;
printf("Enter the Number of Vertices: \n");
scanf("%d", &n);
int cost[9][9];
printf("\n Enter the Cost of Adjacancy Matrix: \n");
for(i=1; i<=n; i++)

14
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B

{
for(j=1; j<=n; j++)
{
scanf("%d", &cost[i][j]);
if(cost[i][j] == 0)
cost[i][j] = 999;
}
}
kruskal(cost, n);
return 0;
}

OUTPUT
Kruskal's Algorithm.

Enter the Number of Vertices: 5

Enter the Cost of Adjacency Matrix:

03070
30420
04056
72504
00640

The edges of minimum cost Spanning tree are:

1 edge (2 4) = 2
2 edge (1 2) = 3
3 edge (2 3) = 4
4 edge (4 5) = 4

minimum Cost = 13

7. Find Minimum Cost Spanning Tree of a given connected undirected graph using Prim's
algorithm. Write the program in C/C++.
ANS
Program 6

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

int a,b,u,v,n,i,j,ne = 1;
int vis[10] = {0}, min, mincost = 0, cost[10][10];

void main()
{
printf("\n Enter the Number of Vertices: \n");
scanf("%d", &n);
printf("\n Enter the adjacency Matrix: \n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
15
Dept. CSE, BMSIT&M
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY
Course Code: 21CSEL48B
{
scanf("%d", &cost[i][j]);
if(cost[i][j] == 0)
cost [i][j] = 999;
}
vis[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(vis[i] !=0)
{
min = cost[i][j];
a = u = i;
b = v = j;
}
if(vis[u] == 0 || vis[v] == 0)
{
printf("\n edge %d : (%d %d) cost : %d", ne++, a,b,min);
mincost += min;
vis[b] = 1;
}
cost[a][b] = cost[b][a] = 999;
}

printf("\n minimum cost = %d\n", mincost);

}
OUTPUT
Prim’s Algorithm

Enter the Number of Vertices: 5

Enter the adjacency Matrix:

03070
30420
04056
72504
00640

edge 1 : (1 2) cost : 3
edge 2 : (2 4) cost : 2
edge 3 : (2 3) cost : 4
edge 4 : (4 5) cost : 4

Minimum cost = 13

16
Dept. CSE, BMSIT&M