Brindavan College

Dwarakanagar, Bagalur Main Road, Yelahanka, Bengaluru - 560063

Approved by AICTE, Recognized by Government & UGC
Affiliated to Bengaluru City University, Karnataka, India
Accredited at the “B”+ Level by NAAC
www.brindavancollege.com
IV Semester

Design and Analysis of

Algorithms Lab
CA-C17P
ACADEMIC YEAR
2024 – 2025

LABORATORY MANUAL
PREPARED BY
Prof. Rashmi P C
Assistant Professor, Dept. of BCA
 Brindavan College
Department of BCA

IV Semester

Design and Analysis of Algorithms Lab

CA-C17P

ACADEMIC YEAR
2024 – 2025

NAM E OF THE STUDENT :

UNIVERSITY SEAT NO. :

BATCH :

PREPARED BY

Asst. Prof. Rashmi P C

 Brindavan College
Department of BCA

LABORATORY CERTIFICATE
This is to certify that Mr. /Ms. ____
bearing USN___ of __ branch
and ____ semester has satisfactorily completed the course of experiments in Design
and Analysis of Algorithms Lab, code CA-C17P prescribed by the Bengaluru City
University, Bengaluru of this Institute for the academic year 2024 – 2025.

MARKS

Maximum Marks Marks Obtained

Signature of Faculty-In-Charge Head of the Department

Date:
 Brindavan College
Dwarakanagar, Bagalur Main Road, Yelahanka, Bengaluru - 560063
Approved by AICTE, Recognized by Government & UGC
Affiliated to Bengaluru City University, Karnataka, India
Accredited at the “B”+ Level by NAAC

Department of BCA

DEPARTMENT VISION

The Department of BCA is aimed to invent technologies of tomorrow that

seem impossible today.

DEPARTMENT MISSION

• To provide creative and disseminating IT knowledge to the

undergraduates.
• To imparting IT skills and aptitude.
 Brindavan College
Dwarakanagar, Bagalur Main Road, Yelahanka, Bengaluru - 560063
Approved by AICTE, Recognized by Government & UGC
Affiliated to Bengaluru City University, Karnataka, India
Accredited at the “B”+ Level by NAAC

Department of BCA

DOs & DON’Ts IN LABORATORY

DOs
➢ Be on time and students should carry observation and completed records in all
aspects.
➢ Dress code & wearing ID card is compulsory.
➢ Electronic gadgets are not allowed inside the lab.
➢ Students should be at their concerned desktop.
➢ After execution the students should get it verified by the concerned faculty.
➢ The executed results should be noted in their observations and get it verified by the
concerned faculty.
➢ Observe good housekeeping practices. Keep the equipment’s in proper place after the
conduction.
➢ Students must ensure that all the switches are in the OFF position; desktop is
shutdown properly after completion of the assignments.

DON’Ts

➢ Do not come late to lab.

➢ Do not touch server computer.
➢ Do not leave the lab without the permission of the faculty in-charge.
➢ Do not wear footwear and enter the lab.
➢ Do not insert pen drive/memory card to any computer in the lab.
➢ Do not upload, delete or alter any software files.
 Data Structures LAB

Course Code: CA-C17P CIE Marks: 10

Teaching Hours/Week (L:T:P:S): 04 Hours SEE Marks: 40
Credits: 04 Exam Hours: 03

Course objectives:
• Understand the fundamental concepts of algorithms and their design principles.
• Analyze the time and space complexity of algorithms using Big O, Omega, and Theta notations.
• Apply sorting and searching algorithms to solve computational problems.
• Design and implement algorithms using techniques like divide-and-conquer, dynamic
programming, and greedy strategies

Laboratory Experiments

SI.NO. Experiments
1 Write a program to implement linear search algorithm 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.
2 Write a program to implement binary search algorithm. 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.
3 Write a program to solve towers of honai problem and execute it for
different number of disks.

4 Write a Program to Sort a given set of numbers using selection sort

algorithm. 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.
The elements can be read from a file or can be generated using the random
number generator.
5 Write a program to find the value of an (where a and n are integers) using
both brute-force based algorithm and divide and conquer based algorithm.
6 Write a Program to Sort a given set of elements using quick sort algorithm.
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.
7 Write a Program to find the binomial co-efficient C(n, k), [where n and k
are integers and n > k] using brute force based algorithm and also dynamic
programming based algorithm.
8 Write a Program to implement Floyd’s algorithm and find the lengths of
the shortest paths from every pairs of vertices in a given weighted graph.
9 Write a program to evaluate a polynomial using brute-force based
algorithm and using Horner’s rule and compare their performances.
Write a Program to solve the string matching problem using Boyer-Moore
10
approach.
SI.NO. Experiments
11 Write a Program to solve the string matching problem using KMP
algorithm.
12 Write a program to implement BFS traversal algorithm.

Write a program to find the minimum spanning tree of a given graph using
13
Prim’s algorithm
14 Write a Program to obtain the topological ordering of vertices in a given
digraph. Compute the transitive closure of a given directed graph using
Warshall's algorithm.
15 Write a Program to Find a subset of a given set S = {s1,s2, ,sn} of n positive
integers whose ..... sum is equal to a given positive integer d. For example, if
S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6} and {1,8}.A suitable
message is to be displayed if the given problem instance doesn't have a
solution

Course outcomes:
At the end of the course the student will be able to:

• Understand the fundamental concepts of algorithms and their design principles.

• Analyze the time and space complexity of algorithms using Big O, Omega, and Theta
notations.
• Apply sorting and searching algorithms to solve computational problems.
• Design and implement algorithms using techniques like divide-and-conquer, dynamic
programming, and greedy strategies.
Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
CONTENTS
EXPT. NAME OF THE EXPERIMENT PAGE
N O. NO.
1 Write a program to implement linear search algorithm 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. 2
Write a program to implement binary search algorithm. Repeat the
2 experiment for different values of n, the number of elements in the list to 6
be searched and plot a graph of the time taken versus n .
Write a program to solve towers of honai problem and execute it for
3 different number of disks. 9
4 Write a Program to Sort a given set of numbers using selection sort
algorithm. Repeat the experiment for different values of n, the number 13
of elements in the list to be sorted and plot a graph of the time taken
versus n. The elements can be read from a file or can be generated using
the random number generator.
Write a program to find the value of an (where a and n are integers)
5 using both brute-force based algorithm and divide and conquer based 17
algorithm.
Write a Program to Sort a given set of elements using quick sort
6 algorithm. Repeat the experiment for different values of n, the number 21
of elements in the list to be sorted and plot a graph of the time taken
versus n.
Write a Program to find the binomial co-efficient C(n, k), [where n and
7 k are integers and n > k] using brute force based algorithm and also 23
dynamic programming based algorithm.
Write a Program to implement Floyd’s algorithm and find the lengths of
8 the shortest paths from every pairs of vertices in a given weighted graph. 25
9 Write a program to evaluate a polynomial using brute-force based
algorithm and using Horner’s rule and compare their performances. 30
10 Write a Program to solve the string matching problem using Boyer-
Moore approach 33
11 Write a Program to solve the string matching problem using KMP
algorithm. 35
12 Write a program to implement BFS traversal algorithm. 39
13 Write a program to find the minimum spanning tree of a given graph 42
using Prim’s algorithm
14 Write a Program to obtain the topological ordering of vertices in a given 45
digraph. Compute the transitive closure of a given directed graph using
Warshall's algorithm.
15 Write a Program to Find a subset of a given set S = {s1,s2, ,sn} of n 54
positive integers whose ..... sum is equal to a given positive integer d. For
example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6} and
{1,8}.A suitable message is to be displayed if the given problem instance
doesn't have a solution

Department of BCA, Brindavan College 1

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
OUTPUT

Department of BCA, Brindavan College 2

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

1. Write a program to implement linear search algorithm

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.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to perform linear search

int linear_search(int *arr, int n, int key) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == key)
return i; // If key is found, return the index
}
return -1; // If key is not found, return -1
}

int main() {
int n, i, key;
printf("Enter the number of elements: ");
scanf("%d", &n);

int *arr = malloc(n * sizeof(int));

printf("\nEnter the elements of an array: ");

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

printf("\nEnter the key element to be searched: ");

scanf("%d", &key);

// Repeat the search operation multiple times to amplify the time taken
int repeat = 1000000;
int result;

clock_t start = clock();

for (i = 0; i < repeat; i++) {
result = linear_search(arr, n, key);

Department of BCA, Brindavan College 3

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
}
clock_t end = clock();

if (result != -1) {
printf("\nKey %d Found at Position %d", key, result);
} else {
printf("\nKey %d Not Found", key);
}

double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000; // In

milliseconds
printf("\nTime taken to search a key element = %f milliseconds\n", time_taken);

return 0;
}

OUTPUT

Run 1:
Enter the number of elements: 5
Enter the elements of an array: 10 20 30 40 50
Enter the key element to be searched: 50
Key 50 found at 4
Time taken to search a key element = 64.000000 milliseconds

Run 2:
Enter the number of elements: 10
Enter the elements of an array: 10 20 30 40 50 100 90 80 70 60
Enter the key element to be searched: 99
Key 99 not found
Time taken to search a key element = 134.000000 milliseconds.

Run 3:
Enter the number of elements: 20
Enter the elements of an array: 10 20 30 30 40 50 60 70 80 90 100 110 120 130 140
150 160 170 180 200
Enter the key element to be searched: 200
Key 200 found at position 19
Time taken to search a key element = 404.000000 milliseconds.

Department of BCA, Brindavan College 4

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 5

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

2. Write a program to implement binary search algorithm.

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.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int binary_search(int* arr, int low, int high, int key) {

while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) {
return mid; // If key is found, return the index
}
if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // If key is not found, return -1
}

int main() {
int n, i, key;
printf("Enter the number of elements: ");
scanf("%d", &n);

Department of BCA, Brindavan College 6

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
int *arr = malloc(n * sizeof(int));
printf("\nEnter the elements of an array in ascending order: ");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("\nEnter the key element to be searched: ");

scanf("%d", &key);

// Repeat the search operation multiple times to amplify the time taken
int repeat = 1000000;
int result;

clock_t start = clock();

for (i = 0; i < repeat; i++) {
result = binary_search(arr, 0, n - 1, key);
}
clock_t end = clock();

if (result != -1) {
printf("\nKey %d Found at Position %d", key, result);
} else {
printf("\nKey %d Not Found", key);
}

double time_taken = ((double)(end - start) / CLOCKS_PER_SEC) * 1000; //

Convert to milliseconds
printf("\nTime taken to search a key element = %f milliseconds\n", time_taken);

Department of BCA, Brindavan College 7

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

free(arr);
return 0;
}
OUTPUT
Run 1:
Enter the number of elements: 5
Enter the elements of an array in ascending order: 10 20 30 40 50
Enter the key element to be searched: 50
Key 50 Found at Position 4
Time taken to search a key element = 83.000000 milliseconds

Run 2:
Enter the number of elements: 10
Enter the elements of an array in ascending order: 10 20 30 40 50 60 70 80 90
100
Enter the key element to be searched: 120
Key 120 Not Found
OUTPUT
Time taken to search a key element = 127.000000 milliseconds

Run :
Enter the number of elements: 20
Enter the elements of an array in ascending order: 10 20 30 40 50 60 70 80 90
100 110 120 130 140 150 160 170 180 190 200
Enter the key element to be searched: 200
Key 200 Found at position 19
Time taken to search a key element = 156.000000 milliseconds

Department of BCA, Brindavan College 8

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 9

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

3. Write a program to solve towers of honai problem and

execute it for different number of disks.
#include <stdio.h>

void toh(int, char, char, char);

int count = 0;

int main() {
char source = 'S', temp = 'T', dest = 'D';
int n;
printf("Enter the number of disks: ");
scanf("%d", &n);
toh(n, source, dest, temp);
printf("The number of moves: %d", count);
return 0;
}

void toh(int n, char source, char dest, char temp) {

if (n > 0) {
toh(n - 1, source, temp, dest);
printf("Move Disk %d %c -> %c\n", n, source, dest);
count++;
toh(n - 1, temp, dest, source);
}
}
OUTPUT

Department of BCA, Brindavan College 10

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

Run 1

Enter the number of disks: 2

Sequence:
Move Disk 1 S -> T
Move Disk 2 S -> D
Move Disk 1 T -> D
The number of moves: 3

Run 2

Enter the number of disks: 3

Sequence:
Move Disk 1 S -> D
Move Disk 2 S -> T
Move Disk 1 D -> T
Move Disk 3 S -> D
Move Disk 1 T -> S
Move Disk 2 T -> D
Move Disk 1 S -> D
The number of moves: 7

Department of BCA, Brindavan College 11

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 12

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

4. Write a Program to Sort a given set of numbers using

selection sort algorithm. 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. The elements can be
read from a file or can be generated using the random
number generator.
#include<stdlib.h>
#include<stdio.h>
#include<time.h>

int min(int a[], int k, int n)

{
int loc, j, min;
min = a[k];
loc = k;
for(j = k+1; j < n; j++)
{
if (min > a[j])
{
min = a[j];
loc = j;
}
}
return loc;
}
int main()
{
int i, *arr, k, n, loc=0, temp;
srand(time(0)); // Seed the random number generator
printf("Enter the number of elements: ");
scanf("%d", &n);
arr = malloc(n * sizeof(int));
printf("\n Populating the array with random numbers... \n");

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

arr[i] = rand() % 100; // populates the array with random numbers
clock_t start = clock(); // start time
for(k = 0; k < n; k++)

Department of BCA, Brindavan College 13

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
{
loc = min(arr, k, n); // find the smallest element location
temp = arr[k];
arr[k] = arr[loc];
arr[loc] = temp;
}

clock_t end = clock(); // end time

double time_taken = ((double)end(end - start) / CLOCKS_PER_SEC * 1000);

printf("\n The Sorted Array is: ");

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

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

printf("\n Time taken to sort the array = %f ms\n", time_taken);

return 0;
}

OUTPUT

Run 1:
Enter the number of elements: 500
Populating the array with random numbers...
Time taken to sort the array = 1.000000 ms

Run 2:
Enter the number of elements: 1000
Populating the array with random numbers...
Time taken to sort the array = 8.000000 ms

Run 3:
Enter the number of elements: 1500
Populating the array with random numbers...
Time taken to sort the array = 16.000000 ms

Run 3:
Enter the number of elements: 2000
Populating the array with random numbers...
Time taken to sort the array = 29.000000 ms

Department of BCA, Brindavan College 14

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 15

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

5. Write a program to find the value of an (where a and n

are integers) Susing both brute-force based algorithm and
divide and conquer based algorithm.

#include<stdio.h>

// Function to calculate aⁿ using brute force method

int power_bruteforce(int a, int n) {
int i, result = 1;
for(i = 0; i < n; i++) {
result *= a;
}
return result;
}

// Function to calculate aⁿ using divide and conquer method

int power_divide_conquer(int a, int n) {
if (n == 0)
return 1;
else if (n % 2 == 0)
return power_divide_conquer(a * a, n / 2);
else
return a * power_divide_conquer(a * a, n / 2);
}

int main() {
int a, n;
printf("Enter the value of a and n: ");
scanf("%d %d", &a, &n);

int result_brute = power_bruteforce(a, n);

int result_divide_conquer = power_divide_conquer(a, n);

printf("Result using brute force: %d\n", result_brute);

printf("Result using divide and conquer: %d\n", result_divide_conquer);

return 0;
}

Department of BCA, Brindavan College 16

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Enter the value of a and n: 2 8

Result using brute force: 256
Result using divide and conquer: 256

Department of BCA, Brindavan College 17

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 18

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

6. Write a Program to Sort a given set of elements using

quick sort algorithm. 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.

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

// Function to partition the array

int partition(int A[], int low, int high) {
int pivot, j, temp, i;
pivot = low;
i = low;
j = high;
while (i < j) {
while(i < high && A[i] <= A[pivot])
i++;
while(A[j] > A[pivot])
j--;
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[pivot];
A[pivot] = A[j];
A[j] = temp;
return j;
}

// Quick sort function

void quickSort(int A[], int low, int high) {
if (low < high) {
int j = partition(A, low, high);
quickSort(A, low, j - 1);
quickSort(A, j + 1, high);

Department of BCA, Brindavan College 19

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
}
}
int main() {
int i, n, *A;
srand(time(0)); // Seed the random number generator

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

scanf("%d", &n);

A = malloc(n * sizeof(int)); // Dynamic memory allocation

printf("\nPopulating the array with random numbers...\n");

for (i = 0; i < n; i++)
A[i] = rand() % 1000; // Generates random numbers between 0 and 999

clock_t start = clock(); // Start time

quickSort(A, 0, n - 1); // Perform quick sort
clock_t end = clock(); // End time

double time_taken = ((double)(end - start) / CLOCKS_PER_SEC) * 1000; //

Time in milliseconds

/* Uncomment if you want to see the sorted array

printf("\nThe Sorted Array is: ");
for (i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n");
*/

printf("\nTime taken to sort the array = %f milli seconds\n", time_taken);

free(A); // Free allocated memory

return 0;
}

Department of BCA, Brindavan College 20

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Run 1:
Enter the number of elements: 1000
Populating the array with random numbers...
Time taken to sort the array = 0.000000 milli seconds

Run 2:
Enter the number of elements: 5000
Populating the array with random numbers...
Time taken to sort the array = 0.000000 milli seconds

Run 3:
Enter the number of elements: 10000
Populating the array with random numbers...
Time taken to sort the array = 7.000000 milli seconds

Run 4:
Enter the number of elements: 15000
Populating the array with random numbers...
Time taken to sort the array = 10.000000 milli seconds

Run 5:
Enter the number of elements: 20000
Populating the array with random numbers...
Time taken to sort the array = 15.000000 milli seconds

Department of BCA, Brindavan College 21

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 22

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

7. Write a Program to find the binomial co-efficient C(n, k),

[where n and k are integers and n > k] using brute force
based algorithm and also dynamic programming based
algorithm.
#include <stdio.h>

// Function to calculate factorial for brute force method

int factorial(int n) {
int fact = 1;
for (int i = 2; i <= n; i++) {
fact *= i;
}
return fact;
}

// Brute force method to find binomial coefficient

int binomialCoeff_bruteForce(int n, int k) {
return factorial(n) / (factorial(k) * factorial(n - k));
}

// Dynamic programming method to find binomial coefficient

int binomialCoeff_DP(int n, int k) {
int C[11][11]; // Assume n <= 10 for simplicity

// Calculate values of binomial coefficients

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= (i < k ? i : k); j++) { // Min(i, k)
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}

Department of BCA, Brindavan College 23

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
return C[n][k];
}

int main() {
int n, k;
printf("Enter the values of n and k: ");
scanf("%d %d", &n, &k);

int result_bruteForce = binomialCoeff_bruteForce(n, k);

int result_DP = binomialCoeff_DP(n, k);

printf("Binomial Coefficient (Brute Force): %d\n", result_bruteForce);

printf("Binomial Coefficient (Dynamic Programming): %d\n", result_DP);

return 0;
}
OUTPUT

Enter the values of n and k: 5 2

Binomial Coefficient (Brute Force): 10
Binomial Coefficient (Dynamic Programming): 10

Department of BCA, Brindavan College 24

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 25

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

8. Write a Program to implement Floyd’s algorithm and find

the lengths of the shortest paths from every pairs of vertices
in a given weighted graph.

#include<stdio.h>
#include<limits.h>
#define INF 99999

// print the solution matrix

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

int i, j;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (D[i][j] == INF)
printf("%s", "INF");
else
printf("%d ", D[i][j]);
}
printf("\n");
}
}
// Implementing Floyd Warshall Algorithm
void floyd(int V, int **C) {
int i, j, k;
int *D = (int *)malloc(V * sizeof(int *));
for (i = 0; i < V; i++)
D[i] = (int *)malloc(V * sizeof(int));

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

for (j = 0; j < V; j++)
D[i][j] = C[i][j];

Department of BCA, Brindavan College 26

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

for (k = 0; k < V; k++) {

for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (D[i][k] + D[k][j] < D[i][j])
D[i][j] = D[i][k] + D[k][j];
}
}
}

printSolution(V, D);
}

int main() {
int i, j, V;
printf("Enter the number of vertices: ");
scanf("%d", &V);

// Allocate memory for the cost matrix

int *C = (int *)malloc(V * sizeof(int *));
for (i = 0; i < V; i++)
C[i] = (int *)malloc(V * sizeof(int));

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

printf("Enter 99999 for infinity\n");
printf("Enter 0 for cost(i, i)\n");

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

for (j = 0; j < V; j++)
scanf("%d", &C[i][j]);

floyd(V, C);
return 0;

Department of BCA, Brindavan College 27

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Enter the number of vertices : 4

Enter the cost matrix:
[enter 99999 for infinity]
[enter 0 for cost(i,i)]
0 99999 2 99999
3 0 99999 99999
99999 5 0 1
6 99999 99999 0
The following matrix shows the shortest distances between every
pair of vertices
0 7 2 3
3 0 5 6
7 5 0 1
6 13 8 0

Department of BCA, Brindavan College 28

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 29

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

9. Write a program to evaluate a polynomial using brute-force

based algorithm and using Horner’s rule and compare their
performances.

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

double bruteForce(int* coef, int n, double x) {

double sum = 0.0;
int i;
for (i = 0; i <= n; i++) {
sum += coef[i] * pow(x, i);
}
return sum;
}

double hornersRule(int* coef, int n, double x) {

double result = coef[n];
int i;
for (i = n - 1; i >= 0; i--) {
result = result * x + coef[i];
}
return result;
}

int main() {
int i, n;
printf("Enter the degree of the polynomial: ");
scanf("%d", &n);

int* coef = malloc((n + 1) * sizeof(int));

printf("Enter the coefficients from highest degree to lowest:\n");

for (i = n; i >= 0; i--) {
scanf("%d", &coef[i]);

Department of BCA, Brindavan College 30

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
}

double x;
printf("Enter the value of x: ");
scanf("%lf", &x);

clock_t start, end;

double time_used;

start = clock();
double brute_force_result = bruteForce(coef, n, x);
end = clock();
time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Brute force result: %.2f, time used: %f seconds\n", brute_force_result,
time_used);

start = clock();
double horners_rule_result = hornersRule(coef, n, x);
end = clock();
time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Horner rule result: %.2f, time used: %f seconds\n", horners_rule_result,
time_used);

free(coef);
return 0;
}
OUTPUT

[Let us evaluate value of 2x^3 - 6x^2 + 2x - 1 for x = 3, co-efficients are {2, -6, 2, -1}]
Enter the degree of the polynomial: 3
Enter the coefficients from highest degree to lowest:
2
-6
2
-1
Enter the value of x:3
Brute force result :5, time used : 0.000000 seconds
Honer rule result :5, time used : 0.000000 seconds

Department of BCA, Brindavan College 31

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 32

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

10. Write a Program to solve the string matching problem

using Boyer-Moore approach
#include <stdio.h>
#include <string.h>

#define MAX_CHARS 256

int max(int a, int b) {

return (a > b) ? a : b;
}

// Function to create the bad character heuristic table

void badCharHeuristic(char *str, int size, int badchar[MAX_CHARS]) {
int i;
for (i = 0; i < MAX_CHARS; i++)
badchar[i] = -1;

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

badchar[(int)str[i]] = i;
}

// Function to perform pattern search using Boyer-Moore Algorithm

void patternSearch(char *text, char *pat) {
int m = strlen(pat);
int n = strlen(text);

int badchar[MAX_CHARS];

// Fill the bad character heuristic table

badCharHeuristic(pat, m, badchar);

int s = 0; // s is the shift of the pattern relative to text

while (s <= (n - m)) {
int j = m - 1;

Department of BCA, Brindavan College 33

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

// Keep reducing j while characters match

while (j >= 0 && pat[j] == text[s + j])
j--;

if (j < 0) {
printf("\nPattern occurs at position = %d", s);
s += (s + m < n) ? m - badchar[(int)text[s + m]] : 1;
} else
s += max(1, j - badchar[(int)text[s + j]]);
}
}

int main() {
char text[100];
pat[100];

printf("Enter the text: ");

gets(text);
text[strlen(text) - 1] = '\0';

printf("Enter the pattern: ");

gets(pat);
pat[strlen(pat) - 1] = '\0';

patternSearch(text, pat);

return 0;
}
OUTPUT

Enter the text: SKYWARDPUBLISHERS

Enter the pattern: PUB
Pattern occurs at position = 7

Department of BCA, Brindavan College 34

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 35

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

11. Write a Program to solve the string matching problem

using KMP algorithm
#include <stdio.h>
#include <string.h>
void computeLPSArray(char* pat, int M, int* lps);
// Prints occurrences of pattern 'pat' in text 'txt'
void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);

// Create lps[] that will hold the longest prefix suffix values for pattern
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d \n", i - j);
j = lps[j - 1];
} else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1; }
}
}
// Fills lps[] for given pattern 'pat' of length 'M'
void computeLPSArray(char* pat, int M, int* lps) {
int len = 0; // length of the previous longest prefix suffix
lps[0] = 0; // lps[0] is always 0

Department of BCA, Brindavan College 36

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len ! == 0) {
len = lps[len -1];
} else {
lps[i] = 0;
i++; }
}
}}
int main() {
char txt[100];
char pat[100];
printf("Enter the text: ");
gets(txt);
txt[strlen(txt) - 1] = '\0';
printf("Enter the pattern: ");
gets(pat);
pat[strlen(pat) -1] = '\0';

KMPSearch(pat, txt);
return 0;

OUTPUT
Enter the text: SKYWARDPUBLISHERS
Enter the pattern: PUB
Found Pattern at index 7

Department of BCA, Brindavan College 37

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 38

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

12. Write a program to implement BFS traversal algorithm.

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

#define MAX 100

int C[MAX][MAX];
int visited[MAX];
int queue[MAX];
int n; // Number of vertices

void BFS(int V) {
int front = 0, rear = -1;
visited[V] = 1;
queue[++rear] = V;

while (front <= rear) {

V = queue[front++];
printf("%d ", V);

for (int i = 1; i <= n; i++) {

if (C[V][i] == 1 && visited[i] == 0) {
queue[++rear] = i;
visited[i] = 1;
}
}
}
}

int main() {
int i, j, V;

printf("Enter the number of vertices in the graph: ");

scanf("%d", &n);

printf("Enter the cost matrix of the graph:\n");

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

Department of BCA, Brindavan College 39

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual
for (j = 1; j <= n; j++)
scanf("%d", &C[i][j]);
}
for(i=1; i<=n; i++)
visited[i] = 0;

printf("Enter the starting vertex: ");

scanf("%d", &V);

printf("BFS Traversal of the graph is: ");

BFS(V);

return 0;
}

OUTPUT

RUN 1

• Enter the Number of vertices: 6

• Enter the Adjacency matrix (cost matrix):

011000

101100

110110

011011

001101

000110

• Starting vertex: 1
• BFS Traversal Output: 1 2 3 4 5 6

Department of BCA, Brindavan College 40

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 41

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

13. Write a program to find the minimum spanning tree of a

given graph using Prim’s algorithm.

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

int minKey(int key[], int mstSet[], int n) {

int min = INT_MAX, min_index;
int v;
for (v = 0; v < n; v++)
if (mstSet[v] == 0 && key[v] < min)
min = key[v], min_index = v;

return min_index;
}

int printMST(int parent[], int** c, int n) {

int totalWeight = 0;
int i;
printf("Edge Weight\n");
for (i = 1; i < n; i++) {
printf("%d - %d %d \n", parent[i] + 1, i + 1, c[i][parent[i]]);
totalWeight += c[i][parent[i]];
}
return totalWeight;
}

void primMST(int** c, int n) {

int* parent = malloc(n * sizeof(int));
int* key = malloc(n * sizeof(int));
int* mstSet = malloc(n * sizeof(int));

int i, count, u, v;
for (i = 0; i < n; i++) {
key[i] = INT_MAX, mstSet[i] = 0;
}
key[0] = 0;
parent[0] = -1;

Department of BCA, Brindavan College 42

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

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

u = minKey(key, mstSet, n);
mstSet[u] = 1;

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

if (c[u][v] && mstSet[v] == 0 && c[u][v] < key[v]) {
parent[v] = u, key[v] = c[u][v];
}
}
}

int totalWeight = printMST(parent, c, n);

printf("Total cost of the minimum spanning tree: %d\n", totalWeight);
}

int main() {
int n, i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);

int** c = malloc(n * sizeof(int*));

for (i = 0; i < n; i++) {
c[i] = malloc(n * sizeof(int));
}

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

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

primMST(c, n);
return 0;
}

Department of BCA, Brindavan College 43

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Enter the number of vertices: 5

Enter the cost adjacency matrix:

02060

20385

03007

68009

05790

Edge Weight

1-2 2

2-3 3

1-4 6

2-5 5

Total cost of the minimum spanning tree: 16

Department of BCA, Brindavan College 44

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 45

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

14. a) Write a Program to obtain the topological ordering of

vertices in a given digraph.
#include<stdio.h>

int main()
{
int n, count = 0, c[10][10], indeg[10], flag[10], i, j, k;

printf("Enter the no of vertices: ");

scanf("%d", &n);

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

indeg[i] = 0, flag[i] = 0;

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

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &c[i][j]);

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

for(i = 0; i < n; i++)
indeg[j] += c[i][j];

printf("The topological order is:\n");

while(count < n)
{
for(k = 0; k < n; k++)
{
if((indeg[k] == 0) && (flag[k] == 0))
{
printf("%d ", (k + 1));
flag[k] = 1;
}

Department of BCA, Brindavan College 46

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

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

{
if(c[k][i] == 1)
indeg[i]--;
}
count++;
}
}

return 0;
}
OUTPUT

Enter the no of vertices: 6

Enter the cost matrix:
011000
000110
000101
000000
000000
000000

The topological order is:

123456

Department of BCA, Brindavan College 47

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

b) Compute the transitive closure of a given directed graph

using Warshall's algorithm.
#include<stdio.h>

void warshallsc(int c[10][10], int n) {

int i, j, k;

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

{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (c[i][j] || (c[i][k] && c[k][j]))
c[i][j] = 1;
}
}
}
Printf(“The transitive closure of the graph is:\n”);

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

for (j = 0; j < n; j++)
printf("%d ", c[i][j]);
printf("\n");
}
}
int main() {
int c[10][10], n, i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);

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

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &c[i][j]);

warshallsc(c, n);
return 0;
}
OUTPUT

Department of BCA, Brindavan College 48

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

Enter the number of vertices: 4

Enter the adjacency cost matrix:
0101
0010
0001
1000

The transitive closure of the graph is:

1111
0111
1011
1111

Department of BCA, Brindavan College 49

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

OUTPUT

Department of BCA, Brindavan College 50

 Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

15. Write a Program to Find a subset of a given set S = {s1,s2,

,sn} of n positive integers whose ..... sum is equal to a given
positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9
there are two solutions {1,2,6} and {1,8}. A suitable message is
to be displayed if the given problem instance doesn't have a
solution.

#include<stdio.h>

int w[10], d, n, count, x[10], i;

void sum_of_subsets(int s, int k, int r) {

x[k] = 1;
if (s + w[k] == d) {
printf("\nSubset %d = ", ++count);
for (i = 0; i <= k; i++)
if (x[i])
printf("%d ", w[i]);
} else if (s + w[k] + w[k + 1] <= d) {
sum_of_subsets(s + w[k], k + 1, r - w[k]);
}
if ((s + r - w[k] >= d) && (s + w[k + 1] <= d)) {
x[k] = 0;
sum_of_subsets(s, k + 1, r - w[k]);
}
}

int main() {
int sum = 0, k;
printf("Enter the number of elements: ");
scanf("%d", &n);

printf("Enter the elements in ascending order: ");

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

printf("Enter the sum: ");

scanf("%d", &d);

Department of BCA, Brindavan College 51

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

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

x[i] = 0;
sum = sum + w[i];
}

if (sum < d || w[0] > d) {

printf("\nNo subset possible\n");
} else {
count = 0;
sum_of_subsets(0, 0, sum);
}

return 0;
}

OUTPUT

Enter the number of elements: 4

Enter the elements in ascending order: 7 11 13 24
Enter the sum: 31

Subset 1 = 7 11 13
Subset 2 = 7 24

Department of BCA, Brindavan College 52

Design and Analysis of Algorithms Lab CA-C17P
Lab Manual

Department of BCA, Brindavan College 53