Analysis and Design of Algorithms Lab

Maharaja Education Trust (R), Mysuru

MAHARAJA INSTITUTE OF TECHNOLOGY MYSORE
An Autonomous Institute affiliated to Visvesvaraya Technological University,
Belagavi
Department of Computer Engineering

LAB Manual
For

Analysis and Design of Algorithms Lab

(M23BCSL406)
4th Semester

Prepared by,

Pradeep B M
Assistant Professor
Dept. of Computer Engineering
MIT Mysore.

Pradeep B M, Dept. of CE, MITMysore. Page 1

 Analysis and Design of Algorithms Lab

CHAPTER 1
INTRODUCTION
 The study of algorithms is the concepts of computer science.
 It is a standard set of important algorithms, they further our analytical skills& help us
in developing new algorithms for required applications

Algorithm

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for

obtaining a required output for any legitimate input ina finite amount of time.
In addition, all algorithms must satisfy the following criteria:
1. Input: Each algorithm should have zero or more inputs. The range of input for which
algorithms works should be specified carefully.
2. Output: The algorithm should produce correct results. At least one quantity has to be
produced.
3. Definiteness: Each instruction should be clear and unambiguous.
4. Effectiveness: Every instruction should be simple and should transform the given Input to
the desired output. so that it can be carried out, in
5. Finiteness: If we trace out the instruction of an algorithm, then for all cases, the algorithm
must terminate after a finite numb2er of steps.

Fundamentals of Algorithmic problem solving

• Understanding the problem

• Ascertain the capabilities of the computational device
• Exact /approximate solution.
• Decide on the appropriate data structure
• Algorithm design techniques
• Methods of specifying an algorithm
• Proving an algorithms correctness
• Analyzing an algorithm

Pradeep B M, Dept. of CE, MITMysore. Page 2

 Analysis and Design of Algorithms Lab
Important Problem Types of different categories
• Sorting
It refers to the problem of re-arranging the items of a given list in ascending or descending
order. The various algorithms that can be used for sorting are bubble sort, selection sort,
insertion sort, quick sort, merge sort, heap sort etc.
• Searching
 This problem deals with finding a value, called a search key, in a given set.
 The various algorithms that can be used for searching are binary search, linear search,
hashing, interpolation search etc.

• String processing
 This problem deals with manipulation of characters or strings, string matching, search
and replace, deleting a string in a text etc.
 String processing algorithm such as string matching algorithms is used in the design of
assemblers and compliers.

• Graph problems
 The graph is a collection of vertices and edges.
 Ex: graph traversal problems, topological sorting etc

• Combinatorial problems
These problems are used to find combinatorial object such as permutation and combinations.
Ex: travelling salesman problem, graph coloring problem etc.

• Geometric problems
This problem deal with geometric objects such as points, curves, lines, polygon etc.
Ex: closest-pair problem, convex hull problem

• Numerical problems
These problems involving mathematical manipulations solving equations, computing
differentiations and integrations, evaluating various types of functions etc.
Ex: Gauss elimination method, Newton-Rap son method

Fundamentals of data Structures

Since most of the algorithms operate on the data, particular ways of arranging the data play a
critical role in the design & analysis of algorithms.
A data structure can be defined as a particular way of arrangement of data.

The commonly used data structures are:

1. Linear data structures
2. Graphs
3. Trees.
4. Sets and dictionaries

Pradeep B M, Dept. of CE, MITMysore. Page 3

 Analysis and Design of Algorithms Lab
1. Linear data structures
The most common linear data structures are arrays and linked lists.
Arrays: Is a collection of homogeneous items. An item’s place within the collection is called
an index.
Linked list: finite sequence of data itemsi.e.it is a collection of data items in a certain order.

2. Graphs
A data structure that consists of a set of nodes and a set of edges that relate the nodes to each
other is called a graph.

3. Undirected graph: A graph in which the edges have no direction

 Directed graph (Digraph): A graph in which each edge is directed from one vertex to
another (or the same) vertex.
4. Tree
A tree is a connected acyclic graph that has no cycle.
5. Sets and dictionaries
 A set is defined as an unordered collection of distinct items called an element of the
set
 Dictionary is a data structure that implements searching, adding of objects

Analysis of algorithms

Analysis of algorithms means to investigate an algorithm’s efficiency with respect to

resources:

• Running time (time efficiency)

It indicates how fast an algorithm in question runs
• Memory space (space efficiency)
It deals with the extra space the algorithm requires

Theoretical analysis of time efficiency

Algorithm efficiency depends on the input size n. And for some algorithms efficiency
depends on type of input.
We have best, worst & average case efficiencies
 Worst-case efficiency:
Efficiency (number of times the basic operation will be executed) for the worst case
input of size n. i.e. The algorithm runs the longest among all possible inputs of size n.
 Best-case efficiency:
Efficiency (number of times the basic operation will be executed for the best case
input of size n. i.e. The algorithmruns the fastest among all possible inputs of size n.
 Average-case efficiency:
Average time taken(number of times the basic operation will be executed) to solve all
the possible instances (random) of the input.

Pradeep B M, Dept. of CE, MITMysore. Page 4

 Analysis and Design of Algorithms Lab
Asymptotic Notations

 Asymptotic notation is a way of comparing functions that ignores constant factors and
small input sizes.
 Three notations used to compare orders of growth of an algorithm’s basic operation
are:

O, Ω, θ notations.

1. Big-oh notation:

A functiont(n) is said to be in O(g(n)), denoted t(n)€O(g(n)),if t(n) is bounded above by

some constant multiple of g(n) for all large n i.e., if there exist some positive constant c
and some nonnegative integer n۪ 0 such that t (n)<=cg(n) for all n>= n0

2. Big-omega notation:

A functiont(n) is said to be in Ω(g(n)), denoted t(n)€ Ω(g(n)),ift(n) is bounded below by

some constant multiple ofg(n) for all large n i.e., if there exist some positive constant c
and Some nonnegative integer n 0 such that
t(n)>=cg(n) for all n>=n0

3. Big-theta notation:

A function t(n) is said to be in θ(g(n)), denoted t(n)€ θ(g(n)),if t(n) is bounded both above
and below by some positive constant multiple of g(n) for all large n i.e., if there exist
some positive constant c

Pradeep B M, Dept. of CE, MITMysore. Page 5

 Analysis and Design of Algorithms Lab

Pradeep B M, Dept. of CE, MITMysore. Page 6

 Analysis and Design of Algorithms Lab

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

Kruskal’s algorithm looks at a minimum spanning three for a weighted connected graph
G=(V,E) as an acyclic sub graph with V-1 edges for which the sum of the edge weights is the
smallest.
The algorithm begins by sorting the graph’s edges in increasing order of their weights. Then
starting with the empty sub graph, it scans this sorted list adding the next edge on the list to
the current sub graph if such an inclusion does not create a cycle and simply skipping the
edge otherwise.
When you select a minimum weight path, it will have source and destination vertices. These
two vertices should not have same ancestor or parent. If both the vertices have the same
origin, then it is a cyclic graph.
D C B A
Here CD is the current edge. Vertex C is the parent of D. But C has parent vertex called B.
For B also a parent called A. According to kruskal’s algorithm, we should add all previous
path to the current path. Then here vertex A becomes the parent of vertex D.

Aim : Kruskal's Algorithm for computing the minimum spanning tree is directly based on the
generic MST algorithm. It builds the MST in forest. Prim's algorithm is based ona generic
MST algorithm. It uses greedy approach.

Algorithm:

Kruskal's Algorithm

Start with an empty set A, and select at every stage the shortest edge that has not been chosen
or rejected, regardless of where this edge is situated in graph.
• Initially, each vertex is in its own tree in forest.
• Then, algorithm considers each edge in turn, order by increasing weight.
• If an edge(u,v) connects two different trees, then(u,v) is added to the set of edges of the
MST,and two trees connected by an edge(u,v)aremergedintoasingletree.
• On the other hand, if an edge(u,v )connects two vertices in the same tree, then
• edge(u,v) is discarded.

Program:

#include<stdio.h>
int ne=1,
min_cost=0;
void main ( )
{
int n,i,j, min,a,u,b,v,cost[20][20],parent[20];
printf("Enter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost matrix:\n");

Pradeep B M, Dept. of CE, MITMysore. Page 7

 Analysis and Design of Algorithms Lab
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
for(i=1;i<=n;i++)
parent[i]=0;
printf("\nThe edges of spanning tree are\n");
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j]; a=u=i;
b=v=j;
}
}
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
printf("Edge %d\t(%d->%d)=%d\n",ne++,a,b,min);
min_cost=min_cost+min;
parent[v]=u;
}
cost[a][b]=cost[a][b]=999;
}
printf("\nMinimum cost=%d\n",min_cost);
}

Pradeep B M, Dept. of CE, MITMysore. Page 8

 Analysis and Design of Algorithms Lab
Outcomes:
On completion of this Program, the students are able to :
 Solve Kruskal's algorithm to find shortest paths.
 Solve Minimum Cost Spanning Tree of a given undirected graph using kruskal algorithm

Viva questions
1 Which are the data structures is used to represent the graph.
2 What is tree?
3 What is spanning tree?
4 What is MST (Minimum-cost Spanning Tree)?
5 Difference between Greedyalgorithm and Dynamic algorithm method.

Pradeep B M, Dept. of CE, MITMysore. Page 9

 Analysis and Design of Algorithms Lab

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

Objectives:
This Program enable students to :
 Learn Prim's algorithm to find shortest paths.
 Find Minimum Cost Spanning Tree ofa given undirected graph using Prim's
algorithm

Choose a node and build a tree from there selecting at every stage the shortest available edge
that can extend the tree to an additional node.
• Prim'salgorithmhasthepropertythattheedgesinthesetAalwaysformasingletree.
• We begin with some vertex in a given graph G= (V, E), defining the initial set of vertices A.
• In each iteration, we choose a minimum-weight edge(u,v),connecting a vertex v in the set A
to the vertex u outside of set A.
• ThevertexuisbroughtintoA.Thisprocessisrepeateduntilaspanningtreeisformed.
• Like Kruskal's algorithm, here too,the import ant fact about MST sis weal ways choose the
smallest-weight edge joining a vertex inside set A to the one outside the set A.
• The implication of this fact is that It adds on ly edges that are safe for A;
• Therefore, when the algorithm terminates, the edges in set A form a MST

Program:
#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;
}
visited[1]=1; printf("\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)

Pradeep B M, Dept. of CE, MITMysore. Page 10

 Analysis and Design of Algorithms Lab
if(visited[i]!=0)
{
min=cost[i][j]; a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min); mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
}

Pradeep B M, Dept. of CE, MITMysore. Page 11

 Analysis and Design of Algorithms Lab

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

Floyds algorithm is a classic example for the application of dynamic programming. It is used
to compute the shortest distance between every two pair of nodes ina given graph and hence it
is also called “all-pair shortest path”algorithm

Program:
#include <stdio.h>
#include <limits.h>
#define V 4
void floydWarshall(int graph[V][V])
{
int dist[V][V],i,j,k;
for (i = 0; i < V; i++)
for ( j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for ( k = 0; k < V; k++)
for ( i = 0; i < V; i++)
for ( j = 0; j < V; j++)

Pradeep B M, Dept. of CE, MITMysore. Page 12

 Analysis and Design of Algorithms Lab
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j]
<dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
printf("Shortest distances between every pair of vertices:\n");
for (i = 0; i < V; i++)
{
for ( j = 0; j < V; j++)
{
if (dist[i][j] == INT_MAX)
printf("INF\t");
else
printf("%d\t", dist[i][j]);
}
printf("\n");
}
}
int main()
{
int graph[V][V] = {{0, INT_MAX, 3, INT_MAX},
{2, 0, INT_MAX, INT_MAX},
{INT_MAX, 7, 0, 1},{6, INT_MAX, INT_MAX, 0}};
floydWarshall(graph);
return 0;
}

Pradeep B M, Dept. of CE, MITMysore. Page 13

 Analysis and Design of Algorithms Lab
B .Design and implement C/C++ Program to find the transitive closure using Warshal's
algorithm.

# include <stdio.h>
int n,a[10][10],p[10][10];
void path()
{
int i,j,k; for(i=0;i<n;i++)
for(j=0;j<n;j++) p[i][j]=a[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(p[i][k]==1&&p[k][j]==1)
p[i][j]=1;
}
void main ()
{
int i,j;
printf("Enter the number of nodes:");
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]);
path();
printf("\nThe path matrix is shown below\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) printf("%d ",p[i][j]);
printf("\n");
}
}

Pradeep B M, Dept. of CE, MITMysore. Page 14

 Analysis and Design of Algorithms Lab

Pradeep B M, Dept. of CE, MITMysore. Page 15

 Analysis and Design of Algorithms Lab

Experiment No. 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.

Dijkstra’s algorithm finds shortest paths to a graph’s vertices in order of their distance from a
given source. First, it finds the shortest path from the source to a vertex nearest to it, then to a
second nearest and so on.

Pradeep B M, Dept. of CE, MITMysore. Page 16

 Analysis and Design of Algorithms Lab
#include<stdio.h>
void dij(int, int [20][20], int [20], int [20], int);
void main( )
{
int i, j, n, visited[20], source, cost[20][20], d[20];
printf("Enter no. of vertices: ");
scanf("%d", &n);
printf("Enter the cost adjacency matrix\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%d", &cost[i][j]);
}
}
printf("\nEnter the source node: ");
scanf("%d", &source);
dij(source, cost, visited, d, n);
for (i = 1; i <= n; i++)
{
if (i != source)
printf("\nShortest path from %d to %d is %d", source, i, d[i]);
}
}
void dij(int source, int cost[20][20], int visited[20], int d[20], int n)
{ int i, j, min, u, w;
for (i = 1; i <= n; i++)
{
visited[i] = 0;
d[i] = cost[source][i];
}
visited[source] = 1;
d[source] = 0;
for (j = 2; j <= n; j++)
{
min = 999;
for (i = 1; i <= n; i++)
{
if (!visited[i]) { if (d[i] < min)
{
min = d[i]; u = i;
}
}
}
visited[u] = 1;
for (w = 1; w <= n; w++)
{
if (cost[u][w] != 999 && visited[w] == 0)
{
if (d[w] > cost[u][w] + d[u])

Pradeep B M, Dept. of CE, MITMysore. Page 17

 Analysis and Design of Algorithms Lab
d[w] = cost[u][w] + d[u];
}
}
}
}

Pradeep B M, Dept. of CE, MITMysore. Page 18

 Analysis and Design of Algorithms Lab

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

Method: Source removal method. Each vertex may have an encoming endge or may not have
incoming edge. Vertex with no incoming edges deleted along with all the edges outgoing
from it. (If there are several sources, break tie arbitrarily. If there none, stop because the
problem cannot be solved). The order in which the vertices are deleted is to be displayed.
Here While numbering the vertices of the graph, remember to assign 1 to vertex with no
incoming edge.

A situation can be modeled by a graph in which vertices represent courses and directed edges
indicate prerequisite requirements. In terms of this digraph, the question is whether we can
list its vertices in such an order that for every edge in graph, the vertex where the edge starts
is listed before the vertex where the edge ends. This problem is called topological sorting. If a
directed graph has a directed cycle, then sorting is not possible. For topological sorting to be
possible, a digraph must be a dag (Directed Acyclic graph). It turns out that being a dag is not
only necessary but also sufficient for topological sorting to be possible. i.e if a diagraph has
no cycles, the topological sorting problem for it has a solution. There are two efficient
algorithms that both verify whether a digraph is a dag and if it is, produce an ordering vertices
that solves the topological sorting problem.

First algorithm is DFS. 2nd algorithm is Source removal method. Second method is based on
decrease and conquer technique: Repeatedly identifying in a remaining digraph. A
source,which is a vertex with no incoming edges and delete it along with all the edges
outgoing from it. (If there are several sources, break tie arbitrarily. If there none, stop
because the problem cannot be solved). The order in which the vertices are deleted yields a
solution to the topological sorting problem.The solution obtained by the source removal
algorithm is different from the one obtained by the DFS based algorithm. Both of them are
correct, of course. The topological sorting problem may have several alternative solutions.

Program:
#include<stdio.h>
void findindegree(int [10][10],int[10],int);
void topological(int,int [10][10]);
void main ()
{
int a[10][10],i,j,n;
printf("Enter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)

Pradeep B M, Dept. of CE, MITMysore. Page 19

 Analysis and Design of Algorithms Lab
scanf("%d",&a[i][j]);
printf("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",a[i][j]);
}
printf("\n");
}
topological(n,a);
}
void findindegree(int a[10][10],int indegree[10],int n)
{
int i,j,sum;
for(j=1;j<=n;j++)
{
sum=0; for(i=1;i<=n;i++)
{
sum=sum+a[i][j];
}
indegree[j]=sum;
}
}
void topological(int n,int a[10][10])
{
int k,top,t[100],i,stack[20],u,v,indegree[20];
k=1;
top=-1;
findindegree(a,indegree,n); for(i=1;i<=n;i++)
{
if(indegree[i]==0)
{
stack[++top]=i;
}
}
while(top!=-1)
{
u=stack[top--]; t[k++]=u; for(v=1;v<=n;v++)
{
if(a[u][v]==1)
{
indegree[v]--;
if(indegree[v]==0)
{
stack[++top]=v;
}
}
}
}

Pradeep B M, Dept. of CE, MITMysore. Page 20

 Analysis and Design of Algorithms Lab
printf("\nTopological sequence is\n");
for(i=1;i<=n;i++)
printf("%d\t",t[i]);
}

Pradeep B M, Dept. of CE, MITMysore. Page 21

 Analysis and Design of Algorithms Lab

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

Program:
#include<stdio.h>
#define MAX 50
int p[MAX],w[MAX],n;
int knapsack(int,int);
int max(int,int);
void main()
{
int m,i,optsoln;
printf("Enter no. of objects: ");
scanf("%d",&n);
printf("\nEnter the weights:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("\nEnter the profits:\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
printf("\nEnter the knapsack capacity:");

Pradeep B M, Dept. of CE, MITMysore. Page 22

 Analysis and Design of Algorithms Lab
scanf("%d",&m);
optsoln=knapsack(1,m);
printf("\nThe optimal soluntion is:%d",optsoln);
}
int knapsack(int i,int m)
{
if(i==n)
return (w[n]>m) ? 0 : p[n];
if(w[i]>m)
return knapsack(i+1,m);
return max(knapsack(i+1,m),knapsack(i+1,m-w[i])+p[i]);
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}

Output:
Enter no. of objects: 3 Enter the weights:
100 10 14
Enter the profits:
20 18 15
Enter the knapsack capacity:116 The optimal solution is:38

Pradeep B M, Dept. of CE, MITMysore. Page 23

 Analysis and Design of Algorithms Lab

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

Program:
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an item
struct Item
{
int value;
int weight;
};
// Function to compare two items based on their value-to-weight ratio
int compare(const void *a, const void *b)
{
double ratio1 = (double)((struct Item *)a)->value / ((struct Item *)a)->weight;
double ratio2 = (double)((struct Item *)b)->value / ((struct Item *)b)->weight;

Pradeep B M, Dept. of CE, MITMysore. Page 24

 Analysis and Design of Algorithms Lab
if (ratio1 < ratio2)
return 1; // Return 1 if ratio1 < ratio2
if (ratio1 > ratio2)
return -1; // Return -1 if ratio1 > ratio2
return 0; // Return 0 if both ratios are equal
}
// Discrete Knapsack Problem (0/1 Knapsack using Greedy Approximation)
int discreteKnapsack(int W, struct Item items[], int n)
{
int totalValue = 0;
// Sort items based on value-to-weight ratio
qsort(items, n, sizeof(struct Item), compare);
for (int i = 0; i < n; i++)
{
if (items[i].weight <= W)
{
W -= items[i].weight;
totalValue += items[i].value;
}
}
return totalValue;
}
// Continuous Knapsack Problem (Fractional Knapsack using Greedy Approximation)
double continuousKnapsack(int W, struct Item items[], int n)
{
double totalValue = 0.0;
// Sort items based on value-to-weight ratio
qsort(items, n, sizeof(struct Item), compare);
for (int i = 0; i < n; i++)
{
if (items[i].weight <= W)
{
W -= items[i].weight;
totalValue += items[i].value;
}
else
{
totalValue += items[i].value * ((double)W / items[i].weight);
break; // We can take a fraction of the current item
}
}
return totalValue;
}

Pradeep B M, Dept. of CE, MITMysore. Page 25

 Analysis and Design of Algorithms Lab
int main()
{
// Example items: value, weight
struct Item items[] = {
{60, 10},
{100, 20},
{120, 30}
};
int n = sizeof(items) / sizeof(items[0]); // Number of items
int W = 50; // Knapsack capacity
// Solve Discrete Knapsack (0/1 Knapsack)
int maxValueDiscrete = discreteKnapsack(W, items, n);
printf("Maximum value in Discrete Knapsack: %d\n", maxValueDiscrete);
// Solve Continuous Knapsack (Fractional Knapsack)
double maxValueContinuous = continuousKnapsack(W, items, n);
printf("Maximum value in Continuous Knapsack: %.2f\n", maxValueContinuous);
return 0;
}
Output:
Maximum value in Discrete Knapsack: 220
Maximum value in Continuous Knapsack: 240.00

Pradeep B M, Dept. of CE, MITMysore. Page 26

 Analysis and Design of Algorithms Lab

Experiment No.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.

Aim:
An instance of the Subset Sum problem Is a pair(S,t),where S={x1,x2, ............. ,xn} is a set of
Positive integers and t (the target) is a positive integer. The decision problem asks for a subset
of S whose sum is as large as possible, but not larger than t.
This problem is NP-complete.
This problem arises in practical applications. Similar to the knapsack problem we may have a
truck that can carry at most t pounds and we have n different boxes to ship and the ith box
weighs xi pounds. The naive approach of computing the sum of the elements of every subset
of S and then selecting the best requires exponential time. Below we present an exponential
time exact algorithm.

#include<stdio.h>
void subset(int,int,int);
int x[10],w[10],d,count=0;
void main()
{
int i,n,sum=0;
printf("Enter the no. of elements: ");
scanf("%d",&n);
printf("\nEnter the elements in ascending order:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]); printf("\nEnter the sum: ");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum<d)
{
printf("No solution\n");
return;
}
subset(0,0,sum);
if(count==0)
{
printf("No solution\n");
return;
}
}
void subset(int cs,int k,int r)
{
int i; x[k]=1; if(cs+w[k]==d)
{

Pradeep B M, Dept. of CE, MITMysore. Page 27

 Analysis and Design of Algorithms Lab
printf("\n\nSubset %d\n",++count);
for(i=0;i<=k;i++)
if(x[i]==1)
printf("%d\t",w[i]);
}
else
if(cs+w[k]+w[k+1]<=d)
subset(cs+w[k],k+1,r-w[k]);
if(cs+r- w[k]>=d && cs+w[k]<=d)
{
x[k]=0;
subset(cs, k+1,r-w[k]);
}
}
Output:
Enter the no. of elements: 5
Enter the elements in ascending order:
1
2
5
6
8
Enter the sum: 9
Subset 1
126
Subset 2
18

Pradeep B M, Dept. of CE, MITMysore. Page 28

 Analysis and Design of Algorithms Lab

Experiment No. 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.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to perform selection sort
void selectionSort(int arr[], int n)
{
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++)
{
minIndex = i;
for (j = i + 1; j < n; j++)
{

Pradeep B M, Dept. of CE, MITMysore. Page 29

 Analysis and Design of Algorithms Lab
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// Swap the found minimum element with the first element
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Function to generate random numbers between 0 and 999
int generateRandomNumber()
{
return rand() % 1000;
}
int main()
{
// Set n value
int n = 6000,i;
// Allocate memory for the array
int* arr = (int*)malloc(n * sizeof(int));
// Generate random elements for the array
srand(time(NULL));
printf("Random numbers for n = %d:\n", n);
for ( i = 0; i < n; i++)
{
arr[i] = generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");
clock_t start = clock(); // Record the start time
sort selectionSort(arr, n); // Perform selection
clock_t end = clock(); // Record the end time
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC; // Calculate the
time taken for sorting
// Output the time taken to sort for the current value of n
printf("\nTime taken to sort for n = %d: %lf seconds\n\n", n, time_taken);
// Display sorted numbers
printf("Sorted numbers for n = %d:\n", n);
for ( i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");
// Free the dynamically allocated memory
free(arr);
return 0;
}

Pradeep B M, Dept. of CE, MITMysore. Page 30

 Analysis and Design of Algorithms Lab

Pradeep B M, Dept. of CE, MITMysore. Page 31

 Analysis and Design of Algorithms Lab

Experiment No. 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.

Quick sort is one of the sorting algorithms working on the Divide and Conquer principle.
Quick sort works by finding an element, called pivot, in the given array and partitions the
array into three sub arrays such that The left sub array contains all elements which are less
than or equal to the pivot The middle sub arrays contains pivot The right sub array contains
all elements which are greater than or equal to the pivot.
Quick sort is well-known sorting algorithms based on the divide and conquer technique.
Quicksort divide s its input elements according to the i value. Specifically, it rearrange s
elements of a given array A[n-1]to achieve its partition, as it uation where all the elements
before some position s are smaller than or equal to A[s] and all the elements after some
position s are greater than or equal to A[s].We call this element the pivot.

After a partition has been achieved, A[s] will be in its final position in the sorted array, and
we can continue sorting the two sub arrays of the elements preceding and following A[s]
independently.

Pradeep B M, Dept. of CE, MITMysore. Page 32

 Analysis and Design of Algorithms Lab

Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to swap two elements
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Function to partition the array and return the pivot index
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1),j;
for (j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
Pradeep B M, Dept. of CE, MITMysore. Page 33
 Analysis and Design of Algorithms Lab
// Function to perform Quick Sort
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to generate random numbers between 0 and 999
int generateRandomNumber()
{
return rand() % 1000;
}
int main()
{
// Set n value
int n= 6000;
// Allocate memory for the array
int* arr = (int*)malloc(n * sizeof(int));
// Generate random elements for the array srand(time(NULL));
printf("Random numbers for n = %d:\n", n);
for ( i = 0; i < n; i++)
{
arr[i] = generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");
// Record the start time
clock_t start = clock();
// Perform quick sort
quickSort(arr, 0, n - 1);
// Record the end time
clock_t end = clock();
// Calculate the time taken for sorting
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
// Output the time taken to sort for the current value of n
printf("\nTime taken to sort for n = %d: %lf seconds\n\n", n, time_taken);
// Display sorted numbers
printf("Sorted numbers for n = %d:\n", n);
for( i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");
// Free the dynamically allocated memory free(arr);
return 0;
}

Pradeep B M, Dept. of CE, MITMysore. Page 34

 Analysis and Design of Algorithms Lab
Output:
Random numbers for n=6000:
243 112 599 677 912 413 721 547 640 822 … (more numbers).......394.....
Time taken to sprt for n=6000 : 1.058000 seconds Sorted numbers for n=6000:
0 0 1 2 2 3 3 3 4 5 …..(more numbers) ….. 995 996 996 997 998
999 999

Pradeep B M, Dept. of CE, MITMysore. Page 35

 Analysis and Design of Algorithms Lab

Experiment No. 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.

The basic operation in merge sort is comparison and swapping. Merge sort algorithm calls it
self recursively. Merge sort divides the array into sub arrays based on the position of the
elements whereas quick sort divides the array into sub arrays based on the value of the
elements.
Merge sort requires an auxiliary array to do the merging.The merging of two subarrays,which
are already sorted, into an auxiliary array can be done in O(n) where n is the total number of
elementsinboththesubarrays.Thisispossiblebecauseboththesubarraysaresorted.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Merge two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
Pradeep B M, Dept. of CE, MITMysore. Page 36
 Analysis and Design of Algorithms Lab
// Merge the temporary arrays back into arr[l..r]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Merge sort function
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Function to generate random numbers between 0 and 999
int generateRandomNumber()
{
return rand() % 1000;
}

Pradeep B M, Dept. of CE, MITMysore. Page 37

 Analysis and Design of Algorithms Lab
int main()
{
// Set n value
int n = 6000;
// Allocate memory for the array
int* arr = (int*)malloc(n * sizeof(int));
// Generate random elements for the array
srand(time(NULL));
printf("Random numbers for n = %d:\n", n);
for ( i = 0; i < n; i++)
{
arr[i] = generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");
// Record the start time
clock_t start = clock();
// Perform merge sort
mergeSort(arr, 0, n - 1);
// Record the end time
clock_t end = clock();
// Calculate the time taken for sorting
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
// Output the time taken to sort for the current value of n
printf("\nTime taken to sort for n = %d: %lf seconds\n\n", n, time_taken);
// Display sorted numbers
printf("Sorted numbers for n = %d:\n", n);
for ( i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");
// Free the dynamically allocated memory
free(arr);
return 0;
}
Output:
Random numbers for n=6000:
243 112 599 677 912 413 721 547 640 822 … (more numbers).......394.....
Time taken to sprt for n=6000 : 1.058000 seconds Sorted numbers for n=6000:
0 0 1 2 2 3 3 3 4 5 …..(more numbers) ….. 995 996 996 997 998
999 999

Pradeep B M, Dept. of CE, MITMysore. Page 38

 Analysis and Design of Algorithms Lab

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

Algorithm:
Input:
A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is
adjacency matrix representation of the graph.
A value graph[i][j] is 1 if there is a direct edge from i to j,
otherwise graph[i][j] is 0.
Output:
An array path[V] that should contain the Hamiltonian Path. path[i] should represent the ith
vertexintheHamiltonianPath.Thecodeshouldalsoreturnfalseifthereis no Hamiltonian Cycle in the
graph.

Backtracking Algorithm

Create an empty path array and add vertex 0 to it.

Add other vertices, starting from the vertex 1.
Before adding a vertex, check for whether it Is adjacent to the previously added vertex and not
already added.
If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex
then we return false.

Program:
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int board[MAX][MAX];
// Function to print the board
void printBoard(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ", board[i][j]);
}
printf("\n");
}
}
// Function to check if it's safe to place a queen at board[row][col]
bool isSafe(int n, int row, int col)
{
// Check the column
for (int i = 0; i < row; i++)
{
if (board[i][col] == 1)
{
return false;
}
}

Pradeep B M, Dept. of CE, MITMysore. Page 39

 Analysis and Design of Algorithms Lab

// Check the upper-left diagonal

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (board[i][j] == 1)
{
return false;
}
}
// Check the upper-right diagonal
for (int i = row, j = col; i >= 0 && j < n; i--, j++)
{
if (board[i][j] == 1)
{
return false;
}
}
return true;
}
// Function to solve N Queens problem using Backtracking
bool solveNQueens(int n, int row)
{
// Base case: If all queens are placed
if (row >= n)
{
return true;
}
// Try placing a queen in all columns one by one
for (int col = 0; col < n; col++)
{
if (isSafe(n, row, col))
{
board[row][col] = 1; // Place queen
// Recur to place the next queen
if (solveNQueens(n, row + 1))
{
return true;
}
// If placing queen in board[row][col] doesn't lead to a solution, backtrack
board[row][col] = 0; // Remove queen
}
}
// If no place is found for queen in this row, return false
return false;
}
// Main function to read input and solve the N Queens problem
int main()
{
int n;
// Read the size of the chessboard (N)
printf("Enter the number of queens (N): ");

Pradeep B M, Dept. of CE, MITMysore. Page 40

 Analysis and Design of Algorithms Lab
scanf("%d", &n);
// Initialize the board with 0's (no queens placed)
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
board[i][j] = 0;
}
}
// Solve the problem
if (solveNQueens(n, 0))
{
printf("Solution to the N-Queens problem:\n");
printBoard(n);
}
else
{
printf("No solution exists for %d queens.\n", n);
}
return 0;
}

Pradeep B M, Dept. of CE, MITMysore. Page 41