Academic Year 2024 – 2025(EVEN Semester)

LABMANUAL

Analysis and Design of Algorithms

(LABORATORY COMPONENT)
BCSL404
IV Semester CS

Prepared By

Veena G, Kalaiselvi S
Asst. Professor
Dept. of CSE
Vision and Mission of the Institute
Vision
To become a leading institute for quality technical education and research with ethical values.
Mission
M1: To continually improve quality education system that produces thinking engineers having
good technical capabilities with human values.
M2: To nurture a good eco-system that encourages faculty and students to engage in meaningful
research and development.
M3: To strengthen industry institute interface for promoting team work, internship and
entrepreneurship.
M4: To enhance educational opportunities to the rural and weaker sections of the society to equip
with practical skills to face the challenges of life.

Vision and Mission of the Department

Vision
To become a leading department engaged in quality education and research in the field of
computer science and engineering.

Mission
M1: To nurture a positive environment with state of art facilities conducive for deep learning
and meaningful research and development.

M2: To enhance interaction with industry for promoting collaborative research in emerging
technologies.
M3: To strengthen the learning experiences enabling the students to become ethical professionals
with good interpersonal skills, capable of working effectively in multi-disciplinary teams.
PROGRAM EDUCATIONAL OBJECTIVES (PEOS)
PEO 1: Successful and ethical professionals in IT and ITES industries contributing to societal
progress.
PEO 2: Engaged in life-long learning, adapting to changing technological scenarios.
PEO 3: Communicate and work effectively in diverse teams and exhibit leadership qualities.

PROGRAM SPECIFIC OUTCOMES (PSOs)

PSO 1: Analyze, design, implement and test innovative application software systems to meet the
specified requirements.
PSO 2: Understand and use systems software packages.
PSO 3: Understand the organization and architecture of digital computers, embedded systems
and computer networks.

PROGRAM OUTCOMES (POs)

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering

fundamentals, and an engineering specialization to the solution of complex engineering
problems.
2. Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.
3. Design/development of solutions: Design solutions for complex engineering problems and
design system components or processes that meet the specified needs with appropriate
consideration for the public health and safety, and the cultural, societal, and environmental
consideration.
4. Conduct investigations of complex problems: Use research-based knowledge and research
methods including design of experiments, analysis and interpretation of data, and synthesis
of the information to provide valid conclusions.
5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
engineering and IT tools including prediction and modeling to complex engineering
activities with an understanding of the limitations.
6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess
societal, health, safety, legal and cultural issues and the consequent responsibilities relevant
to the professional engineering practice.
7. Environment and sustainability: Understand the impact of the professional engineering
solutions in societal and environmental contexts, and demonstrate the knowledge of, and
need for sustainable development.
8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and
norms of the engineering practice.
9. Individual and team work: Function effectively as an individual, and as a member or leader
in diverse teams, and in multidisciplinary settings.
10. Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and
write effective reports and design documentation, make effective presentations, and give
and receive clear instructions.
11. Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member
and leader in a team, to manage projects and in multidisciplinary environments.
12. Life-long learning: Recognize the need for, and have the preparation and ability to engage
in independent and life-long learning in the broadest context of technological change.
 SYLLABUS
Progra
Program
m No.
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
1
undirected graph using Kruskal's algorithm.
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
2
undirected graph using Prim's algorithm
a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's
3 algorithm.
b. Design and implement C/C++ Program to find the transitive closure using Warshal's algorithm
Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted
4
connected graph to other vertices using Dijkstra's algorithm.
Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given
5
digraph.
Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic Programming
6
method.
Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack problems
7
using greedy approximation method.
Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive
8
integers whose sum is equal to a given positive integer d
Design and implement C/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
9
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
Design and implement C/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
10
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.
Design and implement C/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
11
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.
12 Design and implement C/C++ Program for N Queen's problem using Backtracking.

Table of contents
Exp. Experiments Page
No. No.
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a
1 1-3
given connected undirected graph using Kruskal's algorithm.
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a
2 4-6
given connected undirected graph using Prim's algorithm
a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths

3 problem using Floyd's algorithm. 7-8

b. Design and implement C/C++ Program to find the transitive closure using
Warshal's algorithm
Design and implement C/C++ Program to find shortest paths from a given vertex in a
4 9-10
weighted connected graph to other vertices using Dijkstra's algorithm.
Design and implement C/C++ Program to obtain the Topological ordering of vertices
5 11-12
in a given digraph.
Design and implement C/C++ Program to solve 0/1 Knapsack problem using
6 13-13
Dynamic Programming method.
Design and implement C/C++ Program to solve discrete Knapsack and continuous
7 14-16
Knapsack problems using greedy approximation method.
Design and implement C/C++ Program to find a subset of a given set S = {sl ,
8 17-18
s2,.....,sn} of n positive integers whose sum is equal to a given positive integer d
Design and implement C/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
9 values of n> 5000 and record the time taken to sort. Plot a graph of the time taken 19-20
versus n. The elements can be read from a file or can be generated using the random
number generator
Design and implement C/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
10 values of n> 5000 and record the time taken to sort. Plot a graph of the time taken 21-23
versus n. The elements can be read from a file or can be generated using the random
number generator.
11 Design and implement C/C++ Program to sort a given set of n integer elements using 24-26
 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.
12 Design and implement C/C++ Program for N Queen's problem using Backtracking. 27-30
ADA Lab Manual (BCSL404)

1. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given
connected undirected graph using Kruskal’s algorithm.

PROGRAM:
#include <stdio.h>
#define INF 999 // Representing no edge
#define MAX_VERTICES 11 // Maximum number of vertices

int parent[MAX_VERTICES],t[MAX_VERTICES][3],a[MAX_VERTICES]
[MAX_VERTICES];
// DFS Function to Check Connectivity
void dfs(int cost[MAX_VERTICES][MAX_VERTICES], int n, int visited[], int node) {
visited[node] = 1;
for (inti = 1; i<= n; i++) {
if (cost[node][i] != INF && !visited[i]) { // If connected and not visited
dfs(cost, n, visited, i);
}
}
}

// Function to Check if the Graph is Connected

intisConnected(int cost[MAX_VERTICES][MAX_VERTICES], int n) {
int visited[MAX_VERTICES] = {0}; // All nodes initially unvisited
dfs(cost, n, visited, 1); // Start DFS from vertex 1

// Check if all nodes were visited

for (inti = 1; i<= n; i++) {
if (!visited[i]) {
return 0; // Graph is disconnected
}
}
return 1; // Graph is connected
}

intfind(int v)
{
while(parent[v])
v = parent[v];
return v;
}
void union1(inti,int j)
{
parent[j] = i;
}
void kruskal(int n)
{
intk,i,j,u,v,min,r,c,sum=0;
for(k=1;k<n;k++)
{
min = 999;
for(i=1;i<n;i++)

Dept. of CSE, Vemana IT 1

ADA Lab Manual (BCSL404)

for(j=1;j<=n;j++)
{
if(i == j) continue;
if(a[i][j] < min)
{
u = find(i);
v = find(j);
if(u != v)
r = i, c = j, min = a[i][j];
}
}
union1(r,find(c));
t[k][1] = r;
t[k][2] = c;
sum += min;
}
printf("\nCost of Spanning Tree = %d",sum);
printf("\nEdges of Spanning Tree\n");
for(i=1;i<n;i++)
printf("%d -> %d\n",t[i][1],t[i][2]);
}
intmain()
{
inti,j,n;
printf("\nEnter the number of vertices : ");
scanf("%d",&n);
printf("\nEnter the Adjacency Matrix(999 for NoEdge)\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
if (!isConnected(a, n)) {
printf("\n Spanning Tree does NOT exist (Graph is disconnected) \n");
return 0; // Exit early
}

kruskal(n);
return 0;
}
OUTPUT:

Run 1:

Enter the number of vertices : 5

Enter the Adjacency Matrix(999 for NoEdge)

999 5 999 6 999
5 999 1 3 999
999 1 999 4 6
6 3 4 999 2
999 999 999 2 6

Dept. of CSE, Vemana IT 2

ADA Lab Manual (BCSL404)

Cost of Spanning Tree = 11

Edges of Spanning Tree
2 -> 3
4 -> 5
2 -> 4
1 -> 2

Run 2:

Enter the number of vertices: 4

Enter the cost adjacency matrix (use 0 for no edge):
999 5 7 999 2
5 999 999 6 3
7 999 999 4 4
999 6 4 999 5
Spanning Tree does NOT exist (Graph is disconnected)

2. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given
connected undirected graph using Prim’s algorithm.

Dept. of CSE, Vemana IT 3

ADA Lab Manual (BCSL404)

PROGRAM:
#include <stdio.h>
#define INF 999 // Representing no edge
#define MAX_VERTICES 11 // Maximum number of vertices
// DFS Function to Check Connectivity
void dfs(int cost[MAX_VERTICES][MAX_VERTICES], int n, int visited[], int node) {
visited[node] = 1;
for (inti = 1; i<= n; i++) {
if (cost[node][i] != INF && !visited[i]) { // If connected and not visited
dfs(cost, n, visited, i);
}
}
}
// Function to Check if the Graph is Connected
intisConnected(int cost[MAX_VERTICES][MAX_VERTICES], int n) {
int visited[MAX_VERTICES] = {0}; // All nodes initially unvisited
dfs(cost, n, visited, 1); // Start DFS from vertex 1
// Check if all nodes were visited
for (inti = 1; i<= n; i++) {
if (!visited[i]) {
return 0; // Graph is disconnected
}
}
return 1; // Graph is connected
}
// Prim’s Algorithm to find MST
void prims(int cost[MAX_VERTICES][MAX_VERTICES], int n) {
int selected[MAX_VERTICES] = {0}; // Track selected vertices
int edges = 0, min, u, v, totalCost = 0;
selected[1] = 1; // Start with first vertex (1)
printf("\nThe Minimum Spanning Tree (MST) edges are:\n");
while (edges < n - 1) {
min = INF;
u = v = -1;

// Find the minimum weight edge

for (inti = 1; i<= n; i++) {
if (selected[i]) { // Only consider already selected vertices
for (int j = 1; j <= n; j++) {
if (!selected[j] && cost[i][j] < min) { // Edge to unvisited vertex
min = cost[i][j];
u = i;
v = j;
}
}
}
}

// If no valid edge is found, break (Graph is disconnected)

if (u == -1 || v == -1) {

Dept. of CSE, Vemana IT 4

ADA Lab Manual (BCSL404)

break;
}

// Select the new vertex and print the selected edge

selected[v] = 1;
printf("%d -> %d with cost %d\n", u, v, min);
totalCost += min;
edges++;
}

// Check if MST was formed correctly

if (edges != n - 1) {
printf("\n Spanning Tree does NOT exist (Graph is disconnected) \n");
} else {
printf("\n Total Cost of Minimum Spanning Tree: %d\n", totalCost);
}
}

intmain() {
int cost[MAX_VERTICES][MAX_VERTICES], n;
printf("\nEnter the number of vertices: ");
scanf("%d", &n);
printf("\nEnter the cost adjacency matrix (use 0 for no edge):\n");
for (inti = 1; i<= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0 &&i != j)
cost[i][j] = INF; // Replace 0 with INF except diagonal
}
}
// Check if graph is connected before running Prim’s Algorithm
if (!isConnected(cost, n)) {
printf("\n Spanning Tree does NOT exist (Graph is disconnected) \n");
return 0; // Exit early
}
prims(cost, n); // Run Prim’s algorithm
return 0;
}

OUTPUT:
RUN 1:
Enter the number of vertices: 5

Enter the cost adjacency matrix (use 0 for no edge):

999 5 7 999 2
5 999 999 6 3
7 999 999 4 4
999 6 4 999 6
2 3 4 5 999

The Minimum Spanning Tree (MST) edges are:

Dept. of CSE, Vemana IT 5

ADA Lab Manual (BCSL404)

1 -> 5 with cost 2

5 -> 2 with cost 3
5 -> 3 with cost 4
3 -> 4 with cost 4

Total Cost of Minimum Spanning Tree: 13

RUN 2:

Enter the number of vertices: 4

Enter the cost adjacency matrix (use 0 for no edge):
999 5 7 999 2
5 999 999 6 3
7 999 999 4 4
999 6 4 999 5
Spanning Tree does NOT exist (Graph is disconnected)

3A. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using
Floyd’s algorithm.

PROGRAM:

Dept. of CSE, Vemana IT 6

ADA Lab Manual (BCSL404)

#include<stdio.h>
#include<conio.h>
#define INF 999
intmin(inta,int b)
{
return(a<b)?a:b;
}
void floyd(int p[][10],int n)
{
inti,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
void main()
{
inta[10][10],n,i,j;
printf("\nEnter the n value:");
scanf("%d",&n);
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
floyd(a,n);
printf("\nShortest path matrix\n");
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
printf("%d ",a[i][j]);
printf("\n");
}
getch();
}

OUTPUT:

Enter the n value:4

Enter the graph data:

0 999 3 999
2 0 999 999
999 7 0 1
6 999 999 0
Shortest path matrix
0 10 3 4
2056
7701
6 16 9 0

Dept. of CSE, Vemana IT 7

ADA Lab Manual (BCSL404)

3B. Design and implement C/C++ Program to find the transitive closure using Warshal’s
algorithm.
PROGRAM:
#include<stdio.h>
void warsh(int p[][10],int n)
{
inti,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
p[i][j]=p[i][j] || p[i][k] && p[k][j];
}
intmain()
{
inta[10][10],n,i,j;
printf("\nEnter the n value:");
scanf("%d",&n);
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
warsh(a,n);
printf("\nResultant path matrix\n");
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
printf("%d ",a[i][j]);
printf("\n");
}
return 0;
}
OUTPUT:
Enter the n value:4

Enter the graph data:

0100
0001
0000
1010

Resultant path matrix

1111
1111
0000
1111

4. Design and implement C/C++ Program to find shortest paths from a given vertex in a
weighted connected graph to other vertices using Dijkstra’s algorithm.

Dept. of CSE, Vemana IT 8

ADA Lab Manual (BCSL404)

PROGRAM:

#include<stdio.h>
#define INF 999
void dijkstra(int c[10][10],intn,ints,int d[10])
{
intv[10],min,u,i,j;
for(i=1; i<=n; i++)
{
d[i]=c[s][i];
v[i]=0;
}
v[s]=1;
for(i=1; i<=n; i++)
{
min=INF;
for(j=1; j<=n; j++)
if(v[j]==0 && d[j]<min)
{
min=d[j];
u=j;
}
v[u]=1;
for(j=1; j<=n; j++)
if(v[j]==0 && (d[u]+c[u][j])<d[j])
d[j]=d[u]+c[u][j];
}
}
intmain()
{
int c[10][10],d[10],i,j,s,sum,n;
printf("\nEnter n value:");
scanf("%d",&n);
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&c[i][j]);
printf("\nEnter the souce node:");
scanf("%d",&s);
dijkstra(c,n,s,d);
for(i=1; i<=n; i++)
printf("\nShortest distance from %d to %d is %d",s,i,d[i]);
return 0;
}

OUTPUT:
Enter n value:5

Dept. of CSE, Vemana IT 9

ADA Lab Manual (BCSL404)

Enter the graph data:

999 3 999 7 999
3 999 4 2 999
999 4 999 5 6
7 2 5 999 4
999 999 6 4 999

Enter the souce node:1

Shortest distance from 1 to 1 is 999

Shortest distance from 1 to 2 is 3
Shortest distance from 1 to 3 is 7
Shortest distance from 1 to 4 is 5
Shortest distance from 1 to 5 is 9

5. Design and implement C/C++ Program to obtain the Topological ordering of vertices in a
given digraph.

PROGRAM:

Dept. of CSE, Vemana IT 10

ADA Lab Manual (BCSL404)

#include<stdio.h>
#include<conio.h>
inttemp[10],k=0;
void sort(int a[][10],int id[],int n)
{
inti,j;
for(i=1; i<=n; i++)
{
if(id[i]==0)
{
id[i]=-1;
temp[++k]=i;
for(j=1; j<=n; j++)
{
if(a[i][j]==1 && id[j]!=-1)
id[j]--;
}
i=0;
}
}
}
void main()
{
int a[10][10],id[10],n,i,j;
printf("\nEnter the n value:");
scanf("%d",&n);
for(i=1; i<=n; i++)
id[i]=0;
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
id[j]++;
}
sort(a,id,n);
if(k!=n)
printf("\nTopological ordering not possible");
else
{
printf("\nTopological ordering is:");
for(i=1; i<=k; i++)
printf("%d ",temp[i]);
}
getch();
}

OUTPUT:

Dept. of CSE, Vemana IT 11

ADA Lab Manual (BCSL404)

Run 1:
Enter the n value:6
Enter the graph data:
001100
000110
000101
000001
000001
000000
Topological ordering is: 1 2 3 4 5 6

Run 2:
Enter the n value:4

Enter the graph data:

1432
5421
5342
4123
Topological ordering not possible

6. Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
Programming method.

PROGRAM:

Dept. of CSE, Vemana IT 12

ADA Lab Manual (BCSL404)

#include<stdio.h>
int w[10],p[10],n;
intmax(inta,int b)
{
return a>b?a:b;
}
intknap(inti,int m)
{
if(i==n) return w[i]>m?0:p[i];
if(w[i]>m) return knap(i+1,m);
return max(knap(i+1,m),knap(i+1,m-w[i])+p[i]);
}
intmain()
{
intm,i,max_profit;
printf("\nEnter the no. of objects:");
scanf("%d",&n);
printf("\nEnter the knapsack capacity:");
scanf("%d",&m);
printf("\nEnter profit followed by weight:\n");
for(i=1; i<=n; i++)
scanf("%d %d",&p[i],&w[i]);
max_profit=knap(1,m);
printf("\nMax profit=%d",max_profit);
return 0;
}

OUTPUT:
Enter the no. of objects:4

Enter the knapsack capacity:5

Enter profit followed by weight:

12 3
43 5
45 2
55 3

Max profit=100

7. Design and implement C/C++ Program to solve discrete Knapsack and continuous
Knapsack problems using greedy approximation method.
PROGRAM:

Dept. of CSE, Vemana IT 13

ADA Lab Manual (BCSL404)

#include <stdio.h>
#define MAX 50
int p[MAX], w[MAX], x[MAX];
double maxprofit;
int n, m, i;
void greedyKnapsack(int n, int w[], int p[], int m)
{
double ratio[MAX];
// Calculate the ratio of profit to weight for each item
for (i = 0; i< n; i++)
{
ratio[i] = (double)p[i] / w[i];
}
// Sort items based on the ratio in non-increasing order
for (i = 0; i< n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (ratio[i] < ratio[j])
{
double temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;

int temp2 = w[i];

w[i] = w[j];
w[j] = temp2;

temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
}
}
}

Dept. of CSE, Vemana IT 14

ADA Lab Manual (BCSL404)

intcurrentWeight = 0;
maxprofit = 0.0;
// Fill the knapsack with items
for (i = 0; i< n; i++)
{
if (currentWeight + w[i] <= m)
{
x[i] = 1; // Item i is selected
currentWeight += w[i];
maxprofit += p[i];
}
else
{
// Fractional part of item i is selected
x[i] = (m - currentWeight) / (double)w[i];
maxprofit += x[i] * p[i];
break;
}
}
printf("Optimal solution for greedy method: %.1f\n", maxprofit);
printf("Solution vector for greedy method: ");
for (i = 0; i< n; i++)
printf("%d\t", x[i]);
}
intmain()
{
printf("Enter the number of objects: ");
scanf("%d", &n);
printf("Enter the objects' weights: ");
for (i = 0; i< n; i++)
scanf("%d", &w[i]);
printf("Enter the objects' profits: ");
for (i = 0; i< n; i++)
scanf("%d", &p[i]);

Dept. of CSE, Vemana IT 15

ADA Lab Manual (BCSL404)

printf("Enter the maximum capacity: ");

scanf("%d", &m);
greedyKnapsack(n, w, p, m);
return 0;
}

OUTPUT:
Enter the number of objects: 4
Enter the objects' weights: 56 78 98 78
Enter the objects' profits: 23 45 76 78
Enter the maximum capacity: 100
Optimal solution for greedy method: 78.0
Solution vector for greedy method: 1 0 0 0

8. Design and implement C/C++ 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.
PROGRAM:

Dept. of CSE, Vemana IT 16

ADA Lab Manual (BCSL404)

#include<stdio.h>
#define MAX 10
int s[MAX],x[MAX],d;
void sumofsub(intp,intk,int r)
{
inti;
x[k]=1;
if((p+s[k])==d)
{
for(i=1; i<=k; i++)
if(x[i]==1)
printf("%d ",s[i]);
printf("\n");
}
else if(p+s[k]+s[k+1]<=d)
sumofsub(p+s[k],k+1,r
-s[k]);
if((p + r - s[k]>=d) && (p+s[k+1]<=d))
{
x[k]=0;
sumofsub(p,k+1,r
-s[k]);
}
}
intmain()
{
inti,n,sum=0;
printf("\nEnter the n value:");
scanf("%d",&n);
printf("\nEnter the set in increasing order:");
for(i=1; i<=n; i++)
scanf("%d",&s[i]);
printf("\nEnter the max subset value:");
scanf("%d",&d);

Dept. of CSE, Vemana IT 17

ADA Lab Manual (BCSL404)

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

sum=sum+s[i];
if(sum<d || s[1]>d)
printf("\nNo subset possible");
else
sumofsub(0,1,sum);
return 0;
}
OUTPUT:
Enter the n value:9

Enter the set in increasing order:1 2 3 4 5 6 7 8 9

Enter the max subset value:9

126
135
18
234
27
36
45
9

9. Design and implement C/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.

Dept. of CSE, Vemana IT 18

ADA Lab Manual (BCSL404)

PROGRAM:

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
void selection(int a[], int n) {
inti, j, min, temp;
for (i = 0; i<= n-2; i++) {
min = i;
for (j = i+1; j <= n-1; j++) {
if (a[j] < a[min])
min = j;
}
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
void printArr(int a[], int n) {
inti;
for (i = 0; i< n; i++)
printf("%d ", a[i]);
}
void main() {
inta[10000],n, i;
structtimeval t;
double s, e;
printf("Enter the number of elements\n");
scanf("%d",&n);
// Code to test selection sort starts here
printf("Enter the elements : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Before sorting array elements are \n");
printArr(a,n);

Dept. of CSE, Vemana IT 19

ADA Lab Manual (BCSL404)

selection(a, n);
printf("After sorting array elements are \n");
printArr(a,n);
// Code to test selection sort ends here
/*for(i=0;i<n;i++)
a[i]=rand()%100;*/
gettimeofday(&t,NULL);
s=t.tv_sec+(t.tv_usec/1000000.0);
selection(a, n);
gettimeofday(&t,NULL);
e=t.tv_sec+(t.tv_usec/1000000.0);
printf("\ntime taken to sort %d elements is %lf\n", n, (e-s));
}

OUTPUT:
Enter number of elements: 6000
Time taken to sort 6000 elements: 0.031000 seconds

Enter number of elements: 7000

Time taken to sort 7000 elements: 0.034000 seconds

Enter number of elements: 8000

Time taken to sort 8000 elements: 0.047000 seconds

Enter number of elements: 9000

Time taken to sort 9000 elements: 0.052000 seconds

Enter number of elements: 10000

Time taken to sort 10000 elements: 0.077000 seconds

10. Design and implement C/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.

Dept. of CSE, Vemana IT 20

ADA Lab Manual (BCSL404)

PROGRAM:

#include <stdio.h>
#include<sys/time.h>
#include<stdlib.h>
int partition (inta[], int low, int high)
{
intp,i,j,temp;
p=a[low];
i=low ;
j=high+1;
do
{
do {i++;}while(a[i]<p);
do {j--;}while(a[j]>p);
temp=a[i];
a[i]=a[j];
a[j]=temp;
}while(i<j);
temp=a[i];
a[i]=a[j];
a[j]=temp;
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
void quicksort(int a[], int low, int high)
{
if(low<high)
{
int s=partition(a, low, high);
quicksort(a,low,s-1);
quicksort(a,s+1,high);

Dept. of CSE, Vemana IT 21

ADA Lab Manual (BCSL404)

}
}
void printArr(int a[], int n)
{
inti;
for (i = 0; i< n; i++)
printf("%d ", a[i]);
}
intmain()
{
inta[10000],n, i;
structtimeval t;
double s, e;
printf("Enter the number of elements\n");
scanf("%d",&n);
// code to test merge sort starts here
printf("Enter the elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quicksort(a, 0, n-1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
// code to test merge sort ends here
/* for(i=0;i<n;i++)
a[i]=random()%100;*/
gettimeofday(&t,NULL);
s=t.tv_sec+(t.tv_usec/1000000.0);
quicksort(a, 0, n-1);
gettimeofday(&t,NULL);
e=t.tv_sec+(t.tv_usec/1000000.0);
printf("\ntime taken to sort %d elements is %lf\n", n, (e-s));
return 0;

Dept. of CSE, Vemana IT 22

ADA Lab Manual (BCSL404)

}
OUTPUT:
Enter number of elements: 10000
Time taken to sort 10000 elements: 0.0000 seconds
Enter number of elements: 20000
Time taken to sort 20000 elements: 0.015000 seconds

Enter number of elements: 30000

Time taken to sort 30000 elements: 0.011000 seconds

Enter number of elements: 35000

Time taken to sort 35000 elements: 0.003000 seconds

Enter number of elements: 50000

Time taken to sort 50000 elements: 0.015000 seconds

11. Design and implement C/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.

Dept. of CSE, Vemana IT 23

ADA Lab Manual (BCSL404)

PROGRAM:

#include<stdio.h>
#include<sys/time.h>
#include<stdlib.h>
void merge (inta[], int low, int mid, int high)
{
intresarr[10000],i, j, k, m;
i=low ;
j=mid+1;
k=low;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
resarr[k++]=a[i++];
else
resarr[k++]=a[j++];
}
while(i<=mid)
resarr[k++]=a[i++];
while(j<=high)
resarr[k++]=a[j++];
for(m=low;m<=high;m++)
a[m]=resarr[m];
}
void msort(int a[], int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
msort(a,low,mid);
msort(a,mid+1,high);
merge(a,low,mid,high);

Dept. of CSE, Vemana IT 24

ADA Lab Manual (BCSL404)

}
}
void printArr(int a[], int n)
{
inti;
for (i = 0; i< n; i++)
printf("%d ", a[i]);
}
intmain()
{
inta[10000],n, i;
structtimeval t;
double s, e;
printf("Enter the number of elements\n");
scanf("%d",&n);
// code to test merge sort starts here
/* printf("Enter the elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Before sorting array elements are - \n");
printArr(a, n);
msort(a, 0, n-1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);*/
// code to test merge sort ends here
for(i=0;i<n;i++)
a[i]=rand()%100;
gettimeofday(&t,NULL);
s=t.tv_sec+(t.tv_usec/1000000.0);
msort(a, 0, n-1);
gettimeofday(&t,NULL);
e=t.tv_sec+(t.tv_usec/1000000.0);

Dept. of CSE, Vemana IT 25

ADA Lab Manual (BCSL404)

printf("\ntime taken to sort %d elements is %lf\n", n, (e-s));

return 0;
}

OUTPUT:
Enter number of elements: 6000
Time taken to sort 6000 elements: 0.000709 seconds

Enter number of elements: 7000

Time taken to sort 7000 elements: 0.000752 seconds

Enter number of elements: 8000

Time taken to sort 8000 elements: 0.000916 seconds

Enter number of elements: 9000

Time taken to sort 9000 elements: 0.001493 seconds

Enter number of elements: 10000

Time taken to sort 10000 elements: 0.001589 seconds

Enter number of elements: 11000

Time taken to sort 11000 elements: 0.002562 seconds

Enter number of elements: 12000

Time taken to sort 12000 elements: 0.001944 seconds

Enter number of elements: 13000

Time taken to sort 13000 elements: 0.002961 seconds
Enter number of elements: 15000
Time taken to sort 15000 elements: 0.003563 seconds
12. Design and implement C/C++ Program for N Queen’s problem using Backtracking.
PROGRAM:

#include <stdio.h>

Dept. of CSE, Vemana IT 26

ADA Lab Manual (BCSL404)

#include <stdlib.h>
#include <stdbool.h>

// Function to print the solution

void printSolution(int **board, int N)
{
for (inti = 0; i< N; i++)
{
for (int j = 0; j < N; j++)
{
printf("%s ", board[i][j] ? "Q" : "#");
}
printf("\n");
}
}

// Function to check if a queen can be placed on board[row][col]

bool isSafe(int **board, int N, int row, int col)
{
inti, j;

// Check this row on left side

for (i = 0; i< col; i++)
{
if (board[row][i])
{
return false;
}
}

// Check upper diagonal on left side

for (i = row, j = col; i>= 0 && j >= 0; i--, j--)
{
if (board[i][j])

Dept. of CSE, Vemana IT 27

ADA Lab Manual (BCSL404)

{
return false;
}
}

// Check lower diagonal on left side

for (i = row, j = col; j >= 0 &&i< N; i++, j--)
{
if (board[i][j])
{
return false;
}
}

return true;
}

// A recursive utility function to solve N Queen problem

bool solveNQUtil(int **board, int N, int col)
{
// If all queens are placed, then return true
if (col >= N)
{
return true;
}

// Consider this column and try placing this queen in all rows one by one
for (inti = 0; i< N; i++)
{
if (isSafe(board, N, i, col))
{
// Place this queen in board[i][col]
board[i][col] = 1;

Dept. of CSE, Vemana IT 28

ADA Lab Manual (BCSL404)

// Recur to place rest of the queens

if (solveNQUtil(board, N, col + 1))
{
return true;
}

// If placing queen in board[i][col] doesn't lead to a solution,

// then remove queen from board[i][col]
board[i][col] = 0; // BACKTRACK
}
}

// If the queen cannot be placed in any row in this column col, then return false
return false;
}

bool solveNQ(int N)
{
int **board = (int **)malloc(N * sizeof(int *));
for (inti = 0; i< N; i++)
{
board[i] = (int*)malloc(N * sizeof(int));
for (int j = 0; j < N; j++)
{
board[i][j] = 0;
}
}

if (!solveNQUtil(board, N, 0))
{
printf("Solution does not exist\n");
for (inti = 0; i< N; i++)
{
free(board[i]);

Dept. of CSE, Vemana IT 29

ADA Lab Manual (BCSL404)

}
free(board);
return false;
}

printSolution(board, N);
for (inti = 0; i< N; i++) {
free(board[i]);
}
free(board);
return true;
}
intmain()
{
int N;
printf("Enter the number of queens: ");
scanf("%d", &N);
solveNQ(N);
return 0;
}

OUTPUT:
Enter the number of queens: 4
##Q#
Q###
###Q
#Q##

Enter the number of queens: 3

Solution does not exist

Dept. of CSE, Vemana IT 30