VISVESVARAYA TECHNOLOGICAL UNIVERSITY

“Jnana Sangama”, Belgaum-590018

“ANALYSIS AND DESIGN OF ALGORITHMS LAB MANUAL”

[BCSL404]

(IV SEM CSE - CBCS SCHEME)

Prepared By:
Prof. Chethan M S
Assistant Professor
Department of CSE

DEPARTMENT OF INFORMATION SCIENCE & ENGINEERING

SHRIDEVI INSTITUTE OF ENGINEERING & TECHNOLOGY

TUMAKURU-572106
Template for Practical Course and if AEC is a practical Course Annexure-V

Analysis & Design of Algorithms Lab Semester 4

Course Code BCSL404 CIE Marks 50
Teaching Hours/Week (L:T:P: S) 0:0:2:0 SEE Marks 50
Credits 01 Exam Hours 2
Examination type (SEE) Practical
Course objectives:
● To design and implement various algorithms in C/C++ programming using suitable development tools to
address different computational challenges.
● To apply diverse design strategies for effective problem-solving.
● To Measure and compare the performance of different algorithms to determine their efficiency and suitability
for specific tasks.
Sl.No Experiments
1 Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
undirected graph using Kruskal's algorithm.
2 Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
undirected graph using Prim's algorithm.
3 a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's
algorithm.
b. Design and implement C/C++ Program to find the transitive closure using Warshal's
algorithm.
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.
5 Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given
digraph.
6 Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
Programming method.
7 Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack
problems using greedy approximation method.
8 Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n
positive integers whose sum is equal to a given positive integer d.
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.
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.
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.
12 Design and implement C/C++ Program for N Queen's problem using Backtracking.

@# 16032024
Template for Practical Course and if AEC is a practical Course Annexure-V

Course outcomes (Course Skill Set):

At the end of the course the student will be able to:
1. Develop programs to solve computational problems using suitable algorithm design strategy.
2. Compare algorithm design strategies by developing equivalent programs and observing running
times for analysis (Empirical).
3. Make use of suitable integrated development tools to develop programs
4. Choose appropriate algorithm design techniques to develop solution to the computational and
complex problems.
5. Demonstrate and present the development of program, its execution and running time(s) and
record the results/inferences.
Assessment Details (both CIE and SEE)
The weightage of Continuous Internal Evaluation (CIE) is 50% and for Semester End Exam (SEE) is 50%.
The minimum passing mark for the CIE is 40% of the maximum marks (20 marks out of 50) and for the
SEE minimum passing mark is 35% of the maximum marks (18 out of 50 marks). A student shall be
deemed to have satisfied the academic requirements and earned the credits allotted to each subject/
course if the student secures a minimum of 40% (40 marks out of 100) in the sum total of the CIE
(Continuous Internal Evaluation) and SEE (Semester End Examination) taken together

Continuous Internal Evaluation (CIE):

CIE marks for the practical course are 50 Marks.
The split-up of CIE marks for record/ journal and test are in the ratio 60:40.
● Each experiment is to be evaluated for conduction with an observation sheet and record write-up.
Rubrics for the evaluation of the journal/write-up for hardware/software experiments are
designed by the faculty who is handling the laboratory session and are made known to students at
the beginning of the practical session.
● Record should contain all the specified experiments in the syllabus and each experiment write-up
will be evaluated for 10 marks.
● Total marks scored by the students are scaled down to 30 marks (60% of maximum marks).
● Weightage to be given for neatness and submission of record/write-up on time.
● Department shall conduct a test of 100 marks after the completion of all the experiments listed in
the syllabus.
● In a test, test write-up, conduction of experiment, acceptable result, and procedural knowledge will
carry a weightage of 60% and the rest 40% for viva-voce.
● The suitable rubrics can be designed to evaluate each student’s performance and learning ability.
● The marks scored shall be scaled down to 20 marks (40% of the maximum marks).
The Sum of scaled-down marks scored in the report write-up/journal and marks of a test is the total CIE
marks scored by the student.

Semester End Evaluation (SEE):

● SEE marks for the practical course are 50 Marks.

@# 16032024
Template for Practical Course and if AEC is a practical Course Annexure-V

● SEE shall be conducted jointly by the two examiners of the same institute, examiners are
appointed by the Head of the Institute.
● The examination schedule and names of examiners are informed to the university before the
conduction of the examination. These practical examinations are to be conducted between the
schedule mentioned in the academic calendar of the University.
● All laboratory experiments are to be included for practical examination.
● (Rubrics) Breakup of marks and the instructions printed on the cover page of the answer script
to be strictly adhered to by the examiners. OR based on the course requirement evaluation
rubrics shall be decided jointly by examiners.
● Students can pick one question (experiment) from the questions lot prepared by the examiners
jointly.
● Evaluation of test write-up/ conduction procedure and result/viva will be conducted jointly by
examiners.
● General rubrics suggested for SEE are mentioned here, writeup-20%, Conduction procedure and
result in -60%, Viva-voce 20% of maximum marks. SEE for practical shall be evaluated for 100 marks
and scored marks shall be scaled down to 50 marks (however, based on course type, rubrics shall be
decided by the examiners)
● Change of experiment is allowed only once and 15% of Marks allotted to the procedure part are to be
made zero.
The minimum duration of SEE is 02 hours

Suggested Learning Resources:

● Virtual Labs (CSE): http://cse01-iiith.vlabs.ac.in/

@# 16032024
Analysis & Design of Algorithms Lab BCSL404

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

#define INF 999

#define MAX 100
int p[MAX], c[MAX][MAX], t[MAX][2];
int find(int v)
{
while (p[v])
v = p[v];
return v;
}
void union1(int i, int j)
{
p[j] = i;
}
void kruskal(int n)
{
int i, j, k, u, v, min, res1, res2, sum = 0;
for (k = 1; k < n; k++)
{
min = INF;
for (i = 1; i < n - 1; i++)
{
for (j = 1; j <= n; j++)
{
if (i == j) continue;
if (c[i][j] < min)
{
u = find(i);
v = find(j);
if (u != v)
{
res1 = i;
res2 = j;
min = c[i][j];
}
}
}
}
union1(res1, find(res2));
t[k][1] = res1;
t[k][2] = res2;
sum = sum + min;

1 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

}
printf("\nCost of spanning tree is=%d", sum);
printf("\nEdgesof spanning tree are:\n");
for (i = 1; i < n; i++)
printf("%d -> %d\n", t[i][1], t[i][2]);
}
int main()
{
int i, j, n;
printf("\nEnter the n value:");
scanf("%d", & n);
for (i = 1; i <= n; i++)
p[i] = 0;
printf("\nEnter the graph data:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", & c[i][j]);
kruskal(n);
return 0;
}

Output:

Enter the n value:5

Enter the graph data:

1 3 4 6 2
1 7 6 9 3
5 2 8 99 45
1 44 66 33 6
12 4 3 2 0

Cost of spanning tree is=11

Edges of spanning tree are:
2 -> 1
1 -> 5
3 -> 2
1 -> 4

2 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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

#include<stdio.h>
#define INF 999
int prim(int c[10][10],int n,int s)
{
int v[10],i,j,sum=0,ver[10],d[10],min,u;
for(i=1; i<=n; i++)
{
ver[i]=s;
d[i]=c[s][i];
v[i]=0;
}
v[s]=1;
for(i=1; i<=n-1; i++)
{
min=INF;
for(j=1; j<=n; j++)
if(v[j]==0 && d[j]<min)
{
min=d[j];
u=j;
}
v[u]=1;
sum=sum+d[u];
printf("\n%d -> %d sum=%d",ver[u],u,sum);
for(j=1; j<=n; j++)
if(v[j]==0 && c[u][j]<d[j])
{
d[j]=c[u][j];
ver[j]=u;
}
}
return sum;
3 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

}
void main()
{
int c[10][10],i,j,res,s,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);
res=prim(c,n,s);
printf("\nCost=%d",res);
getch();
}

Output :
Enter n value: 4

Enter the graph data:

4521
7592
1769
0285

Enter the source node:4

4 -> 1 sum=0
4 -> 2 sum=2
1 -> 3 sum=4
Cost=4

4 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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

#include<stdio.h>
#include<conio.h>
#define INF 999
int min(int a,int b)
{
return(a<b)?a:b;
}
void floyd(int p[][10],int n)
{
int i,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
void main()
{
int a[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");
}
5 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

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

6 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

3b. Design and implement C/C++ Program to find the transitive closure using Warshal's
algorithm.
#include<stdio.h>
void warsh(int p[][10],int n)
{
int i,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
p[i][j]=p[i][j] || p[i][k] && p[k][j];
}
int main()
{
int a[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;
}

7 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

Output:
Enter the n value:4

Enter the graph data:

0100
0001
0000
1010

Resultant path matrix

1111
1111
0000
1111

8 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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.
#include<stdio.h>
#define INF 999
void dijkstra(int c[10][10],int n,int s,int d[10])
{
int v[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];
}
}
int main()
{
int c[10][10],d[10],i,j,s,sum,n;
printf("\nEnter n value:");
scanf("%d",&n);
printf("\nEnter the graph data:\n");
9 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

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:4

Enter the graph data:

444 767 987 12
999 87 56 45
1 0 999 678
444 678 235 0

Enter the source node:1

Shortest distance from 1 to 1 is 444

Shortest distance from 1 to 2 is 247
Shortest distance from 1 to 3 is 247
Shortest distance from 1 to 4 is 12

10 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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

#include<stdio.h>
#include<conio.h>
int temp[10],k=0;
void sort(int a[][10],int id[],int n)
{
int i,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++)
11 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

{
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:
********************************OUTPUT 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

12 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

**********************************OUTPUT 2********************************

Enter the n value:4

Enter the graph data:

1432
5421
5342
4123

Topological ordering not possible

13 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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

#include<stdio.h>
int w[10],p[10],n;
int max(int a,int b)
{
return a>b?a:b;
}
int knap(int i,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]);
}
int main()
{
int m,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;
}

14 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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

15 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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

#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];
16 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

p[j] = temp2;
}
}
}
int currentWeight = 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]);
}
int main()
{
printf("Enter the number of objects: ");
scanf("%d", &n);
printf("Enter the objects' weights: ");
for (i = 0; i < n; i++)
17 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

scanf("%d", &w[i]);
printf("Enter the objects' profits: ");
for (i = 0; i < n; i++)
scanf("%d", &p[i]);
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

18 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

8. Design and implement C/C++ Program to find a subset of a given set S = {sl s2,.....,sn}
of n positive integers whose sum is equal to a given positive integer d.

#include<stdio.h>
#define MAX 10
int s[MAX],x[MAX],d;
void sumofsub(int p,int k,int r)
{
int i;
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]);
}
}
int main()
{
int i,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]);
19 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

printf("\nEnter the max subset value:");

scanf("%d",&d);
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

20 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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.

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

void selsort(int a[], int n)

{
int i, j, small, pos, temp;
for(j = 0; j < n - 1; j++)
{
small = a[j];
pos = j;
for(i = j + 1; i < n; i++)
{
if(a[i] < small)
{
small = a[i];
pos = i;
}
}
temp = a[j];
a[j] = small;
a[pos] = temp;
}
}

int main()
{
int a[10], i, n;
struct timespec start, end;
21 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

double dura;

printf("\nEnter the n value:");

scanf("%d", &n);
printf("\nEnter the array:");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);

clock_gettime(CLOCK_MONOTONIC, &start);
selsort(a, n);
clock_gettime(CLOCK_MONOTONIC, &end);

dura = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("\nTime taken is: %lf seconds", dura);

printf("\nSorted array is:");
for(i = 0; i < n; i++)
printf("%d ", a[i]);

return 0;
}

Output:

Enter the n value:5

Enter the array:12 7 5 15 4

Time taken is: 0.000002 seconds

Sorted array is: 4 5 7 12 15

22 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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.

#include<stdio.h>
int partition(int a[25],intlow,int high)
{
intp,i,j,temp;
p=a[low];
i=low+1;
j=high;
while(low<high)
{
while(a[i]<=p&&i<high)
i++;
while(a[j]>p)
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
}
return j;
23 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

}
void sort(int a[],intlow,int high)
{
if(low<high)
{
int s=partition(a,low,high);
sort(a,low,s-1);
sort(a,s+1,high);
}
}
int main()
{
inti, n, a[25];
printf("Enter the array size: ");
scanf("%d",&n);
printf("Enter array elements:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,0,n-1);
printf("Order of Sorted elements: ");
for(i=0;i<n;i++)
printf(" %d",a[i]);
return 0;
}

Output:
Enter the array size: 4
Enter array elements:
42
63
71
2
Order of Sorted elements: 2 42 63 71

24 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

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.

#include<stdio.h>
void merge(int *array ,intlow,intmid,int high)
{
intresarray[25];
inti=low;
int k=low;
int j=mid+1;

while(i<=mid && j<=high)

{
if(array[i]<array[j])
{
resarray[k]=array[i];
i++;
k++;
}
else
{
resarray[k]=array[j];
j++;
k++;
}
}
while(i<=mid)
resarray[k++]=array[i++];
while(j<=high)
resarray[k++]=array[j++];
for(int m=low;m<=high;m++)
25 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

array[m]=resarray[m];
}
void sort(int *array,intlow,int high)
{
if(low<high)
{
int mid=(low+high)/2;
sort(array,low,mid);
sort(array,mid+1,high);
merge(array,low,mid,high);
}
}
int main()
{
int n;
printf("Enter the size: ");
scanf("%d", &n);
int array[n];
printf("Enter the elements of array: ");
for (inti = 0; i< n; i++)
{
scanf("%d", &array[i]);
}
sort(array, 0, n - 1);
printf("The sorted array is: ");
for (inti = 0; i< n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
return 0;
}

26 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

Output:

Enter the size: 5

Enter the elements of array: 7

The sorted array is: 2 3 4 7 8

27 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

12.Design and implement C/C++ Program for N Queen's problem using Backtracking.

#include<stdio.h>
#include<conio.h>
#include<math.h>
int a[30],count=0;
int place(int pos)
{
int i;
for (i=1;i<pos;i++)
{
if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
return 0;
}
return 1;
}
void print_sol(int n)
{
int i,j;
count++;
printf("\n\nSolution #%d:\n",count);
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
if(a[i]==j)
printf("Q\t");
else printf("*\t");
}
printf("\n");
}
}

28 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

void queen(int n)
{
int k=1;
a[k]=0;
while(k!=0)
{
a[k]=a[k]+1;
while((a[k]<=n)&&!place(k))
a[k]++;
if(a[k]<=n)
{
if(k==n)
print_sol(n);
else
{
k++;
a[k]=0;
}
}
else k--;
}
}

void main()
{
int i,n;
clrscr();
printf("Enter the number of Queens\n");
scanf("%d",&n);
queen(n);
printf("\nTotal solutions=%d",count);
getch();
}

29 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

Output:

Enter the number of Queens : 4

Solution 1:

1 2 3 4
1 - Q - -

2 - - - Q

3 Q - - -

4 - - Q -

Solution 2:

1 2 3 4
1 - - Q -

2 Q - - -

3 - - - Q

4 - Q - -

30 Dept of ISE, SIET

Analysis & Design of Algorithms Lab BCSL404

Program 2 N-Queens
#include<stdio.h>
#include<math.h>

int board[20],count;

int main()
{
int n,i,j;
void queen(int row,int n);
printf(" - N Queens Problem Using Backtracking -");
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
queen(1,n);
return 0;
}

//function for printing the solution

void print(int n)
{
int i,j;
printf("\n\nSolution %d:\n\n",++count);
for(i=1;i<=n;++i)
printf("\t%d",i);
for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j) //for nxn board
{
if(board[i]==j)
printf("\tQ"); //queen at i,j position
else
printf("\t-"); //empty slot
31 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

}
}
}

/*funtion to check conflicts

If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row,int column)
{
int i;
for(i=1;i<=row-1;++i)
{
//checking column and digonal conflicts
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}
return 1; //no conflicts
}

//function to check for proper positioning of queen

void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column; //no conflicts so place queen
if(row==n) //dead end
print(n); //printing the board configuration
else //try queen with next position
queen(row+1,n);
32 Dept of ISE, SIET
Analysis & Design of Algorithms Lab BCSL404

}
}
}

Output:
Solution 1:

1 2 3 4
1 - Q - -

2 - - - Q

3 Q - - -

4 - - Q -

Solution 2:

1 2 3 4
1 - - Q -

2 Q - - -

3 - - - Q

4 - Q - -

33 Dept of ISE, SIET