Padm. Dr. V. B.

Kolte College of Engineering, Malkapur (MS)

Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

LSSBM’s
Padm. Dr. V. B. Kolte College of Engineering Malkapur
Dist. Buldana (MS)

Laboratory Manual
Semester VI
Subject: - Design & Analysis of Algorithm
Sant Gadge Baba Amravati University Amravati

Department of
Computer Science & Engineering

Website: www.coemalkapur.ac.in

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Index
Sr.No Title Page No.

1 Vision and Mission of the Institute and Program

2 Program educational objective and program outcomes

3 Syllabus( Theory+ Practical) Course outcomes, Mapping with

Pos

4 Assessment Format i.e ACIPV(Guidelines)

5 Aim of the Lab Manual

6 List of experiment

7 a .Title/Aim

b .Software Used

c. Theory

d. UML Diagrams

e. Conclusion.

f. Quiz/Objective type question/Viva-voce

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

LSSBM’s
Padm. Dr. V. B. Kolte College of Engineering Malkapur
Dist. Buldana (MS)

CERTIFICATE

This is to certify that Mr/Miss ---------------------------------------

Enrollment No. Roll No . Section _
of B.E. (CSE) SEM-VI has satisfactorily completed the term work of
the subject Design & Analysis of Algorithm, prescribed by Sant
Gadge Baba University, Amravati during the academic term 2022- 13.

Date: Signature of the faculty

Department of Computer Sci. & Engg.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

programme Educational Objectives (PEOs)

PEO.1Graduates will work productively as computer science engineers exhibiting ethical
qualities and leadership roles in multi-disciplinary teams.

PEO.2Graduates will adapt to the changing technologies, tools and societal requirements.

PEO.3Graduates will design and deploy software that meets the needs of individuals and the
industries

PEO.4Graduates will take up higher education and/or be associated with the field so that they
can keep themselves abreast of Research & Development

Programme Outcomes (POs)

PO.1Students should be able to apply knowledge of computing and mathematics to computer
science problems.

PO.2Students should be able to analyze a problem and identify and define the computing
requirements appropriate to its solution.

PO.3Students should be able to design, implement, and evaluate a computer-based system,

process, component, or program to meet desired needs.

PO.4Students should be able to function effectively on teams to accomplish a common goal.

PO.5Students should be able to function to understand professional, ethical, legal, security and
social issues and responsibilities.

PO.6Students should be able to communicate effectively with a range of audiences.

PO.7Students should be able to analyze the local and global impact of computing on
individuals, organizations and society.

PO.8Students should be able to engage in continuing professional development.

PO.9Students should be able to use current techniques, skills and tools necessary for
computing practices.

PO.10Students should be able to apply mathematical foundations, algorithmic principles, and

computer science theory in the modeling and design of computer-based systems that
demonstrate comprehension of the trade-offs involved in design choices.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

PO.11Students should be able to apply design and development principles in the construction
of software systems of varying complexity.

Program Specific Outcomes (PSOs)

PSOs are statements that describe what the graduates of a specific engineering program should
be able to do.

PSO 1: Able to apply the knowledge gained during the course of the program from Mathematics,
Basic Computing, Basic Sciences and Social Sciences in general and all computer science
courses in particular to identify, formulate and solve real life complex engineering problems faced
in industries and/or during research work with due consideration for the public health and safety,
in the context of cultural, societal, and environmental situations.

PSO 2: Able to provide socially acceptable technical solutions to complex computer science
engineering problems with the application of modern and appropriate techniques for sustainable
development relevant to professional engineering practice.

PSO 3: Able to apply the knowledge of ethical and management principles required to work in a
team as well as to lead a team.

PSO 4: Able to design and develop hardware and software in emerging technology environments.

PSO 5: Apply standard software engineering practices and strategies in software project
development to deliver a quality product for business success.

PSO 6: Understand, analyze and develop computer programs in the areas related to algorithms,
system software, multimedia, web design, big data analytics and networking for efficient design
of computer-based systems of varying complexity.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

COURSE LEARNING OBJECTIVES (CLO)

CLO.1 1. To understand asymptotic analysis of algorithms.

CLO.2 2. To apply algorithmic strategies while solving problems.

3. Ability to analyze time and space complexity.
CLO.3
4. Demonstrate a familiarity with major algorithms.
CLO.4

COURSE OUTCOMES (CO)

On successful completion of this subject, students should be able to:

1. Carry out the analysis of various Algorithms for mainly Time

CO.1
complexity.
2. Apply design principles and concepts to algorithm design.
CO.2
3. Understand different algorithmic design strategies.
CO.3

CO.4
4. Analyze the efficiency of algorithms using time complexity.
CO.5
5. Apply the standard sorting algorithms.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Aim of the Lab manual

This manual is designed for the Third Year (6th Semester) students of CSE. The main aim
this Manual is to provide guidelines to faculty for proper conduction of lab sessions. It has been
prepared as per university curriculum & covers various aspects of Operating System; it is Core
Subject CSE, in this practical student able to understand the design and analysis of algorithms.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Department of Computer Science &Engineering

List of Experiments
2023-24

Subject: Design & Analysis of Algorithm

Semester VI

Exp.
EXPERIMENT CO Mapping PO Mapping
No.
DESCRIPTION
1. Introduction to Algorithms. CO1, CO4 PO1, PO2

2. Write a C program to generate Fibonacci series using loops. CO2, CO3, CO5 PO5, PO12

3. Write a C program to implement Insertion Sort Algorithm CO3, CO4 CO5 PO1, PO12

4. Write a C program to implement Quick Sort Algorithm. CO3, CO4, CO5 PO1, PO5, PO12

5. Write a C program to implement Merge Sort Algorithm. CO3, CO4, CO5 PO4, PO5

6. Write a C program to implement Prim’s Algorithm of Minimum CO3 PO12

spanning tree
7. Write a C program to implement Kruskal’s Algorithm of Minimum CO3 PO1, PO5
spanning
tree
8. Write a C program to implement Dijkstra’s Algorithm. CO3, CO5 PO1, PO12

9. Write a C program to implement Floyd’s Algorithm. CO3, CO5 PO4

10 Explain Breadth First Search algorithm and Implement program for CO2 PO12
it.
List of Experiments beyond Syllabus

1 Explain Depth First Search algorithm and Implement C program CO1, CO2 PO5, PO12
for it.
2 Implement C program N Queen‟s problem using Back Tracking CO1, CO3 PO1, PO5, PO12

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Practical Plan for Batch A

Exp Proposed Covered

EXPERIMENT DESCRIPTION
. Date Date
No.
1. Introduction to Algorithms.

2. Write a C program to generate Fibonacci series using loops.

3. Write a C program to implement Insertion Sort Algorithm

4. Write a C program to implement Quick Sort Algorithm.

5. Write a C program to implement Merge Sort Algorithm.

6. Write a C program to implement Prim’s Algorithm of Minimum

7. Write a C program to implement Kruskal’s Algorithm of

Minimum
8. Write a C program to implement Dijkstra’s Algorithm.

9. Write a C program to implement Floyd’s Algorithm.

10 Explain Breadth First Search algorithm and Implement C

program for it.
11 Explain Depth First Search algorithm and Implement C program

for it.
12 Implement C program N Queen‟s problem using Back Tracking

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Practical Plan for Batch B

Exp Propose Covered

EXPERIMENT DESCRIPTION
. dDate Date
No.
1. Introduction to Algorithms.

2. Write a C program to generate Fibonacci series using loops.

3. Write a C program to implement Insertion Sort Algorithm

4. Write a C program to implement Quick Sort Algorithm.

5. Write a C program to implement Merge Sort Algorithm.

6. Write a C program to implement Prim’s Algorithm of Minimum

7. Write a C program to implement Kruskal’s Algorithm of

Minimum
8. Write a C program to implement Dijkstra’s Algorithm.

9. Write a C program to implement Floyd’s Algorithm.

10 Explain Breadth First Search algorithm and Implement C

program for it.
11 Explain Depth First Search algorithm and Implement C program
for it.
12 Implement C program N Queen‟s problem using Back Tracking

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 01

1. AIM: Introduction to Algorithms.

2. OBJECTIVE: To Study the details of algorithms

3. THEORY:

Definition of Algorithm:
Algorithm is defined as a collection of unambiguous instructions occurring in some
specific sequence and such an algorithm should produce output for given set of input in
finite amount of time.

1. What is an Algorithm?
 A clearly specified set of simple instructions to be followed to solve a problem.
 Takes a set of values, as input and produces a value, or set of values, as output
 May be specified in English as a computer program or as a pseudo code.

2. Data structures

 Methods of organizing data.

3. Program = algorithms + data structures

4. Why we need algorithm analysis?

 Writing a working program is not good enough,
 The program may be inefficient.
 If the program is run on a large data set, then the running time becomes an issue.

Algorithm Analysis

We only analyze correct algorithms/programs. An algorithm is correct if, for every input
instance, it halts with the correct output. Incorrect algorithms might not halt at all on some
input instances might halt with other than the desired answer.

Analyzing an algorithm includes predicting the resources that the algorithm requires.

Resources include-
 Memory.
 Communication bandwidth.
 Computational time (usually most important).

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Factors affecting the running time

Computer
Compiler
Algorithm used
Input to the algorithm.

The content of the input affects the running time typically, the input size (number of
items in the input) is the main consideration.

Ex: Sorting problem: - The number of items to be sorted

Ex: Multiply two matrices together: - The total number of elements in the two matrices.
Machine model assumed
Instructions are executed one after another, with no concurrent operations i.e. not
parallel computers.

Time complexity can be classified as:

Worst-case running time of an algorithm.

 The longest running time for any input of size n.

 An upper bound on the running time for any input.
 Guarantee that the algorithm will never take longer.
 The worst case can occur fairly often.
Example: Sort a set of numbers in increasing order; and the data is in decreasing
order.
 Example: In searching a database for a particular piece of information.

Best-case running time of an algorithm.

 The shortest running time for any input of size n.
 A lower bound on the running time for any input.
Example: Sort a set of numbers in increasing order; and the data in already in
increasing order.

Average case running time of an algorithm.

 May be difficult to define what “average” means, usually it is taken as average of

best and worst values.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

4. CONCLUSION:

Thus we have studied the Algorithm and its Analysis successfully.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 02

1. AIM: Write a C program to generate Fibonacci series using loops.

2. OBJECTIVE: To implement the C program for Fibonacci series using loops .

3. THEORY:

Fibonacci Series
In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the
numbers in the following integer sequence. By definition, the first two numbers in the
Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous
two.

Algorithm:

1. Declare the necessary variables for the loop and range of the Fibonacci series.
2. Print the first two numbers i.e. 0 and 1.
3. Calculate the subsequent series numbers using the for loop.
4. Display the Fibonacci series.
5. Stop.

PROGRAM:

/*
* C Program to print fibonacci series using recursion
*/
#include <stdio.h>
#include <conio.h>

int fibonacci(int term);

int main(){
int terms, counter;
printf("Enter number of terms in Fibonacci series: ");
scanf("%d", &terms);
/*
* Nth term = (N-1)th therm + (N-2)th term;
*/
printf("Fibonacci series till %d terms\n", terms);
for(counter = 0; counter < terms; counter++){
printf("%d ", fibonacci(counter));
}

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

getch();
return 0;
}
/*
* Function to calculate Nth Fibonacci number
* fibonacci(N) = fibonacci(N - 1) + fibonacci(N - 2);
*/
int fibonacci(int term){
/* Exit condition of recursion*/
if(term < 2)
return term;
return fibonacci(term - 1) + fibonacci(term - 2);
}

Output:

Enter number of terms in Fibonacci series: 9

Fibonacci series till 9 terms
0 1 1 2 3 5 8 13 21

5. CONCLUSION:
Hence the program is successfully executed.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 03

1. AIM: Write a C program to implement Insertion Sort Algorithm

2. OBJECTIVE: To understand and implement the insertion sort algorithm.

3. THEORY:

It’s a sorting algorithm used to sort the elements.

Algorithm:

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Program:

#include<stdio.h>

#include<conio.h>

int main() {

int i, j, num, temp, arr[20];

clrscr();

printf("Enter total elements: ");

scanf("%d", &num);

printf("Enter %d elements: ", num);

for (i = 0; i < num; i++) {

scanf("%d", &arr[i]);

for (i = 1; i < num; i++) {

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

temp = arr[i];

j = i - 1;

while ((temp < arr[j]) && (j >= 0)) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = temp;

printf("After Sorting: ");

for (i = 0; i < num; i++) {

printf("%d ", arr[i]);

getch();

return 0;

Output:

Enter total elements: 5

Enter 5 elements: 5 3 7 2 1

After Sorting: 1 2 3 5 7

5. CONCLUSION:

Hence we successfully studied and implement the insertion sort algorithm.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 04

1. AIM: Write a C program to implement Quick Sort Algorithm.

2. OBJECTIVE: To study and implement the quick sort algorithm.

3. THEORY:

Quick Sort

Quicksort is a divide-and-conquer sorting routine where a pivot element is selected

to partition the array into two (possibly unequal or even empty) sub-arrays positioning the
pivot element in the proper sorted location. The algorithm then recurseson both sub-
arrays performing the same procedure. Since each step places the pivot element into its
final location, there is no combine step needed.

Partitioning

The key to the quick-sort routine is selecting a pivot element and then moving all values
less than the pivot to the front of the sub-array, all the values greater than the pivot to the
back of the sub-array, and then inserting the pivot element between the two parts (which is
its sorted position). One simple way to select the pivot element is to simply take thelast
element in the subarray.
After moving smaller elements to the front and inserting the pivot into its correct location,
the sub-array will have the following structure Note that while the pivot elementis in the
correct final location, the two other pieces are not sorted. Since the loop runs from p to r-1
(which for the initial call is 1 and n-1) and all other statements have constant run time, the
total run time for PARTITION() is O(n).

The basic concept is to pick one of the elements in the array as a pivot value around which
the other elements will be rearranged. Everything less than the pivot is moved left of the
pivot (into the left partition). Similarly, everything greater than the pivot goes into the right
partition. At this point each partition is recursively quick sorted.

The Quick sort algorithm is fastest when the median of the array is chosen as the pivot
value. That is because the resulting partitions are of very similar size. Each partition splits
itself in two and thus the base case is reached very quickly.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Figure: Quicksort on a random array

In practice, the Quick sort algorithm becomes very slow when the array passed to it is
already close to being sorted. Because there is no efficient way for the computer to find the
median element to use as the pivot, the first element of the array is used as the pivot. So
when the array is almost sorted, quick sort doesn't partition it equally. Instead, the partitions
are asymmetrical like in Figure 4.2. This means that one of the recursion branches is much
deeper than the other, and causes execution time to go up. Thus, it is said that the more
random the arrangement of the array, the faster the quick sort Algorithm finishes.

Quick sort works by partitioning a given array A[p . . r] into two nonempty sub array
A[p. . q] and A[q+1 . . r] such that every key in A[p . . q] is less than or equal to every
key in A[q+1 . . r]. Then the two sub arrays are sorted by recursive calls to Quick sort. The
exact position of the partition depends on the given array and index q is computed as a part
of the partitioning procedure.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Algorithm Quicksort (p, q)

// Sorts the elements a[p],……,a[q] which reside in the global array a[1 : n] into
ascending order.
{
if( p < r) then // if there are more than one element
{
// divide P into two sub problems
j=Partition (a, p,q+1);
// j is the position of the partitioning element
// solve the sub problems
QuickSort (p, j 1)
;
QuickSort (j + 1, q);
}
}
As a first step, Quick Sort chooses as pivot one of the items in the array to be sorted. Then
array is then partitioned on either side of the pivot. Elements that are less than or equal to
pivot will move toward the left and elements that are greater than or equal to pivot will
move toward the right.

Partitioning the Array

Partitioning procedure rearranges the sub arrays inplace.
Algorithm Partition (a, m, p)
// Within a[m],a[m+1],….,a[p1]
the elements are rearranged in such a manner that if
initially t=a[m] then after completion a[q]=t for some q between m and p1,
a[k] |<=t for
m<=k<q, and a[k]>=t for q<k<p. q is returned. Set a[p]= ∞.
{
v = a[m]; i=m; j=p;
repeat
{
repeat i=i+1;
until a[i] >=v;
repeat j = j1;
until a[j] <=v;
if i < j then exchange A[i] ↔ A[j]
} until ( i>= j);
a[m]=a[j]; a[j]=v; return j;
}

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

26
Partition selects the first key, a[p] as a pivot key about which the array will
partitioned
Keys ≤ a[p] will be moved towards the left.
Keys ≥ a[p] will be moved towards the right.

PROGRAM:
/*c program for quick sorting*/
#include<stdio.h>
#include<conio.h>
void qsort(int arr[20], int fst, int last);
int main()
{
int arr[30];
int i,size;
printf("Enter total no. of the elements : ");
scanf("%d",&size);
printf("Enter total %d elements : \n",size);
for(i=0; i<size; i++)
scanf("%d",&arr[i]);
qsort(arr,0,size-1);
printf("Quick sorted elements are as : \n");
for(i=0; i<size; i++)
printf("%d\t",arr[i]);
getch();
return 0;
}
void qsort(int arr[20], int fst, int last)
{
int i,j,pivot,tmp;
if(fst<last)
{
pivot=fst;
i=fst;
j=last;
while(i<j)
{
while(arr[i]<=arr[pivot] && i<last)
i++;
while(arr[j]>arr[pivot])
j--;
if(i<j)
{

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
tmp=arr[pivot];
arr[pivot]=arr[j];
arr[j]=tmp;
qsort(arr,fst,j-1);
qsort(arr,j+1,last);
}
}

Output -

Enter total no. of the elements : 5

Enter total -28787 elements :
Quick sorted elements are as :
Enter total no. of the elements : 5
Enter total 5 elements :
76134
Quick sorted elements are as:
1 3 4 6 7

5. CONCLUSION:

Quick sort algorithm is used to sort the elements successfully .

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 05

1. AIM: Write a C program to implement Merge Sort Algorithm.

2. OBJECTIVE: To study and implement the merge sort algorithm.

3. THEORY:

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

PROGRAM:

#include<stdio.h>

void mergesort(int a[],int i,int j);

void merge(int a[],int i1,int j1,int i2,int j2);

int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:");

for(i=0;i<n;i++)
scanf("%d",&a[i]);

mergesort(a,0,n-1);

printf("\nSorted array is :");

for(i=0;i<n;i++)
printf("%d ",a[i]);

return 0;
}

void mergesort(int a[],int i,int j)

{
int mid;

if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays

}
}

void merge(int a[],int i1,int j1,int i2,int j2)

{
int temp[50]; //array used for merging
int i,j,k;
i=i1; //beginning of the first list
j=i2; //beginning of the second list
k=0;

while(i<=j1 && j<=j2) //while elements in both lists

{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}

while(i<=j1) //copy remaining elements of the first list

temp[k++]=a[i++];

while(j<=j2) //copy remaining elements of the second list

temp[k++]=a[j++];

//Transfer elements from temp[] back to a[]

for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}

Output

Enter Number of Element 5

Enter array element 7 5 9 4 1
Sorted array is 1 4 5 7 9

4. CONCLUSION:

Successfully implement the merge sort algorithm in C.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 06

1. AIM: Write a C program to implement Prim’s Algorithm of Minimum spanning tree.

2. OBJECTIVE: To analyze and implement the Prim’s algorithm.

3. THEORY:

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

4. PROGRAM:

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

5. CONCLUSION

Successfully studied and execute the Prim’s algorithm.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 07

1 AIM: Write a C program to implement Kruskal’s Algorithm of Minimum spanning tree

2. OBJECTIVE: To study and implement the Kruskal’s Algorithm

3. THEORY:

Program:

#include<stdio.h>

#include<conio.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);

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

void main()

clrscr();

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)

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

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

getch();

int find(int i)

while(parent[i])

i=parent[i];

return i;

int uni(int i,int j)

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

if(i!=j)

parent[j]=i;

return 1;

return 0;

Output:

Enter the no. of vertices:6

Enter the cost adjacency matrix:

031600

305030

150564

605002

306006

004260

The edges of Minimum Cost Spanning Tree are

1 edge (1,3) =1

2 edge (4,6) =2

3 edge (1,2) =3

4 edge (2,5) =3

5 edge (3,6) =4

Minimum cost = 13

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

5. CONCLUSION

Successfully studied and execute the Kruskal’s algorithm.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 08

1. AIM: Write a C program to implement Dijkstra’s Algorithm.

2. OBJECTIVE: To implement the Dijkstra’s Algorithm.

3. THEORY:

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

4. PROGRAM:
#include<stdio.h>

#include<conio.h>

#define INFINITY 9999

#define MAX 10

void dijikstra(int G[MAX][MAX], int n, int startnode);

void main(){

int G[MAX][MAX], i, j, n, u;

clrscr();

printf("\nEnter 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", &G[i][j]);

printf("\nEnter the starting node:: ");

scanf("%d", &u);

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

dijikstra(G,n,u);

getch();

void dijikstra(int G[MAX][MAX], int n, int startnode)

int cost[MAX][MAX], distance[MAX], pred[MAX];

int visited[MAX], count, mindistance, nextnode, i,j;

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

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

if(G[i][j]==0)

cost[i][j]=INFINITY;

else

cost[i][j]=G[i][j];

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

distance[i]=cost[startnode][i];

pred[i]=startnode;

visited[i]=0;

distance[startnode]=0;

visited[startnode]=1;

count=1;

while(count < n-1){

mindistance=INFINITY;

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

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

if(distance[i] < mindistance&&!visited[i])

mindistance=distance[i];

nextnode=i;

visited[nextnode]=1;

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

if(!visited[i])

if(mindistance+cost[nextnode][i] < distance[i])

distance[i]=mindistance+cost[nextnode][i];

pred[i]=nextnode;

count++;

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

if(i!=startnode)

printf("\nDistance of %d = %d", i, distance[i]);

printf("\nPath = %d", i);

j=i;

do

j=pred[j];

printf(" <-%d", j);

Prepared By: Asst. Prof. M. R. Rajput
 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

while(j!=startnode);

Output:

Enter the no. of vertices:: 4

Enter the adjacency matrix::

0111

1010

1101

1010

Enter the starting node:: 1

Distance of 0 = 1

Path = 0 <-1

Distance of 2 = 1

Path = 2 <-1

Distance of 3 = 2

Path = 3 <-0 <-1

5. CONCLUSION:

Successfully studied and execute the Dijkastr’s algorithm.

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 09

1. AIM: Write a C program to implement Floyd’s Algorithm.

2. OBJECTIVE: To implement Floyd’s Algorithm.

3. THEORY:

Prepared By: Asst. Prof. M. R. Rajput

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

4. Program
5. #include<stdio.h>
6.#include<conio.h>
7. int min(int,int);
8. void floyds(int p[10][10],int n) {
9. int i,j,k;
10. for (k=1;k<=n;k++)
11. for (i=1;i<=n;i++)
12. for (j=1;j<=n;j++)
13. if(i==j)
14. p[i][j]=0; else
15. p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
16. }
17. int min(int a,int b) {
18. if(a<b)
19. return(a); else
Prepared By: Asst. Prof. Smita B. Zanke
 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

20. return(b);
21. }
22. void main() {
23. int p[10][10],w,n,e,u,v,i,j;
24. ;
25. clrscr();
26. printf("\n Enter the number of vertices:");
27. scanf("%d",&n);
28. printf("\n Enter the number of edges:\n");
29. scanf("%d",&e);
30. for (i=1;i<=n;i++) {
31. for (j=1;j<=n;j++)
32. p[i][j]=999;
33. }
34. for (i=1;i<=e;i++) {
35. printf("\n Enter the end vertices of edge%d with its weight \n",i);
36. scanf("%d%d%d",&u,&v,&w);
37. p[u][v]=w;
38. }
39. printf("\n Matrix of input data:\n");
40. for (i=1;i<=n;i++) {
41. for (j=1;j<=n;j++)
42. printf("%d \t",p[i][j]);
43. printf("\n");
44. }
45. floyds(p,n);
46. printf("\n Transitive closure:\n");
47. for (i=1;i<=n;i++) {
48. for (j=1;j<=n;j++)
49. printf("%d \t",p[i][j]);
50. printf("\n");
51. }
52. printf("\n The shortest paths are:\n");
53. for (i=1;i<=n;i++)
54. for (j=1;j<=n;j++) {
55. if(i!=j)
56. printf("\n <%d,%d>=%d",i,j,p[i][j]);
57. }
58. getch();
59. }

CONCLUSION: Thus the Floyd’s Algorithm is verified and implement successfully.

Prepared By: Asst. Prof. Smita B. Zanke

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 10

1. AIM: Write a C program to implement Breadth First Search Algorithm.

2. OBJECTIVE: To implement the Breadth First Search Algorithm.
3. THEORY: BFS is an algorithm for traversing or searching tree or graph data structures. It starts
at the tree root, and explores all of the neighbour nodes at the present depth prior to moving on to the
nodes at the next depth level. The aim of BFS algorithm is to traverse the graph as close as possible to
the root node. Queue is used in the implementation of the breadth first search.
Steps : 1. Push the root
node in the Queue.
2. Loop until the queue is empty.
3. Remove the node from the Queue.
4. If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in

Example :

Program

1. #include<stdio.h>
2. #include<conio.h>
3. int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
4. void bfs(int v) {
5. for (i=1;i<=n;i++)
6. if(a[v][i] && !visited[i])
7. q[++r]=i;

Prepared By: Asst. Prof. Smita B. Zanke

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

8. if(f<=r) {
9. visited[q[f]]=1;
10. bfs(q[f++]);
11. }
12. }
13. void main() {
14. int v;
15. clrscr();
16. printf("\n Enter the number of vertices:");
17. scanf("%d",&n);
18. for (i=1;i<=n;i++) {
19. q[i]=0;
20. visited[i]=0;
21. }
22. printf("\n Enter graph data in matrix form:\n");
23. for (i=1;i<=n;i++)
24. for (j=1;j<=n;j++)
25. scanf("%d",&a[i][j]);
26. printf("\n Enter the starting vertex:");
27. scanf("%d",&v);
28. bfs(v);
29. printf("\n The node which are reachable are:\n");
30. for (i=1;i<=n;i++)
31. if(visited[i])
32. printf("%d\t",i); else
33. printf("\n Bfs is not possible");
34. getch();
35. }

Output
Enter the number of vertices 3 Enter graph data in matrix form: 2 4 5 2 3 4 1 7 8
Enter the starting vertex: 2 The node which are reachable are: 1 2 3
Result: In this way we have studied and implemented BFS algorithm.

Prepared By: Asst. Prof. Smita B. Zanke

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 11

1. AIM: Write a C program to implement Depth First Search Algorithm.

2. OBJECTIVE: To implement the Depth First Search Algorithm..
3. THEORY: DFS is traversing or searching tree or graph data structures algorithm. The algorithm
starts at the root node and explores as far as possible or we find the goal node or the node which
has no children. It then backtracks from the dead end towards the most recent node that is yet to
be completely unexplored. DFS uses Depth wise searching . DFS data structure uses stack . In DFS,
the edges that leads to an unvisited node are called discovery edges while the edges that leads to an
already visited node are called block edges.
Steps for searching 1. Push the root node in the Stack.
2. Loop until stack is empty.
3. Peek the node of the stack.
4. If the node has unvisited child nodes, get the unvisited child node, mark it as traversed and push
it on stack.
If the node does not have any unvisited child nodes, pop the node from the stack. Adjacency Matrix
It is a two dimensional array with Boolean flags.
As an example, we can represent the edges for the
above graph using the following adjacency matrix.
 n by n matrix, where n is number of vertices
 A[m,n] = 1 iff (m,n) is an edge, or 0 otherwise
 For weighted graph: A[m,n] = w (weight of edge), or positive infinity otherwise Advantages of Adjacency
Matrix
 Adjacency matrix representation of graph is very simple to implement.
 Adding or removing time of an edge can be done in O(1) time. Same time is required to check, if there is an
edge between two vertices.
 It is very convenient and simple to program. Disadvantages of Adjacency Matrix
 It consumes huge amount of memory for storing big graphs.
 It requires huge efforts for adding or removing a vertex. If you are constructing a graph in dynamic
structure, adjacency matrix is quite slow for big graphs.

Prepared By: Asst. Prof. Smita B. Zanke

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

Example

1. #include<stdio.h>
2. #include<conio.h>
3. int a[20][20],reach[20],n;
4. void dfs(int v) {
5. int i;
6. reach[v]=1;
7. for (i=1;i<=n;i++)
8. if(a[v][i] && !reach[i]) {
9. printf("\n %d->%d",v,i);
10. dfs(i);
11. }
12. }
13. void main() {
14. int i,j,count=0;
15. clrscr();
16. printf("\n Enter number of vertices:");
17. scanf("%d",&n);
18. for (i=1;i<=n;i++) {
19. reach[i]=0;
20. for (j=1;j<=n;j++)
21. a[i][j]=0;
22. }
23. printf("\n Enter the adjacency matrix:\n");
24. for (i=1;i<=n;i++)
25. for (j=1;j<=n;j++)
26. scanf("%d",&a[i][j]);
27. dfs(1);
28. printf("\n");
29. for (i=1;i<=n;i++) {
30. if(reach[i])
31. count++;
Prepared By: Asst. Prof. Smita B. Zanke
 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

32. }
33. if(count==n)
34. printf("\n Graph is connected"); else

35. printf("\n Graph is not connected");

36. getch();

Output

Enter number of vertices: 5 Enter the adjacency matrix:

0
Prepared By: Asst. Prof. Smita B. Zanke
 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

1->

2 1->

3 1->

4 1->

5 Graph is connected

Result: In this way we have studied and implement DFS algorithm.

Prepared By: Asst. Prof. Smita B. Zanke

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

EXPERIMENT NO: 12

1. AIM: Write a C program to implement N queen problem using Back Tracking.

2. OBJECTIVE: To implement the N queen problem using Back Tracking
3. Theory:
Backtracking is kind of solving a problem by trial and error. However, it is a well-organized trial
and error. We make sure that we never try the same thing twice. We also make sure that if the
problem is finite we will eventually try all possibilities (assuming here is enough computing
power to try all possibilities). Backtrack approach Requires less than m trials to determine the
solution Form a solution (partial vector) and check at every step if this has any chance of success.
If the solution at any point seems not promising, ignore it. If the partial vector (x1, x2,. . . , xi)
doesnot yield an optimal solution, ignore mi+1 ∙ ∙∙mn possible test vectors even without looking at
them. 8 queen’s problem Place eight Queens on an 8 × 8 chessboard so that no Queen attacks another
Queen Identify data structures to solve the problem First pass: Define the chessboard to be an 8 × 8
arraySecond pass: Since each queen is in a different row, define the chessboard solution to be an 8
tuple.(x1, . . . , x8), where xi is the column for ith queen Identify explicit constraints Explicit
constraints using 8 tuple formulation are Si = {1, 2, 3, 4, 5, 6, 7,8}, 1 <= i <= 8 Solution space of 88
8tuples
Identify implicit constraints No two xi can be the same, or all the queens must be in different
columns
All solutions are permutations of the 8tuple (1, 2, 3, 4, 5, 6, 7, 8) Reduces the size of solution space
from 88 to 8! Tuples No two queens can be on the same diagonal The solution above is expressed
as an 8 tuple as 4, 6, 8, 2, 7, 1, 3, 5

Prepared By: Asst. Prof. Smita B. Zanke

 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

The Backtracking Algorithm for n Queens.

Problem: Position n queens on a chessboard so that no two are in the same row, column, or diagonal.
Inputs: positive integer n.
Outputs: all possible ways n queens can be placed on an n x n chessboard so that no two queens threaten each
other.
Each output consists of an array of integers col indexed from 1 to n, where col[i] is the column
where the queen in the ith row is placed. Algorithm N Queens ( k, n) //Prints all Solution to the n-queens problem
{ for i := 1 to n do { if Place (k, i) then
{ x[k] := i; if ( k = n)
then write ( x [1 : n] else NQueens ( k+1, n); } } }
Algorithm Place (k, i) { for j := 1 to k-1 do if (( x[ j ] =
// in the same column or (Abs( x [ j ] - i) =Abs ( j – k )))
// or in the same diagonal then return false; return true; }
Program

1. #include<stdio.h>
2. #include<conio.h>
3. #include<math.h>
4. int a[30],count=0;
5. int place(int pos) {
6. int i;
7. for (i=1;i<pos;i++) {
8. if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
9. return 0;
10. }
Prepared By: Asst. Prof. Smita B. Zanke
 Padm. Dr. V. B. Kolte College of Engineering, Malkapur (MS)
Department of Computer Science & Engineering Lab Manual: Design & Analysis of Algorithm, Semester 6th

11. return 1;
12. }
13. void print_sol(int n) {
14. int i,j;
15. count++;
16. printf("\n\nSolution #%d:\n",count);
17. for (i=1;i<=n;i++) {
18. for (j=1;j<=n;j++) {
19. if(a[i]==j)
20. printf("Q\t"); else
21. printf("*\t");
22. }
23. printf("\n");
24. }
25. }
26. void queen(int n) {
27. int k=1;
28. a[k]=0;
29. while(k!=0) {
30. a[k]=a[k]+1;
31. while((a[k]<=n)&&!place(k))
32. a[k]++;
33. if(a[k]<=n) {
34. if(k==n)
35. print_sol(n); else {
36. k++;
37. a[k]=0;
38. }
39. } else
40. k--;
41. }
42. }
43. void main() {
44. int i,n;
45. clrscr();
46. printf("Enter the number of Queens\n");
47. scanf("%d",&n);
48. queen(n);
49. printf("\nTotal solutions=%d",count);
50. getch();

Result: In this way we have implemented N Queen‟s problem using Back Tracking

Prepared By: Asst. Prof. Smita B. Zanke