react lab manual for sixth semester BE course lab manual

React lab manual

1. ALVA’S INSTITUTE OF ENGINEERING & TECHNOLOGY
(A Unit of Alva’s Education Foundation)
Shobhavana Campus, Mijar, Moodbidri, D.K–574225
(Accredited by NAAC with A+ Grade)
Affiliated to VTU Belagavi, Approved by AICTE, NewDelhi
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
(Accredited by NBA, New Delhi)

ANALYSIS AND DESIGN OF
ALGORITHMS LABORATORY

Lab Manual
(Subject Code: BCSL404)
[As per Choice Based Credit System (CBCS)scheme]
SEMESTER–IV

PREPARED BY,
Mr. H Harshavardhan (Sr. Asst Professor)
Mrs. Deepika Kamath ( Sr. Asst Professor)
APPROVED BY,
Dr. Manjunath Kotari (Professor and Head of CSE)

5. COURSE OUTCOMES
Co
numbers
Course outcomes

BCSL404.1
Implement graph related algorithms to
analyses the performance.
BCSL404.2
Design algorithms using brute
greedy, dynamic programming, divide
and conquer approaches to analyses
the performance.

BCSL404.3
Implement algorithms such as sorting,
combinatorial

BCSL404.4
Apply and compare the performance
of algorithms that use back tracking
CO-PO/CO
CO No.
PO1 PO
2
PO
3

BCSL404.1
2 2 2
BCSL404.2
2 2 2
BCSL404.3 2 2 1

BCSL404.4
2 2 2
AVG 2 1.6 1.4



COURSE OUTCOMES (CO’S)
Course outcomes Blooms
level
Implement graph related algorithms to
analyses the performance.


Apply(L2)
Design algorithms using brute-force,
greedy, dynamic programming, divide
conquer approaches to analyses
the performance.

Apply(L3)
Implement algorithms such as sorting,
combinatorial to analyses the
performance.


Apply(L3)
Apply and compare the performance
of algorithms that use back tracking
principle.


Apply(L3)




PO/CO-PSO MAPPING MATRIX
PO
4
PO
5
PO
6
PO
7
PO
8
PO
9
PO
10
PO
11
2 2 2 2
2 2 2 2 2
1 2 1 2 1
2 2 1 2 1
1.4 1.4 1 2 1
Blooms Target
level
Apply(L2)

2
Apply(L3) 2
Apply(L3)

2
Apply(L3)

2
PSO MAPPING MATRIX
PO
12
PS
O1
PS
O2
PS
O3
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2

6. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 1

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 connect e dun directed 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 too there vertices using Dijkstra's
algorithm.
5 Design and implement C/C++ Program to obtain the Topological order in go f
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 sub set of a given set
S={sl,s2,.....,sn} of n positive integers who sesumis equal to a given positive
integer.
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

7. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 2

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.
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 50Marks.
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 for10marks.
● 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- upon time.
● Department shall conduct attest 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

8. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 3

total CIE marks scored by the student.
Semester End Evaluation(SEE):
● SEE marks for the practical course are 50Marks.
● 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/

9. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 4

PROGRAM 1
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of
a given connected undirected graph using Kruskal's algorithm.
#include <stdio.h>
#include <stdlib.h>

int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];

// Function prototypes
int find(int);
int uni(int, int);

void main() {
printf("\n\n\tImplementation of Kruskal's Algorithm\n\n");

// Input the number of vertices
printf("\nEnter the number of vertices: ");
scanf("%d", &n);

// Input the cost adjacency matrix
printf("\nEnter the cost adjacency matrix:\n");
for (i = 1; i<= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0) // Replace 0 with a high value (999) to indicate no
edge
cost[i][j] = 999;
}
}

printf("\nThe edges of the Minimum Cost Spanning Tree are:\n");

// Loop to find the MST using Kruskal's algorithm
while (ne < n) {
min = 999; // Reset min value for each iteration

// Find the minimum cost edge
for (i = 1; i<= n; i++) {
for (j = 1; j <= n; j++) {
if (cost[i][j] < min) {

10. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 5

min = cost[i][j];
a = u = i;
b = v = j;
}
}
}

u = find(u); // Find root parent of vertex u
v = find(v); // Find root parent of vertex v

// If adding this edge does not create a cycle, include it in MST
if (uni(u, v)) {
printf("\n%d Edge (%d, %d) = %d\n", ne++, a, b, min);
mincost += min; // Add cost of this edge to total minimum cost
}

// Mark the edge as used by setting cost to 999
cost[a][b] = cost[b][a] = 999;
}

// Print the final minimum cost
printf("\n\tMinimum Cost = %d\n", mincost);
}

// Function to find the root parent of a node
int find(int i) {
while (parent[i])
i = parent[i];
return i;
}

// Function to perform union operation
int uni(int i, int j) {
if (i != j) {
parent[j] = i;
return 1;
}
return 0;
}

11. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 6


***********OUTPUT***********

Enter the no. of vertices
4

Enter the cost adjacency matrix

The edges of Minimum Cost Spanning Tree are

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

Minimum cost = 7

12. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 7

PROGRAM 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>
int a, b, u, v, n, i, j, ne = 1;
int visited[10] = {0}, min, mincost = 0, cost[10][10];

void main() {
printf("\n Enter the number of nodes: ");
scanf("%d", &n);
printf("\n Enter the adjacency matrix:\n");
for (i = 1; i<= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = 999; // Use a high value to represent no connection
}
}

visited[1] = 1; // Start from the first node
printf("\n");

while (ne < n) { // Loop until we include n-1 edges in the MST
for (i = 1, min = 999; i<= n; i++) {
for (j = 1; j <= n; j++) {
if (cost[i][j] < min) { // Find the minimum cost edge
if (visited[i] != 0) { // Ensure one end is in the tree
min = cost[i][j];
a = u = i;
b = v = j;
}
}
}
}

if (visited[u] == 0 || visited[v] == 0) { // Check if we can add this edge
printf("\n Edge %d:(%d %d) cost: %d", ne++, a, b, min);
mincost += min;
visited[b] = 1;
}

13. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 8


cost[a][b] = cost[b][a] = 999; // Mark the edge as used
}

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

***********OUTPUT***********

Enter the number of nodes: 4

Enter the adjacency matrix:
0 1 3 0
1 0 1 5
3 1 0 2
0 5 2 0

Edge 1:(1 2) cost: 1
Edge 2:(2 3) cost: 1
Edge 3:(3 4) cost: 2

Minimum cost = 4

14. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 9

PROGRAM 3

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

#include <stdio.h>

void main()
{
int n, i, j, k;
int Floyd[10][10], Cost[10][10];

printf("\n*tPROGRAM TO IMPLEMENT FLOYD'S ALGORITHMt* \n");

// Input number of vertices
printf("\nEnter the number of vertices: ");
scanf("%d", &n);

// Input Cost adjacency matrix
printf("\nEnter the Cost adjacency Matrix:\n");
for(i = 0; i< n; i++)
for(j = 0; j < n; j++)
scanf("%d", &Cost[i][j]);

// Display input graph
printf("\nInput Graph:\n");
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d\t", Cost[i][j]);
}
printf("\n");
}
printf("\n");

// Initialize the Floyd matrix
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
Floyd[i][j] = Cost[i][j];

15. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 10

}
}

// Apply Floyd's algorithm for all pairs shortest path
for(k = 0; k < n; k++)
{
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
if(Floyd[i][j] > (Floyd[i][k] + Floyd[k][j]))
Floyd[i][j] = (Floyd[i][k] + Floyd[k][j]);
}
}
}

// Display All Pair Shortest Path Matrix
printf("\nAll Pair Shortest Path Matrix:\n");
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d\t", Floyd[i][j]);
}
printf("\n");
}
printf("\n");
}




**********OUTPUT***********

Enter the number of vertices
4

Enter the Cost adjacency Matrix
0 3 999 7
8 0 2 999
5 999 0 1
2 999 999 0

16. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 11


Input Graph
0 3 999 7
8 0 2 999
5 999 0 1
2 999 999 0


All Pair Shortest Path Matrix
0 3 5 6
5 0 2 3
3 6 0 1
2 5 7 0

17. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 12

B. Design and implement C/C++ Program to find the transitive closure using
Warshall's algorithm.

#include <stdio.h>

void main()
{
int n, i, j, k;
int path[10][10], adj[10][10];

printf("\n*tPROGRAM TO IMPLEMENT WARSHALL'S
ALGORITHMt*\n");

// Input the number of vertices
printf("\nEnter the number of vertices: ");
scanf("%d", &n);

// Input the adjacency matrix
printf("\nEnter the adjacency Matrix:\n");
for(i = 0; i< n; i++)
for(j = 0; j < n; j++)
scanf("%d", &adj[i][j]);

// Display the input graph (adjacency matrix)
printf("\nInput Graph (Adjacency Matrix):\n");
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d\t", adj[i][j]);
}
printf("\n");
}
printf("\n");

// Initialize the path matrix with the adjacency matrix

for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
path[i][j] = adj[i][j];

18. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 13

}
}

// Apply Warshall's algorithm to find the transitive closure

for(k = 0; k < n; k++)
{
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
if(path[i][j] || (path[i][k] && path[k][j]))
path[i][j] = 1;
}
}
}

// Display the path matrix (Transitive closure)

printf("\nPath Matrix / Transitive Closure:\n");
for(i = 0; i< n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d\t", path[i][j]);
}
printf("\n");
}
printf("\n");
}

********OUTPUT**********

Enter the number of vertices
4

Enter the adjacency Matrix
0 1 0 1
0 0 1 1
0 0 0 0
0 0 1 0

19. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 14

Input Graph
0 1 0 1
0 0 1 1
0 0 0 0
0 0 1 0

Path Matrix / Transitive closure
1 1 1 1
0 1 1 1
0 0 0 0
0 0 1 0

20. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 15

PROGRAM 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>
#include <limits.h>
#include <stdlib.h>

#define INFINITY INT_MAX

// Dijkstra's Algorithm function
void dij(int n, int v, int cost[10][10], int dist[10]) {
int i, u, count, w, flag[10], min;

// Initialize the distance array and the flag array
for(i = 0; i< n; i++) {
flag[i] = 0; // No node is visited initially
dist[i] = cost[v][i]; // Distance from the source node to each node
}
count = 1;
flag[v] = 1; // Mark the source node as visited

// Main loop of Dijkstra's algorithm
while(count < n) {
min = INFINITY;

// Find the node with the minimum distance
for(w = 0; w < n; w++)
if(dist[w] < min && !flag[w]) {
min = dist[w];
u = w;
}

// Mark the node as visited
flag[u] = 1;
count++;

// Update the distances of the neighbors of the chosen node
for(w = 0; w < n; w++)
if((dist[u] + cost[u][w] <dist[w]) && !flag[w])

21. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 16

dist[w] = dist[u] + cost[u][w];
}
}

int main() {
int n, v, i, j, cost[10][10], dist[10];

// Input the number of nodes
printf("\nEnter the number of nodes: ");
scanf("%d", &n);

// Input the cost matrix
printf("\nEnter the cost matrix:\n");
for(i = 0; i< n; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
if(cost[i][j] == 0 &&i != j) // If no path exists, set it to infinity
cost[i][j] = INFINITY;
}
}

// Input the source node
printf("\nEnter the source node: ");
scanf("%d", &v);
v--; // Adjusting for 0-indexed array

// Call Dijkstra's algorithm
dij(n, v, cost, dist);

// Output the shortest paths from the source node
printf("\nShortest paths from node %d:\n", v + 1);
for(i = 0; i< n; i++) {
if(i != v) // Skip the source node itself
printf("%d -> %d, cost = %d\n", v + 1, i + 1, dist[i]);
}

return 0;
}

22. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 17

********OUTPUT********
Enter the number of nodes: 5

Enter the cost matrix:
0 10 0 0 5
10 0 20 0 0
0 20 0 10 0
0 0 10 0 10
5 0 0 10 0

Enter the source node: 1

Shortest paths from node 1:
1 -> 2, cost = 10
1 -> 3, cost = 20
1 -> 4, cost = 15
1 -> 5, cost = 5

23. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 18

PROGRAM 5

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

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

int a[10][10], n, indegre[10]; // n- vertices

void find_indegre() // col sum of matrix
{
int j, i, sum; // row and column
for (j = 0; j < n; j++)
{
sum = 0;
for (i = 0; i< n; i++)
sum += a[i][j];
indegre[j] = sum;
}
}

void topology()
{
int i, u, v, t[10], s[10], top = -1, k = 0; // i to process the graph, u & v vertices,
t : to final result store.

find_indegre();
for (i = 0; i< n; i++)
{
if (indegre[i] == 0)
s[++top] = i; // add to stack whose indegre is zero
}
while (top != -1)
{
u = s[top--]; // pop and store in u. First vertex removed whose indegre is
Zero.
// First node removed will be the first in the topological ordering.

t[k++] = u; // remove u
for (v = 0; v < n; v++)
{

24. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 19

if (a[u][v] == 1) // check if there is an edge from u to v
{
indegre[v]--; // decrement the indegre after removing the edge
if (indegre[v] == 0)
s[++top] = v; // if indegre 0 push to stack.
}
}
}
printf("The topological Sequence is:\n"); // print the topological 1D array
for (i = 0; i< n; i++)
printf("%d ", t[i]);
}

void main()
{
int i, j;

printf("Enter number of jobs:");
scanf("%d", &n);
printf("\nEnter the adjacency matrix:\n");
for (i = 0; i< n; i++)
{
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
}
topology();
}

*******OUTPUT***********
Enter number of jobs: 6

Enter the adjacency matrix:
0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 1 0 0
0 0 0 0 0 0

The topological Sequence is:
0 1 2 4 3 5

25. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 20

PROGRAM 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], v[10][10], n, i, j, cap, x[10] = {0};

int max(int i, int j) {
return ((i > j) ? i : j);
}

int knap(int i, int j) {
int value;
if (v[i][j] < 0) {
if (j < w[i])
value = knap(i - 1, j);
else
value = max(knap(i - 1, j), p[i] + knap(i - 1, j - w[i]));
v[i][j] = value;
}
return (v[i][j]);
}

void main() {
int profit, count = 0;

// Input number of items
printf("\nEnter the number of elements\n");
scanf("%d", &n);

// Input the profit and weights for each item
printf("Enter the profit and weights of the elements\n");
for (i = 1; i <= n; i++) {
printf("For item no %d\n", i);
scanf("%d%d", &p[i], &w[i]);
}

// Input the knapsack capacity
printf("\nEnter the capacity \n");
scanf("%d", &cap);

26. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 21


// Initialize the DP table v[][]
for (i = 0; i <= n; i++) {
for (j = 0; j <= cap; j++) {
if ((i == 0) || (j == 0))
v[i][j] = 0;
else
v[i][j] = -1;
}
}

// Calculate the maximum profit
profit = knap(n, cap);

// Trace the items included in the knapsack
i = n;
j = cap;
while (j != 0 && i != 0) {
if (v[i][j] != v[i - 1][j]) {
x[i] = 1; // Item i is included
j = j - w[i];
}
i--;
}

// Output the items that are included
printf("Items included are\n");
printf("Sl.no\tweight\tprofit\n");
for (i = 1; i <= n; i++) {
if (x[i]) {
printf("%d\t%d\t%d\n", ++count, w[i], p[i]);
}
}

// Output the total profit
printf("Total profit = %d\n", profit);
}

27. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 22

*******OUTPUT********
Enter the number of elements
4
Enter the profit and weights of the elements
For item no 1
10 2
For item no 2
20 3
For item no 3
30 4
For item no 4
40 5

Enter the capacity
5
Items included are
Sl.no weight profit
1 3 20
2 2 10
Total profit = 30

28. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 23

PROGRAM 7

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

#include <stdio.h>

int main() {
float weight[50], profit[50], ratio[50], Totalvalue = 0.0, temp, capacity,
amount, x[10];
int n, i, j;

// Input the number of items
printf("Enter the number of items : ");
scanf("%d", &n);

// Input the weight and profit for each item
for (i = 0; i < n; i++) {
printf("Enter Weight and Profit for item[%d] :\n", i);
scanf("%f %f", &weight[i], &profit[i]);
}

// Input the capacity of the knapsack
printf("Enter the capacity of knapsack :\n");
scanf("%f", &capacity);

// Calculate the ratio of profit to weight for each item
for (i = 0; i < n; i++) {
ratio[i] = profit[i] / weight[i];
}

// Sort items based on the ratio of profit to weight (greedy approach)
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
if (ratio[i] < ratio[j]) {
// Swap the ratios
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;

// Swap the weights
temp = weight[j];

29. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 24

weight[j] = weight[i];
weight[i] = temp;

// Swap the profits
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}

// Solve the problem using the Greedy Algorithm
printf("Knapsack problems using Greedy Algorithm:\n");
for (i = 0; i < n; i++) {
x[i] = 0.0; // Initialize the solution vector to 0
}

for (i = 0; i < n; i++) {
if (weight[i] > capacity) {
break; // If the item cannot be fully included, stop
} else {
x[i] = 1.0; // Include the entire item
Totalvalue = Totalvalue + profit[i]; // Add the profit to the total value
capacity = capacity - weight[i]; // Update the remaining capacity
}
}

// If there is still capacity left for a fraction of the next item
if (i < n) {
x[i] = capacity / weight[i]; // Take the fraction of the remaining item
Totalvalue = Totalvalue + (ratio[i] * capacity); // Add the fractional profit
to the total value
}

// Output the results
printf("\nThe maximum value is : %f\n", Totalvalue);
printf("Solution vector for greedy method: ");
for (i = 0; i < n; i++) {
printf("%f\t", x[i]); // Print the solution vector (fractional inclusion of each
item)
}

30. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 25

return 0;
}

************OUTPUT**********

Enter the number of items :5
Enter Weight and Profit for item[0] :
2 10
Enter Weight and Profit for item[1] :
3 15
Enter Weight and Profit for item[2] :
4 20
Enter Weight and Profit for item[3] :
5 25
Enter Weight and Profit for item[4] :
3 12
Enter the capacity of knapsack :
10
Knapsack problems using Greedy Algorithm:

The maximum value is :65.000000
Solution vector for greedy method: 1.000000 1.000000 1.000000
0.000000 0.000000

31. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 26

PROGRAM 8

Design and implement C program to find a subset of a given set
S={s1,s2,….sn} of n positive integers whose whose sum is equal to a given
positive integer d.

#include <stdio.h>

int s[10], x[10], d;

void sumofsub(int m, int k, int r);

void main() {
int n, sum = 0;
int i;

// Input the size of the set
printf("\nEnter the size of the set: ");
scanf("%d", &n);

// Input the elements of the set in increasing order
printf("\nEnter the set in increasing order:\n");
for (i = 1; i <= n; i++) {
scanf("%d", &s[i]);
}

// Input the value of d (desired sum)
printf("\nEnter the value of d: \n");
scanf("%d", &d);

// Calculate the sum of the set elements
for (i = 1; i <= n; i++) {
sum = sum + s[i];
}

// Check if the sum of the set elements is less than d or if the smallest element
is greater than d
if (sum < d || s[1] > d) {
printf("\nNo subset possible.\n");
} else {
sumofsub(0, 1, sum); // Call the recursive function to find subsets
}

32. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 27

}

void sumofsub(int m, int k, int r) {
int i = 1;

// Mark the current element as included in the subset
x[k] = 1;

// If the sum of the selected subset equals the desired value d, print the subset
if ((m + s[k]) == d) {
printf("Subset: ");
for (i = 1; i <= k; i++) {
if (x[i] == 1) {
printf("\t%d", s[i]);
}
}
printf("\n");
}
else if (m + s[k] + s[k + 1] <= d) {
// Include the current element and move to the next element
sumofsub(m + s[k], k + 1, r - s[k]);
}

// Backtrack and explore the next possible subset by excluding the current
element
if ((m + r - s[k] >= d) && (m + s[k + 1] <= d)) {
x[k] = 0;
sumofsub(m, k + 1, r - s[k]);
}
}

***********OUTPUT*********
Enter the size of the set: 5

Enter the set in increasing order:
2 4 6 8 10

Enter the value of d: 12
Subset: 2 4 6
Subset: 2 10
Subset: 4 8

33. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 28

PROGRAM 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>

// Function to perform Selection Sort
void SelectionSort(int array[], int n) {
int i, j;
for (i = 0; i < n; i++) {
int min = i;

// Find the minimum element in the unsorted part of the array
for (j = i + 1; j < n; j++) {
if (array[j] < array[min]) {
min = j;
}
}

// Swap the found minimum element with the first element
int temp = array[min];
array[min] = array[i];
array[i] = temp;
}
}

int main() {
int n, a[50000], k;
clock_t st, et;
double ts;

// Input the number of elements to be sorted
printf("\nEnter how many numbers: ");
scanf("%d", &n);

// Generate and display random numbers
printf("\nThe random numbers are:\n");

34. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 29

for (k = 0; k < n; k++) {
a[k] = rand(); // Generate random number
printf("%d\t", a[k]);
}

// Start the clock to measure the sorting time
st = clock();

// Perform the selection sort
SelectionSort(a, n);

// Stop the clock after sorting
et = clock();

// Calculate the time taken in seconds
ts = (double)(et - st) / CLOCKS_PER_SEC;

// Display the sorted numbers
printf("\nSorted numbers are:\n");
for (k = 0; k < n; k++) {
printf("%d\t", a[k]);
}

// Display the time taken to perform the sorting
printf("\nThe time taken is: %e seconds\n", ts);

return 0;
}

******OUTPUT******
Enter how many numbers: 10

The random numbers are:
25592 17357 9193 26756 11809 23331 2938 14934 8521 22047

Sorted numbers are:
2938 9193 11809 14934 17357 22047 23331 25592 26756 8521

The time taken is: 1.321000e-03 seconds

35. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 30

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

// Function to exchange two values
void Exch(int *p, int *q) {
int temp = *p;
*p = *q;
*q = temp;
}

// Function to implement Quick Sort
void QuickSort(int a[], int low, int high) {
if (low >= high)
return;

int key = low, i = low + 1, j = high;

// Partition the array into two halves
while (i <= j) {
while (a[i] <= a[key] && i <= high)
i++;
while (a[j] > a[key] && j >= low)
j--;
if (i < j)
Exch(&a[i], &a[j]);
}

Exch(&a[j], &a[key]); // Place the pivot element at the correct position
QuickSort(a, low, j - 1); // Recursively sort the left part
QuickSort(a, j + 1, high); // Recursively sort the right part
}

int main() {
int n, k;

36. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 31

clock_t st, et;
double ts;

// Input the number of elements to be sorted
printf("\nEnter how many numbers: ");
scanf("%d", &n);

if (n <= 0) {
printf("Invalid input\n");
return 1; // Indicate error if n is non-positive
}

int a[n]; // Array of size n

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

// Generate and display random numbers
printf("\nThe random numbers are:\n");
for (k = 0; k < n; k++) {
a[k] = rand(); // Generate a random number
printf("%d\t", a[k]);
}

// Start the clock to measure the sorting time
st = clock();

// Perform Quick Sort
QuickSort(a, 0, n - 1);

// Stop the clock after sorting
et = clock();

// Calculate the time taken in seconds
ts = (double)(et - st) / CLOCKS_PER_SEC;

// Display the sorted numbers
printf("\nSorted numbers are:\n");
for (k = 0; k < n; k++) {
printf("%d\t", a[k]);
}

37. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 32

// Display the time taken to perform the sorting
printf("\nThe time taken is: %e seconds\n", ts);

return 0; // Indicate success
}

**********OUTPUT***********
Enter how many numbers: 10

The random numbers are:
1804289383 846930887 1681692777 1714635016 295413767 1354970977
352644528 359761746 712600197 1902132171

Sorted numbers are:
295413767 359761746 352644528 712600197 846930887
1681692777 1714635016 1804289383 1902132171 1354970977

The time taken is: 1.503000e-06 seconds

38. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 33

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

// Function to merge two halves of an array
void Merge(int a[], int low, int mid, int high) {
int i, j, k;
int b[20];
i = low;
j = mid + 1;
k = low;

// Merge the two halves
while (i <= mid && j <= high) {
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}

// If there are remaining elements in the left half
while (i <= mid)
b[k++] = a[i++];

// If there are remaining elements in the right half
while (j <= high)
b[k++] = a[j++];

// Copy the merged elements back into the original array
for (k = low; k <= high; k++)
a[k] = b[k];
}

// Function to perform Merge Sort

39. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 34

void MergeSort(int a[], int low, int high) {
int mid;
if (low >= high)
return;

mid = (low + high) / 2;
MergeSort(a, low, mid); // Recursively sort the left half
MergeSort(a, mid + 1, high); // Recursively sort the right half
Merge(a, low, mid, high); // Merge the two sorted halves
}

int main() {
int n, a[2000], k;
clock_t st, et;
double ts;

// Input the number of elements to be sorted
printf("\nEnter how many numbers: ");
scanf("%d", &n);

if (n <= 0) {
printf("Invalid input.\n");
return 1; // Indicate error if n is non-positive
}

// Generate and display random numbers
printf("\nThe random numbers are:\n");
srand(time(NULL)); // Seed the random number generator
for (k = 0; k < n; k++) {
a[k] = rand(); // Generate random number
printf("%d\t", a[k]);
}

// Start the clock to measure the sorting time
st = clock();

// Perform Merge Sort
MergeSort(a, 0, n - 1);

// Stop the clock after sorting
et = clock();

40. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 35

// Calculate the time taken in seconds
ts = (double)(et - st) / CLOCKS_PER_SEC;

// Display the sorted numbers
printf("\nSorted numbers are:\n");
for (k = 0; k < n; k++) {
printf("%d\t", a[k]);
}

// Display the time taken to perform the sorting
printf("\nThe time taken is: %f seconds\n", ts);

return 0; // Indicate success
}

*******OUTPUT*****
Enter how many numbers: 10

The random numbers are:
1884913 2498491 1786493 121234 1239998 1348962 8765432
5432198 9887651 5555555

Sorted numbers are:
121234 1884913 2498491 1786493 1239998 1348962 8765432
5432198 9887651 5555555

The time taken is: 0.000005 seconds

41. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 36

PROGRAM 12

Design and implement C program for N Queen’s problem using
Backtracking

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

int a[30], count = 0;

// Function to check if a queen can be placed at position 'pos'
int place(int pos) {
int i;
for (i = 1; i < pos; i++) {
// Check if the queen is in the same column or diagonally
if ((a[i] == a[pos]) || (abs(a[i] - a[pos]) == abs(i - pos))) {
return 0; // Invalid position
}
}
return 1; // Valid position
}

// Function to print the solution
void print_sol(int n) {
int i, j;
count++;
printf("\n\nSolution #%d:\n", count);
// Print the board for the current solution
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (a[i] == j) {
printf("Q\t"); // Place a Queen
} else {
printf("*\t"); // Empty space
}
}
printf("\n");
}
}

// Function to solve the N-Queens problem using backtracking

42. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 37

void queen(int n) {
int k = 1;
a[k] = 0; // Initially place the first queen in a non-conflicting position

while (k != 0) {
a[k] = a[k] + 1; // Try to place the queen in the next column

// Check if the current placement is valid
while ((a[k] <= n) && !place(k)) {
a[k]++; // Try next column if current one is invalid
}

if (a[k] <= n) { // If valid placement
if (k == n) {
// If all queens are placed, print the solution
print_sol(n);
} else {
k++; // Move to next queen
a[k] = 0; // Place queen in a valid position
}
} else {
k--; // Backtrack if no valid placement
}
}
}

int main() {
int n;
// Input number of queens
printf("Enter the number of Queens: ");
scanf("%d", &n);

// Solve the N-Queens problem
queen(n);

// Print the total number of solutions
printf("\nTotal solutions = %d\n", count);

return 0;
}

43. ANALYSIS AND DESIGN ALGORITHMS LAB


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING 38

*****OUTPUT******
Enter the number of Queens: 4

Solution #1:
* Q * *
* * * Q
Q * * *
* * Q *

Solution #2:
* * Q *
Q * * *
* * * Q
* Q * *

Total solutions: 2