Dayananda Sagar Academy of Technology
& Management
Opp. Art of living, Udayapura, Kanakapura road, Bengaluru- 560082
(An Autonomous college under VTU, Belagavi & Approved by
AICTE, New Delhi)
Accredited by NBA, New Delhi
Department of Computer Science & Engineering
(Artificial Intelligence)
(1st edition) 2025-2026
ANALYSIS & DESIGN OF ALGORITHMS LAB
Laboratory Manual (BCS404)
Compiled by: Subject handled by:
Prof. Priyanka R Dr. C Nandini
Assistant Professor VP, Prof. and Head of the dept.
Dept. of CSE(AI) Dept. of CSE(AI)
TABLE OF CONTENTS
SL.
Lab Programs
No.
Design and implement C Program to find Minimum Cost
Spanning Tree of a given connected undirected graph using
1.
Kruskal's algorithm.
Design and implement C Program to find Minimum Cost
2. Spanning Tree of a given connected undirected graph
using Prim's algorithm.
a. Design and implement C Program to solve All-Pairs Shortest
3. Paths problem using Floyd's algorithm.
b. Design and implement C Program to find the transitive closure
using Warshal's algorithm
Design and implement C Program to find shortest paths from a given
4. vertex in a weighted connected graph to other vertices using
Dijkstra's algorithm
5. Design and implement C Program to obtain the Topological ordering
of vertices in a given digraph
Design and implement C Program to solve 0/1 Knapsack problem
6. using Dynamic Programming method.
Design and implement C Program to sort a given set of n integer
7. elements using Selection 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 n. The
elements can be read from a file or can be generated using the
random number generator.
8. Design and implement C Program 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 n. The elements
can be read from a file or can be generated using the random number
generator
9. Design and implement C Program 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 n. The elements
can be read from a file or can be generated using the random number
generator.
10. Design and implement C Program for N Queen's problem using
Backtracking.
DAYANANDA SAGAR ACADEMY OF TECHNOLOGY &
MANAGEMENT
(Affiliated to Visvesvaraya Technological University,Belagavi &
Approved by AICTE,New Delhi)
Opp. Art of Living, Udayapura, Kanakapura Road, Bangalore – 560082
DEPARTMENT OF COMPUTER SCIENEC & ENGINEERING
(ARTIFICIAL INTELLIGENCE)
Accredited by NBA, New Delhi
Department Vision
"To create an enriching learning environment that imparts creative, learning
and research skills to students in the domain of artificial intelligence."
Department Mission
of artificial intelligence."
Department Mission
M1 : To Impart Strong foundation of statistics for understanding Artificial
Intelligence.
M2 : To develop skilled and knowledgeable professionals in the field of
Artificial Intelligence.
M3 : To contribute towards advanced AI technologies that provide increased
and better performance.
M4 : To collaborate with renowned companies for multidisciplinary research
and development.
M5 : To guide the students in learning and creative for developing intelligent
technology-based solutions to societal problems.
DAYANANDA SAGAR ACADEMY OF TECHNOLOGY &
MANAGEMENT
(Affiliated to Visvesvaraya Technological University,Belagavi &
Approved by AICTE,New Delhi)
Opp. Art of Living, Udayapura, Kanakapura Road, Bangalore – 560082
DEPARTMENT OF COMPUTER SCIENEC & ENGINEERING
(ARTIFICIAL INTELLIGENCE)
Accredited by NBA, New Delhi
1. Programme Educational Objectives (PEOs)
PEO 1:The Graduates of CSE(AI) acquire a comprehensive understanding of the
fundamentals of Artificial Intelligence (AI) and its applications.
PEO 2:To apply AI techniques and tools to solve real-world problems and create
innovative solutions.
PEO 3:To develop skills in data analysis, Cloud Computing, Full Stack
development and Machine learning for AI implementation.
PEO 4: To develop the ability to design, analyze, and evaluate the CSE( AI )
systems.
PEO 5:To foster creativity, innovative thinking, entrepreneurial Skills and a
commitment to lifelong learning in the field of CSE(AI) to contribute towards
DIGIWORLD.
2. Programme Specific Outcomes
PSO 1: To Apply Analytical Skills for Problem Solving in Engineering, Business
and Societal Applications using CSE (AI) Approaches safely and securely.
PSO 2: Ability to Enrich the Critical Thinking Skills and Decision making in
Emerging Technologies such as Natural Language Processing, Machine
Learning, Deep Learning, Data Analysis, Robotics and Computer Vision.
ADA Lab Manual
1 Design and implement C Program to find Minimum Cost Spanning Tree
of a given connected undirected graph using Kruskal's algorithm
# include <stdio.h>
int a,b,i,j,u,v,n;
int visited[10],edge=1, min, mincost=0, cost[10][10];
void kruskal(int n, int cost[10][10])
{
printf("The edge of the spanning tree are \n");
while(edge<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;
}
while(visited[u])
u=visited[u];
while(visited[v])
v=visited[v];
if(u!=v)
{
edge++;
printf("\n Edge (%d,%d)=%d", a,b,min);
mincost=mincost+min;
visited[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n The minimum cost =%d", mincost);
}
int main( )
{
printf("Enter the number of vertices:\n");
scanf("%d", &n);
printf("Enter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d", &cost[i][j]);
kruskal(n,cost);
return 0;
}
OUTPUT:
Enter the number of vertices:
4
Enter the cost adjacency matrix:
0 10 999 40 1
10 10
2
10 0 20 999
999 20 0 30 20
40 999 30 0 40
The edge of the spanning tree is 30
4 3
Edge (1, 2) =10
Edge (2, 3) =20
Edge (3, 4) =30
The minimum cost =60
2. Design and implement C Program to find Minimum Cost Spanning
Tree of a given connected undirected graph using Prim's algorithm
# include<stdio.h>
int n, a[10][10];
void min_spa_tree()
{
int i,j, u,v, min, sum,k;
int t[10][2],p[10],d[10],s[10],source;
min=9999;
source=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]!=0 && a[i][j]<=min)
{
min=a[i][j];
source=i;
}
}
}
for(i=1;i<=n;i++)
{
d[i]=a[source][i];
s[i]=0;
p[i]=source;
}
s[source]=1;
sum=0;
k=1;
for(i=1;i<n;i++)
{
min=9999;
u=-1;
for(j=1;j<=n;j++)
{
if(s[j]==0)
{
if(d[j]<=min)
{
min=d[j];
u=j;
}
}
}
t[k][1]=u;
t[k][2]=p[u];
k++;
sum+=a[u][p[u]];
s[u]=1;
for(v=1;v<=n;v++)
{
if(s[v]==0 && a[u][v]<d[v])
{
d[v]=a[u][v];
p[v]=u;
}
}
}
if(sum>=9999)
printf("spanning tree does not exits\n");
else
{
printf("spanning tree exists and min spanning tree is \n");
for(i=1;i<n;i++)
{
printf("%d", t[i][1]);
printf(" ");
printf("%d", t[i][2]);
printf("\n");
}
printf("The cost of the spanning tree is %d", sum);
printf("\n");
}
}
int main( )
{
int i,j;
printf("Enter the no of nodes\n");
scanf("%d", &n);
printf("Enter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d", &a[i][j]);
}
}
min_spa_tree( );
return 0;
}
OUTPUT:
Enter the no of nodes
4
Enter the cost adjacency matrix 1 2 10
0 10 999 40
10 0 20 999
999 20 0 30
40 999 30 0 20 40
4 3
Spanning tree exists and min spanning tree is
12 30
32
43
The cost of the spanning tree is 70
3. a) Design and implement C Program to solve All-Pairs Shortest Paths
problem using Floyd's algorithm.
b) Design and implement C Program to find the transitive closure using
Warshal's algorithm
a) Floyd's algorithm:
#include <stdio.h>
#define INF 99999 // Infinity
// Function to implement Floyd's algorithm
void floydWarshall(int graph[][4], int V) {
int dist[V][V], i, j, k;
// Initialize the distance matrix same as input graph matrix
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
// Calculate shortest paths using Floyd-Warshall algorithm
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printf("The following matrix shows the shortest distances"
" between every pair of vertices:\n");
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
int main() {
// Number of vertices in the graph
int V = 4;
// Graph representation as an adjacency matrix
int graph[4][4] = {{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}};
// Call the function
floydWarshall(graph, V);
return 0;
}
b) Warshal’s algorithm:
#include<stdio.h>
int n,i,j;
int a[10][10];
int p[10][10];
int write_data()
{
printf("the path matrix is shown below\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d",p[i][j]);
printf(" ");
}
printf("\n");
}
return 0;
}
void path_matrix()
{
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=a[i][j];
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(p[i][k]==1&&p[k][j]==1)
p[i][j]=1;
}
}
}
}
int main()
{
printf("enter the no. of nodes\n");
scanf("%d",&n);
printf("enter the adjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
path_matrix();
write_data();
return 0;
}
OUTPUT
Enter the no. of nodes
4
Enter the adjacency matrix 1 2
0100
0010
1001
0000 4 3
The path matrix is shown below
1111
1111
1111
0 000
4. Design and implement C Program to find shortest paths from a given
vertex in a weighted connected graph to other vertices using Dijkstra's
algorithm.
#include<stdio.h>
Void dijstra(int n, int v, int cost[10][10], int d[])
{
int count,u,i,j,s[10],min;
for(i=1;i<=n;i++)
{
s[i]=0;
d[i]=cost[v][i];
}
s[v]=1;
d[v]=1;
count=2;
while(count<=n)
{
min=999;
for(j=1;j<=n;j++)
if(d[j]<min && s[j]==0)
{
min=d[j];
u=j;
}
s[u]=1;
count++;
for(j=1;j<=n;j++)
if((d[u]+cost[u][j]<d[j])&&s[j]==0)
d[j]=d[u]+cost[u][j];
}
}
intmain( )
{
int n,i,j,v,c[10][10],d[10];
printf("Enter the no of nodes");
scanf("%d", &n);
printf("Enter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d", &c[i][j]);
printf("Enter the source vertex");
scanf("%d", &v);
dijstra(n,v,c,d);
printf("The shortest path");
for(j=1;j<=n;j++)
if(j!=v)
printf("\n%d->%d=%d", v,j,d[j]);
return 0;
}
OUTPUT:
Enter the number of nodes
3 1
Enter the cost adjacency Matrix
0 10 999 10
999 0 20
3 2
30 999 0 30
20
Enter the source vertex
1
The shortest path
1-->2=10
1-->3=30
5. Design and implement C Program to obtain the Topological ordering of
vertices in a given digraph
#include<stdio.h>
void find_indegree(int n,int a[10][10],int indegree[])
{
int i,j,sum;
for(j=1;j<=n;j++)
{
sum=0;
for(i=1;i<=n;i++)
sum=sum+a[i][j];
indegree[j]=sum;
}
}
void topological(int n,int a[10][10])
{
int i,k,u,v,top,t[10],indegree[10],s[10];
find_indegree(n,a,indegree);
top=-1;
k=1;
for(i=1;i<=n;i++)
if(indegree[i]==0)
s[++top]=i;
while(top!=-1)
{
u=s[top--];
t[k++]=u;
for(v=1;v<=n;v++)
{
if(a[u][v]==1)
{
indegree[v]--;
if(indegree[v]==0)
s[++top]=v;
}
}
}
printf("THE TOPOLOGICAL SEQUENCE IS \n");
for(i=1;i<=n;i++)
printf("%d\t",t[i]);
}
int main()
{
int i,j,n,a[10][10];
printf("ENTER THE NUMBER OF NODES\n");
scanf("%d",&n);
printf("ENTER THE ADJACENCY MATRIX\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
topological(n,a);
return 0;
}
OUTPUT:
1
ENTER THE NUMBER OF NODES
3
ENTER THE ADJACENCY MATRIX
3 2
011
000
010
THE TOPOLOGICAL SEQUENCE IS
1 3 2
6. Design and implement C Program to solve 0/1 Knapsack problem using
Dynamic Programming method.
#include<stdio.h>
#include<stdlib.h>
int w[10], p[10], v[10][10];
intMax(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int knapsack(int n,int c)
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=c;j++)
{
if(i==0||j==0)
v[i][j]=0;
elseif(j-w[i]>=0)
v[i][j]=Max(v[i-1][j],p[i]+v[i-1][j-w[i]]);
else
v[i][j]=v[i-1][j];
}
}
return v[n][c];
}
Void optimalsubset(int n,int c)
{
int i,j;
for(i=n,j=c;i>=1 && j>0;i--)
{
if(v[i][j]!=v[i-1][j])
{
printf("item %d\n",i);
j=j-w[i];
}
}
}
int main( )
{
int n,c,mp,i,j;
printf("enter the number of items \n");
scanf("%d",&n);
printf("enter the weights of each item\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("enter the profit of each item\n");
for(i=1;i<=n;i++)
scanf("%d",&profits[i]);
printf("enter the knapsack capacity\n");
scanf("%d",&c);
mp=knapsack(n,c);
printf("solution of the knapsack \n");
for(i=0;i<=n;i++)
{
for(j=0;j<=c;j++)
printf("%d\t",v[i][j]);
printf("\n");
}
printf("the maximal value is %d \n",mp);
printf("the items of optimal subset are\n");
optimalsubset(n,c);
return 0;
}
OUTPUT:
enter the number of items
4
enter the weights of each item
2
1
3
2
enter the profit of each item
12
10
20
15
Enter the knapsack capacity
5
Solution of the knapsack
0 0 0 0 0 0
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37
The maximal value is 37
The items of optimal subset are
Item 4
Item 2
Item 1
7. Design and implement C Program to sort a given set of n integer elements using
Selection 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 n. The elements can be read from a file or can be generated
using the random number generator.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to perform selection sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
// Function to generate random integers and store them in a file
void generateRandomNumbersToFile(int n, const char* filename) {
FILE *file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
srand(time(NULL)); // Seed for random number generation
for (int i = 0; i < n; i++) {
fprintf(file, "%d\n", rand());
}
fclose(file);
}
// Function to read integers from a file and store them in an array
void readIntegersFromFile(int arr[], int n, const char* filename) {
FILE *file = fopen(filename, "r");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
for (int i = 0; i < n; i++) {
fscanf(file, "%d", &arr[i]);
}
fclose(file);
}
int main() {
FILE *timeFile = fopen("time_vs_n.csv", "w");
if (timeFile == NULL) {
printf("Error opening file.\n");
exit(1);
}
fprintf(timeFile, "n, time_taken_ms\n");
for (int n = 5000; n <= 10000; n += 1000) {
// Generate random numbers and store in a file
generateRandomNumbersToFile(n, "random_numbers.txt");
// Read integers from the file
int arr[n];
readIntegersFromFile(arr, n, "random_numbers.txt");
// Measure the time taken to sort
clock_t start = clock();
selectionSort(arr, n);
clock_t end = clock();
double time_taken = ((double)(end - start)) * 1000 / CLOCKS_PER_SEC;
// Record the time taken
fprintf(timeFile, "%d, %lf\n", n, time_taken);
}
fclose(timeFile);
printf("Time taken for sorting recorded in time_vs_n.csv\n");
return 0;
}
OUTPUT:
Enter the size
The sorted array is
15
77
83
86
93
Time taken 1.000000
8. Design and implement C Program 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 n. The elements can be read from a file or can be generated
using the random number generator.
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define maxsize 3000
void quicksort(int a[],int l,int h)
{
int j;
if(l<h)
{
usleep(500000);
j=partition(a,l,h);
quicksort(a,l,j-1);
quicksort(a,j+1,h);
}
}
int partition(int a[],int l,int h)
{
int i,j,k,t;
k=a[l];
i=l+1;
j=h;
while(1)
{
while(l<h && k>=a[i])
i++;
while(k<a[j])
j--;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
else
{
t=a[l];
a[l]=a[j];
a[j]=t;
return j;
}
}
}
int main()
{
int a[maxsize],i,n;
double runtime=0;
printf("Enter the size \n");
scanf("%d",&n);
srand(1);// generates random numbers
for(i=1;i<=n;i++)
a[i]=rand()%100;
time_t start=time(NULL);
quicksort(a,1,n);
time_t end=time(NULL);
runtime=difftime(end,start);
printf("The sorted array is");
for(i=1;i<=n;i++)
printf("\n%d\n", a[i]);
printf("Time taken %f\n",runtime);
return 0;
}
OUTPUT:
Enter the number of elements to sort
10
The randomly generated numbers are:
83
86
77
15
93
35
86
92
49
21
The sorted elements are :
15
21
35
49
77
83
86
86
92
93
Time taken to sort=1.000000
9. Design and implement C Program 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 n. The elements can be read from a file or can be generated using
the random number generator.
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define maxsize 3000
Void merge(int a[],int low,int mid,int high)
{
int i,j,k,p;
int b[maxsize];
i=k=low;
j=mid+1;
while(i<=mid && j<=high)
{
if(a[i]<=a[j])
{
b[k]=a[i];
i=i+1;
}
else
{
b[k]=a[j];
j=j+1;
}
k=k+1;
}
if(i>mid)
for(p=j;p<=high;p++)
{
b[k]=a[p];
k=k+1;
}
else
for(p=i;p<=mid;p++)
{
b[k]=a[p];
k=k+1;
}
for(i=low;i<=high;i++)
a[i]=b[i];
}
Void mergesort(int a[],int low, int high)
{
int mid;
if(low<high)
{
usleep(50000);
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}
int main()
{
int a[maxsize],i,n;
double runtime=0;
printf("Enter the number of elements to sort\n");
scanf("%d", &n);
srand(1);
for(i=1;i<=n;i++)
a[i]=rand()%100;
printf("The randomly generated numbers are:\n");
for(i=1;i<=n;i++)
{ printf("%d\n", a[i]);
time_t start=time(NULL);
mergesort(a,1,n);
time_t end=time(NULL);
runtime=difftime(end,start);
}
printf("The sorted elements are :\n");
for(i=1;i<=n;i++)
printf("%d\n", a[i]);
printf("Time taken to sort=%f\n",runtime );
return 0;
}
OUTPUT:
Enter the number of elements to sort
5
The randomly generated numbers are:
83
86
77
15
93
The sorted elements are :
15
83
86
77
93
Time taken to sort=0.001
10. Design and implement C Program for N Queen's problem using Backtracking
#include<stdio.h>
#include<stdlib.h>
int x[10],n;
intdisplay()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(x[i]==j)
printf("\tQ");
else
printf("\t x");
printf("\n\n");
}
printf("\n\n");
return 0;
}
intplace(int k, int i)
{
int j;
for(j=1;j<=k-1;j++)
if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))
return 0;
return 1;
}
intnqueen(int k)
{
int i;
for(i=1;i<=n;i++)
if(place(k,i))
{
x[k]=i;
if(k==n)
display();
nqueen(k+1);
}
}
int main()
{
printf("enter the no. of queens\n");
scanf("%d",&n);
if(n==1||n==2||n==3)
printf(" nqueen solution doesnot exist\n");
else
printf("solution for nqueen\n");
nqueen(1);
}
OUTPUT:
Enter the no. of queens
4
solution for nqueen
x Q x x
x x x Q
Q x x x
x x Q x
x x Q x
Q x x x
x x x Q
x Q x x
