ATME COLLEGE OF ENGINEERING

13th KM Stone, Bannur Road, Mysore - 560 028

DEPARTMENT OF COMPUTER SCIENCE ENGINEERING

(DATA SCIENCE)

(ACADEMIC YEAR 2023-24)

LABORATORY MANUAL

SUBJECT: ANALYSIS & DESIGN OF ALGORITHMS LABORATORY

SUB CODE: BCSL404
SEMESTER: IV-2022 CBCS Scheme

Composed By Verified By Approved By

Mr.Babuprasad Mrs. Madhu Nagaraju Dr. ANITHA D B

i Instructor Faculty Incharge HOD, CSE-DSE
 INSTITUTIONAL MISSION AND VISION

Objectives
To provide quality education and groom top-notch professionals, entrepreneurs and leaders for
different fields of engineering, technology and management.

To open a Training-R & D-Design-Consultancy cell in each department, gradually introduce doctoral
and postdoctoral programs, encourage basic & applied research in areas of social relevance, and
develop the institute as a center of excellence.

To develop academic, professional and financial alliances with the industry as well as the academia at
national and transnational levels

To develop academic, professional and financial alliances with the industry as well as the academia at
national and transnational levels.

To cultivate strong community relationships and involve the students and the staff in local community
service.

To constantly enhance the value of the educational inputs with the participation of students, faculty,
parents and industry.
Vision
Development of academically excellent, culturally vibrant, socially responsible and globally competent
human resources.

Mission
 To keep pace with advancements in knowledge and make the students competitive and capable at the
global level.
 To create an environment for the students to acquire the right physical, intellectual, emotional and
moral foundations and shine as torch bearers of tomorrow’s society.
 To strive to attain ever-higher benchmarks of educational excellence.
 DEPARTMENT OF COMPUTER SCIENCE ENGINEERING AND ENGINEERING

(DATA SCIENCE &ENGINEERING)

Vision of The Department

• To impart technical education in the field of data science of excellent quality with a high level of
professional competence, social responsibility, and global awareness among the students

Mission
• To impart technical education that is up to date, relevant and makes students competitive and employable
at global level
• To provide technical education with a high sense of discipline, social relevance in an intellectually,
ethically and socially challenging environment for better tomorrow
• Educate to the global standards with a benchmark of excellence and to kindle the spirit of innovation.

Program Outcomes(PO)

 Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals,

and an engineering specialization to the solution of complex engineering problems.

 Problem analysis: Identify, formulate, review research literature, and analyze complex engineering
problems reaching substantiated conclusions using first principles of mathematics, natural sciences, and
engineering sciences.

 Design/development of solutions: Design solutions for complex engineering problems and design system
components or processes that meet the specified needs with appropriate consideration for the public health
and safety, and the cultural, societal, and environmental
considerations.
 Conduct investigations of complex problems: Use research-based knowledge and research methods
including design of experiments, analysis and interpretation of data, and synthesis of the information to
provide valid conclusions.
  Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern engineering
and IT tools including prediction and modeling to complex engineering activities with an understanding
of the limitations.

 The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal,
health, safety, legal and cultural issues and the consequent responsibilities relevant to the professional
engineering practice
 Environment and sustainability: Understand the impact of the professional engineering solutions in
societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable
development.

 Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of the
engineering practice.

 Individual and team work: Function effectively as an individual, and as a member or leader in diverse
teams, and in multidisciplinary settings.

 Communication: Communicate effectively on complex engineering activities with the engineering

community and with society at large, such as, being able to comprehend and write effective reports and
design documentation, make effective presentations, and give and receive clear instructions.

 Project management and finance: Demonstrate knowledge and understanding of the engineering and
management principles and apply these to one’s own work, as a member and leader in a team, to manage
projects and in multidisciplinary environments.
 Life-long learning: Recognize the need for, and have the preparation and ability to engage in independent
and life-long learning in the broadest context of technological change.

Program Specific Outcomes (PSOs)

 PSO1: Develop relevant programming skills to become a successful data scientist

 PSO2: Apply data science concepts and algorithms to solve real world problems of the society
  PSO3: Apply data science techniques in the various domains like agriculture, education healthcare for
better society

Program Educational Objectives (PEOs):

PEO1: Develop cutting-edge skills in data science and its related technologies, such as machine learning,
predictive analytic, and data engineering.

PEO2: Design and develop data-driven solutions to real-world problems in a business, research, or social
environment.

PEO3: Apply data engineering and data visualization techniques to discover, investigate, and interpret data.

PEO4: Demonstrate ethical and responsible data practices in problem solving

PEO5: Integrate fields within computer science, optimization, and statistics to develop better solutions
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.

Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
6 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.

Viva Questions and Answers

Analysis & Design of Algorithms Laboratory BCSL404

CHAPTER 1

INTRODUCTION
Need for studying algorithms
Theoretical importance

 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 in a finite amount oftime.
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.

Notion of algorithm

Problem

Algorithm

Input Outpu
t
“Computer”

DEPT. OF CSE-DS, ATMECE Page 1

Analysis & Design of Algorithms Laboratory BCSL404

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

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

DEPT. OF CSE-DS, ATMECE Page 2

Analysis & Design of Algorithms Laboratory BCSL404

• 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 dealwith 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 ofdata.

The commonly used data structures are:

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

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 ofdata items ina 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.

DEPT. OF CSE-DS, ATMECE Page 3

Analysis & Design of Algorithms Laboratory BCSL404

 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.

3. Tree
A tree is a connected acyclic graphthat has no cycle.

4. 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 analgorithm’s efficiencywith respect to

resources:

• Running time (time efficiency)

It indicates how fast an algorithm in question runs

• Memory space (space efficiency)

It deals withthe 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 operationwill be executed for the best case
input of size n. i.e. The algorithm runs the fastest among all possible inputs of size n.

DEPT. OF CSE-DS, ATMECE Page 4

Analysis & Design of Algorithms Laboratory BCSL404

Average-case efficiency:
Average time taken(number of times the basic operationwill be executed) to solve all the

possible instances (random) of the input.

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.

Big-oh notation:
A function t(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

Big-oh notationt(n)€O(g(n)) Big-omega notation t(n)€Ω,(g(n))

Big-omega notation:
A function t(n) is said to be inΩ(g(n)),denoted t(n)€ Ω(g(n)),ift(n) is bounded below 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 suchthat

t(n)>=cg(n) for all

n>=n0Big-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

DEPT. OF CSE-DS, ATMECE Page 5

Analysis & Design of Algorithms Laboratory BCSL404

c2g (n) <=t (n) <=c1g (n) for all n>= n0

Big-theta

notation t(n)€θ(g(n))Basic Asymptotic

Efficiency classes:

1 constant

log n logarithmic

N linear

n log n n log n

n2 quadratic

n3 cubic

2n exponential

n! factorial

DEPT. OF CSE-DS, ATMECE Page 6

Analysis & Design of Algorithms Laboratory BCSL404

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];

int find(int);
int uni(int,int);
void main()
{
printf("\n\tImplementation of Kruskal's algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
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)
cost[i][j]=999;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
}
int find(int i)
{

DEPT. OF CSE-DS, ATMECE Page 7

Analysis & Design of Algorithms Laboratory BCSL404

while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}

DEPT. OF CSE-DS, ATMECE Page 8

Analysis & Design of Algorithms Laboratory 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>
#include<conio.h>
int i,j,u,v,n,ne=1;
int min,mincost=0,visited[10]={0},cost[10][10];
void main()
{

printf("\n Enter the No of nodes or vertices:");

scanf("%d",&n);
printf("\n Enter the Cost Adjacency matrix of the given graph:\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;
}
printf("The edges of Minimum Cost Spanning Tree are\n");
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)
if(visited[i]!=0)
{
min=cost[i][j];
u=i;
v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("%d edge (%d,%d) =%d\n",ne++,u,v,min);
mincost=mincost+min;
visited[v]=1;
}
cost[u][v]=cost[v][u]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
}

DEPT. OF CSE-DS, ATMECE Page 9

Analysis & Design of Algorithms Laboratory BCSL404

3. a) Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's
algorithm.
#include<stdio.h>
#include<stdlib.h>
int a[10][10],d[10][10],n;

int min(int a, int b)

{
return (a<b) ? a:b;
}

void path()
{
int i, j, k;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
d[i][j]= min(d[i][j], d[i][k]+d[k][j]);
}
}
}
}
int main()
{
int i,j;
printf("Enter the no of Vertices:");
scanf("%d", &n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
d[i][j]= a[i][j];
}
path();
printf("Final Distance Matrix:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",d[i][j]);
}
printf("\n");
}
}
b) Warshal’s Algorithmn
#include<stdio.h>
#include<stdlib.h>
int a[10][10],t[10][10],n;
void path()

DEPT. OF CSE-DS, ATMECE Page 10

Analysis & Design of Algorithms Laboratory BCSL404

{
int i, j, k;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if((t[i][j]) || (t[i][k]&& t[k][j]))
t[i][j] =1;
}
}
}
}
int main()
{
int i,j;
printf("Enter the no of Vertices:");
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]);
t[i][j]= a[i][j];
}
path();
printf("Transitive Matrix:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",t[i][j]);
}
printf("\n");
}
}

DEPT. OF CSE-DS, ATMECE Page 11

Analysis & Design of Algorithms Laboratory BCSL404

4. Program in C to find shortest paths from a given vertex in a weighted connected graph to other vertices
using Dijkstra's algorithm.

#include<stdio.h>
#include<conio.h>
#define infinity 999
void dij(int n,int v,int cost[10][10],int dist[100])
{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}

int main()
{
int n,v,i,j,cost[10][10],dist[10];
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the cost 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]=infinity;
}
printf("\n Enter the source matrix:");
scanf("%d",&v);
dij(n,v,cost,dist);
printf("\n Shortest path:\n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d\n",v,i,dist[i]);
}

DEPT. OF CSE-DS, ATMECE Page 12

Analysis & Design of Algorithms Laboratory 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 a[10][10],n,indegre[10];
void find_indegre()
{ int j,i,sum;
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;
find_indegre();
for(i=0;i<n;i++)
{
if(indegre[i]==0) s[++top]=i;
}
while(top!=-1)
{
u=s[top--];
t[k++]=u;
for(v=0;v<n;v++)
{
if(a[u][v]==1)
{
indegre[v]--;
if(indegre[v]==0) s[++top]=v;
}
}
}
printf("The topological Sequence is:\n");
for(i=0;i<n;i++)
printf("%d ",t[i]);
}

int 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();
}

DEPT. OF CSE-DS, ATMECE Page 13

Analysis & Design of Algorithms Laboratory BCSL404

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

#include<stdio.h>
#include<conio.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]);
}

int main()
{
int profit,count=0;
printf("\nEnter the number of elements\n");
scanf("%d",&n);
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]);
}
printf("\nEnter the capacity \n");
scanf("%d",&cap);
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;
profit=knap(n,cap);
i=n;
j=cap;
while(j!=0&&i!=0)
{
if(v[i][j]!=v[i-1][j])
{
x[i]=1;
j=j-w[i];
i--;
}
else

DEPT. OF CSE-DS, ATMECE Page 14

Analysis & Design of Algorithms Laboratory BCSL404

i--;
}
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]);
printf("Total profit = %d\n",profit);
}

DEPT. OF CSE-DS, ATMECE Page 15

Analysis & Design of Algorithms Laboratory BCSL404

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

#include<stdio.h>
#include<stdlib.h>
int main()
{
float weight[50],profit[50],ratio[50],Totalvalue,temp,capacity,amount;
int n,i,j;
printf("Enter the number of items :");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter Weight and Profit for item[%d] :\n",i);
scanf("%f %f", &weight[i], &profit[i]);
}
printf("Enter the capacity of knapsack :\n");
scanf("%f",&capacity);

for(i=0;i<n;i++)
ratio[i]=profit[i]/weight[i];

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

for (j = i + 1; j < n; j++)
if (ratio[i] < ratio[j])
{
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;

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

temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}

printf("Knapsack problems using Greedy Algorithm:\n");

for (i = 0; i < n; i++)
{
if (weight[i] > capacity)
break;
else
{
Totalvalue = Totalvalue + profit[i];
capacity = capacity - weight[i];
}
}
if (i < n)
Totalvalue = Totalvalue + (ratio[i]*capacity);
printf("\nThe maximum value is :%f\n",Totalvalue);
return 0;
}

DEPT. OF CSE-DS, ATMECE Page 16

Analysis & Design of Algorithms Laboratory BCSL404

8. 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>
#include<conio.h>
int s[10] , x[10],d ;
void sumofsub ( int , int , int ) ;
int main ()
{
int n , sum = 0 ;
int i ;
printf ( " \n Enter the size of the set : " ) ;
scanf ( "%d" , &n ) ;
printf ( " \n Enter the set in increasing order:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
scanf ("%d", &s[i] ) ;
printf ( " \n Enter the value of d : \n " ) ;
scanf ( "%d" , &d ) ;
for ( i = 1 ; i <= n ; i++ )
sum = sum + s[i] ;
if ( sum < d || s[1] > d )
printf ( " \n No subset possible : " ) ;
else
sumofsub ( 0 , 1 , sum ) ;
}
void sumofsub ( int m , int k , int r )
{
int i=1 ;
x[k] = 1 ;
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 )
sumofsub ( m + s[k] , k + 1 , r - s[k] ) ;
if ( ( m + r - s[k] >= d ) && ( m + s[k+1] <=d ) )
{
x[k] = 0;
sumofsub ( m , k + 1 , r - s[k] ) ;
}
}

DEPT. OF CSE-DS, ATMECE Page 17

Analysis & Design of Algorithms Laboratory BCSL404

9. Design and implement C Program to sort a given set of n integer elements using Selection Sort method
and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken
to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated
using the random number generator.

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

void selection(int arr[], int n)

{
int i, j, small;

for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
small = i; //minimum element in unsorted array

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

if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}

int main()
{
int n, a[1000],k;
clock_t st,et;
double ts;
printf("\n Enter How many Numbers: ");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for(k=1; k<=n; k++)
{
a[k]=rand();
printf("%d\t",a[k]);
}
st=clock();
selection(a,n);
et=clock();
ts=(double)(et-st)/CLOCKS_PER_SEC;
printf("\nSorted Numbers are: \n ");
for(k=1; k<=n; k++)
printf("%d\t", a[k]);
printf("\nThe time taken is %e",ts);
}

DEPT. OF CSE-DS, ATMECE Page 18

Analysis & Design of Algorithms Laboratory 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>
#include<stdlib.h>
# include <time.h>

void Exch(int *p, int *q)

{
int temp = *p;
*p = *q;
*q = temp;
}
void QuickSort(int a[], int low, int high)
{
int i, j, key, k;
if(low>=high)
return;
key=low; i=low+1; j=high;
while(i<=j)
{
while ( a[i] <= a[key] ) i=i+1;
while ( a[j] > a[key] ) j=j-1;
if(i<j) Exch(&a[i], &a[j]);
}
Exch(&a[j], &a[key]);
QuickSort(a, low, j-1);
QuickSort(a, j+1, high);
}
int main()
{
int n, a[1000],k;
clock_t st,et;
double ts;
srand(time(NULL));
printf("\n Enter How many Numbers: ");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for(k=1; k<=n; k++)
{
a[k]=rand();
printf("%d\t",a[k]);
}
st=clock();
QuickSort(a, 1, n);
et=clock();
ts=(double)(et-st)/CLOCKS_PER_SEC;
printf("\nSorted Numbers are: \n ");
for(k=1; k<=n; k++)
printf("%d\t", a[k]);
printf("\nThe time taken is %e",ts);
}

DEPT. OF CSE-DS, ATMECE Page 19

Analysis & Design of Algorithms Laboratory 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>
# include <stdlib.h>
#include<time.h>

void Merge(int a[], int low, int mid, int high)

{
int i, j, k, b[20];
i=low; j=mid+1; k=low;
while ( i<=mid && j<=high )
{
if( a[i] <= a[j] )
b[k++] = a[i++] ;
else
b[k++] = a[j++] ;
}
while (i<=mid) b[k++] = a[i++] ;
while (j<=high) b[k++] = a[j++] ;
for(k=low; k<=high; k++)
a[k] = b[k];
}
void MergeSort(int a[], int low, int high)
{
int mid;
if(low >= high)
return;
mid = (low+high)/2 ;
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
Merge(a, low, mid, high);
}
int main()
{
int n, a[2000],k;
clock_t st,et;
double ts;
srand(time(NULL));
printf("\n Enter How many Numbers:");
scanf("%d", &n);
printf("\nThe Random Numbers are:\n");
for(k=1; k<=n; k++)
{
a[k]=rand();
printf("%d\t", a[k]);
}
st=clock();
MergeSort(a, 1, n);
et=clock();
ts=(double)(et-st)/CLOCKS_PER_SEC;
printf("\n Sorted Numbers are : \n ");

DEPT. OF CSE-DS, ATMECE Page 20

Analysis & Design of Algorithms Laboratory BCSL404

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

printf("%d\t", a[k]);
printf("\nThe time taken is %e",ts);
}

DEPT. OF CSE-DS, ATMECE Page 21

Analysis & Design of Algorithms Laboratory BCSL404

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

#include<stdio.h>
#include<stdlib.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");
}
}

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;

DEPT. OF CSE-DS, ATMECE Page 22

Analysis & Design of Algorithms Laboratory BCSL404

}
}
else
k--;
}
}

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

DEPT. OF CSE-DS, ATMECE Page 23

Analysis & Design of Algorithms Laboratory BCSL404

VIVA QUESTIONS

1. What is an Algorithm?
Algorithm is a Step by step procedure to Solve a given problem for a finite number of input
producing finite number of output with desired output.

2. What is a Flow Chart?

Flow chart is a Graphical Representation of a solution to the Problem.

3. What is the difference between Algorithm, Flow Chart, Program?

 Algorithm specifies the different things to be followed for solving a Problem.

 Flow Chart is a Graphical Representation of a Solution to the Problem. Both

Algorithm and Flow Chartare Machine Independent.
 Program is a Set of Instructions which is used as a tool to communicate to the
machine to get our workdone, Program is Machine Dependent for particular
Machine.

4. What is the Aim of DAA lab or why we need to study DAA Lab
DAA is a discipline, where we are dealing with designing or writing the algorithm keeping
in Consideration of Space and Time Complexity, Such that Our Algorithm should execute
in a very minimum amount of time by Minimum Space or RAM.

5. Define Space and Time Complexity? Among this which one is more prioritized?
Space Complexity is a measure of Amount of Space taken by a Program to finish its Execution.
Time Complexity is a measure of amount of time taken by a program to complte its Execution.
Depending Upon Application it is considered, EX:For Mobile or Handheld Devices, We give
Prefernce for both Space and time.
For a Huge and Inter active Systems like Web Applications we give more Preferences to time
Complexeity.

6. What is Design and what is Analysis of a Program?

Design is a Process of Writing an algorithm to a given Problem so that it should accept finite
number ofinput and finite number of output with a definite output and Should Exit appropriately.

DEPT. OF CSE-DS, ATMECE Page 24

Analysis & Design of Algorithms Laboratory BCSL404

Analysis:Analysis is a next Phase of Writing an Algorithm ,in this phase we calculate the Efficiency
of anAlgorithm i.e time and space needed by an algorithm.

7. Write the general plan for analyzing the recursive algorithms.

 Identify the inputs.

 Identify the output is depended only on number of inputs.

 Identify the Basic Operation in Algorithm.

 Form or write the Recursive Relation to the Algorithm.

8. What are the various notations used to write an algorithm?

(i) Pseudocode (ii)Natural Language and etc..

9. What is a Pseudocode?
It’s a notation which is having the combination of Programming Constructs and English like Statements.

10. What is the Time Complexity of Bubble Sort, Selection Sort , Merge Sort, Quick
Sort?(L3)
Bubble Sort-n2, Selection Sort- n2 Merge Sort-nlog.n Quick Sort -
nLogn, Worst case for Quick Sort- n2

11. Which sorting algorithm is more Efficient and why?

Quick Sorting is More Efficient ,because this algorithm is instable algorithm and in place.

12. What do you mean by the term Instable Algorithms?

The Instable Algorithms are one, which divides the array as certainly depending upon pivot or
key element and hence i index precedes index j

13. Which algorithms are faster?

Instable Algorithms are much Faster compared to Stable Algorithms.

14. For what type of instance Merge sort do better than Quick Sort?

DEPT. OF CSE-DS, ATMECE Page 25

Analysis & Design of Algorithms Laboratory BCSL404

For a Larger input and a sorted input values.

15. For what type of instance Quick sort do better than Merge Sort?

For Smaller Set of input numbers.

16. What are Inplace Algorithms?

Inplace Algorithms are the one which doesn't occupies Extra Space.

17. Write the order of growth terms as per the time Execution in Ascending Order.
logn,n,nlogn,n2,n3, ...... nn,2n,n!

18. What is Brute Force Technique? When We Should Use?

Brute Force is a straight Forward Technique to solve a problem, We used to solve a
Problem through this approach when we don't have sufficient data to solve a problem in
Efficient Way.

19. What is the difference between Divide and Conquer, Decrease and Conquer?
Divide and Conquer can be solved to solve a problem with a larger data set and when there
is no dependency between any of the data sets.
 Divide and Solve as Small as Small sets.
Conquer or Merge it get one final resultant data set.
Decrease and Conquer is almost similar to Divide and Conquer but we are finding a
solutions to the problem in a different variations, EX:Decrease by Constant (Usually by
One),Decrease by Constant factor which is almost similar to Divide and Conquer
Technique(Usually by two),Decrease by Variable(The Dividing Criteria changes for each
iteration depends upon the data set.

20. Define Greedy Technique.

Greedy Technique is always applied for the problem of the type optimization type, which
reduces loss and increases profit.

21. Define Optimal and Feasible Solution.

Optimal Solution is a solution which is best among N Feasible Solution. Feasible Solution is a solution

DEPT. OF CSE-DS, ATMECE Page 26

Analysis & Design of Algorithms Laboratory BCSL404

which Satisfies a Problem Constraints/conditions.

22. Can A Problem solved by all the algorithmic Techniques.

Yes, but some problems will give better results with some Algorithmic Technique and it
may give worst result when it is applied with other technique.
23. State and Explain Knapsack Problem.

Filling the Maximum number of items to the Knapsack (Container) Which Increases the
profit and decreases the Loss.

24. Which one is Most Admired algorithmic Technique?

Dynamic Programming.

25. What is Spanning tree and Minimum Spanning tree?

A tree Without Cycles are called as Spanning tree . A Minimum Spanning Tree is a
spanning tree which yeilds the very less Cost when all the edges costsummed up.

26. How Many Spanning Tree can a Tree can have?

A tree can have 1 to many number of Possible ways of Spanning Tree.

27. Differentiate between Prims and Kruskals Algorithm for finding MST.
In Prims We consider any one vertex in the graph as Source and We compute the distance
from that source to other vertices ,after computing the vertices which has minimum value
among (n-1) vertices is added to tree vertices and that respective edges added to tree Edges
Set.The above mentioned Process continues till we reach (n-1) vertices.
In Kruskals we first arrange the edges in Ascending Order and then we start to form the tree
which wont formcycles,if adding that edges forms cycles then that edges is dropped from adding
to tree edges.The above saidprocess is continues till we reach the count of
(n-1) Vertices.

28. What is the Application of Prims and Kruskals Algorithm?

In Networks to remove the Cyclicity of the Network.

29. Explain Job Sequencing With Deadlines?

Placing or scheduling the maximum number of Jobs to a machine without violating the deadlines
constraint of any of the Jobs in Sequence.

DEPT. OF CSE-DS, ATMECE Page 27

Analysis & Design of Algorithms Laboratory BCSL404

30. Why the Name Bubble Sort named?

Because in first Pass the first highest data will bubbles up,so since the largest element
bubbles up in the first and second largest element bubbles up in the Second pass andsoon,so
hence the name bubble sort.

31. Why the Name Selection Sort?(L3)

The Selection sort is named because we initially first select an arrays first element as
minimum and will compare with other elements ,so in pass one first least element goes
to the first position and so on so forth for 2nd,3rd and so on. Selecting

32. What is the difference between Brute force strings matching to Horspool String Matching
Method? (L2)In brute Force we compare each and every element of the text to the pattern
by shifting the text position by one and in Horspool method we shift it by number of shift
positions recorded in the shift table.

33. Explain Merge Sort?

In Merge Sort will divide the entire input set by 2 until we reach low<high and later will find
a solution to each item by comparing half of the array data set to the other half array
data set and finally we merge it to form a single array(conquer)

34. What is the Basic Operations in Merge sort and Quick sort?
In Merge Sort the Basic Operations is Comparisions and in Quick sort basic Operations is
Partitioning and hence also known as partitioning sort.

35. Why the Insertion Sort?

We are Inserting an element to its suitable place by comparing n elements for each pass.

36. What is the Use of DFS and BFS?

DFS and BFS both used to check the Connectivity of a graph, Cyclicity in a graph, Spanning
tree of a graph.

37. Differentiate between DFS and BFS.

DEPT. OF CSE-DS, ATMECE Page 28

Analysis & Design of Algorithms Laboratory BCSL404

DFS and BFS are both the Graph Traversing Technique,in which DFS Traverse the Graph
in a depth wise(Vertical) and BFS Traverse the Graph from left to right(Horizontal)

38. Which Data structures used in BFS and DFS.

BFS USes Queue as its data structure and DFS uses as stack its Data structure.

39. What are back edges in DFS and Cross Edges in BFS.
Back Edges and Cross edges are the Edges which already visited by a ancestor node.

40. What is Topological Sorting?

Topological Sorting is a Sorting Technique used for sorting Vertices in the Graph.

41. What is the Conditions necessary for a Topological Sorting?

For a Topological Sorting the Graph Should be DAG(Directed Acyclic Graph)

42. What are the Different methods used to solve a topological Sorting ?
1.Source Removal Method
2.Using DFS based Scheme.

43. What is the Use of Topological Sorting?

Use of Topological Ordering is in the field of Operating System for Scheduling and in
Networks,Automation and Robotics.

44. What is Dijikstra's Algorithm?

Dijikstra's Algorithm is Used to find the Single shortest Path from source to the other vertex.
45. What is a graph?
Graph is a component which is having a set of Edges and vertices G={V,E}

46. What are the different ways that can be represents a graph?
Adjaceny Matrix and Adjacency List.

47. What is Adjacency Matrix?

Is a Matrix which illustrates the Graph in the form of Matrix,if it is a weights Graph then we
initialize the value of the cost in that position(i,j) or else simply we write 1 to mention ther
exist an edge between (i,j) OR else we use 0 or 9999 to mention non connectivity of a
graph.

DEPT. OF CSE-DS, ATMECE Page 29

Analysis & Design of Algorithms Laboratory BCSL404

48. What is the limitations of Algorithms?

Algorithm can't find the better the solutions when we come across the tight lower bound,
So we can find the better solutions which is not possible with Algorithmic way.To find the
Tight lower bound we use Decision Trees.

49. What is Tight lower Bound?

It is a Lower bound which is a best lower bound for an problem, beyond that no
algorithm will produce better results.
50. What are Decision Trees?
Decision trees are also known as Comparision Trees used to find the tight lower bound
for a particular Problem EX:Tight Lower Bound For Sorting is n.logn
and tight lower bound for Searching is logn which is not possible to get the better result.

51. What is a polynomial problem (P-type)

P-type problem are decision problems in which we can find the solutions in a
polynomial time and is of type deterministic.

52. What is NP-problem?

NP-Problem belongs to decision problem and these problems are Non Deterministic
Polynomial i.e for which the problem doesn't have deterministic solutions and Can be solved
in Polynomial time
There are 2 phases in solving a problem.
(i) Guessing(Non-Deterministic stage) Producing N number of Candidate Outputs.

(ii) Verification(Deterministic Stage) Verifying The correctness of N Number of

Candidate Outputs.

53. What is NP-Complete Problems?

Np_Complete Problems belongs to Decision problems and NP type Problems . These
problems can be find the solutions by converting or reducing to the problem which we know
the Solutions.

54. What is a trivial lower bound?

Trivial bound can be derived by formulating the number of inputs that has to be given and number
ofoutputs that has to be generated.

DEPT. OF CSE-DS, ATMECE Page 30

Analysis & Design of Algorithms Laboratory BCSL404

55. Explain Backtracking W.r.t

(I)Subset Problem (ii)N-Queens Problem

56. Explain Subset Problem.

In a given Set S ,find the Subset,in which the sum of all subset elements is equal to the sum d
which is predefined in a problem.
57. Explain N-Queens Problem.(
N-Queens Problem is of Placing a N-Queens in a N*N Chess board such that No 2- Queens
Should be placed in the same Row,Column and same diagnol(N=Should consider both
principal diagonal elements)
58. What is Hamiltonian Circuit?(L2)
Hamiltonian circuit is a problem in which that circuit starts from a source vertex and has other
vertex in any order without repeating and Should end with the Source vertex only i.e source and
Destination vertex should be same.
59. Explain the Problem of TSP.(L2)
Travelling Sales Person Problem is a problem in which he should Visit N number of cities
with a minimum number of Cost by visiting every city Exactly one and the city what he is started
should end with same city.
60. What is the Concept of Dynamic Programming?(L3)
Deriving a Solution to the basic Condition and Extracting the solutions for the rest of the other
data sets by Previously drawnd Solution.Computer to other algorithmic Technique Dynamic
Programming because it avoids lot of reworking on the same Solution what we have solved in
the earlier phases of deriving the solution to the problem.

61. What is the goal of Warshalls Algorithm?(L3)

Warshall’s algorithm is to find the shortest distance between a node to all the other nodes in
the graph.It Uses the Property of Transitive Closure i.e if there exist a path between (i,k) and
(k,j) then there surely exist a path between (i,j)
(i,k) &(k,j)---◻(I,J)What is the use of Floyds algorithm?(L3) It is
use to find the All pairs shortest Path of an Graph.

DEPT. OF CSE-DS, ATMECE Page 31