Silver Oak College of Engineering & Technology

GUJARAT TECHNOLOGICAL UNIVERSITY

BACHELOR OF ENGINEERING

ANALYSIS AND DESIGN OFALGORITHMS

(3150703)
5th SEMESTER

COMPUTER ENGINEERING

Laboratory Manual
Laboratory Manual
DEPARTMENT OF COMPUTER ENGINEERING

VISION
To be recognized for the quality education and research in the field of Information Technology
known for its accomplished graduates.
MISSION
The mission of Information Technology Department, Silver Oak College of Engineering and
Technology, Ahmedabad is to:
1. Continually improve the standard of our graduates by engaging in innovative teaching
learning methods with high caliber motivated faculty members keeping in-line with the rapid
technological advancements.
2. Promote and support research activities over a wide range of academic interests among
students and staff for growth of individual knowledge and continuous learning.
3. Provide an education system that promotes innovation, creativity, entrepreneurial spirit,
leadership as well as freedom of thought with emphasis on professionalism and ethical
behavior

Program Educational Objectives (PEO):

PEO1: To provide fundamental knowledge of science and engineering for an IT professional and
equipped with proficiency of mathematical foundations and algorithmic principles and inculcate
competent problem-solving ability
PEO2: To implant ability in creativity & design of IT systems and transmit knowledge and skills to
analyze, design, test and implement various software applications
PEO3: To exhibit leadership capability, triggering social and economical commitment and inculcate
community services
PEO4: To inculcate professional-social ethics, teamwork in students and acquaint them with
requisite technical and managerial skills to attain a successful career.

PROGRAM OUTCOMES (POs)

Engineering Graduates will be able to:

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals,

and an engineering specialization to the solution of complex engineering problems.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of
the engineering practice.
9. Individual and team work: Function effectively as an individual, and as a member or leader in
diverse teams, and in multidisciplinary settings.
10. 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.
11. 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.
12. 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.

ANALYSIS AND DESIGN OF ALGORITHMS PRACTICAL BOOK

DEPARTMENT OF COMPUTER ENGINEERING

PREFACE

It gives us immense pleasure to present the first edition of Analysis and Design of
Algorithms Practical Book for the B.E. 3rd year students for SILVER OAK GROUP OF
INSITUTES.

The Analysis and Design of Algorithms theory and laboratory course at SILVER OAK
COLLEGE OF ENGINEERING & TECHNOLOGY, AHMEDABAD is designed in such a
way that students develop the basic understanding of the subject in the theory classes and then try
their hands on the experiments to realize the various devices and circuits learnt during the
theoretical sessions. The main objective of the ADA laboratory course is: Learning ADA through
algorithm. The objective of this ADA Practical Book is to provide a comprehensive source for all
the experiments included in the ADA laboratory course.

We acknowledge the authors and publishers of all the books which we have consulted
while developing this Practical book. Hopefully this Analysis and Design of Algorithms Practical
Book will serve the purpose for which it has been developed.

Lab Manual Revised By: Prof. Nirzari Patel, Silver Oak College of Engineering and Technology

Lab Manual Revision No. : SOCET_3150703_LM_2020_1

Instructions to Students
1. Be prompt in arriving to the laboratory and always come well prepared for the experiment.
2. Students are instructed to remove your shoes and shocks outside the lab. Also don’t keep your bags
on the table.
3. Students need to maintain a proper decorum in the computer lab. Students must use the equipment
with care. Any damage is caused is punishable.
4. Students are instructed to come to lab in formal dresses only.
5. Students are supposed to occupy the systems allotted to them and are not supposed to talk or make
noise in the lab.
6. Students are required to carry their Lab Manual with completed practical while entering the lab.
7. Lab Manual need to be submitted every week.
8. Students are not supposed to use pen drives in the lab. The grades for the Analysis and Design of
Algorithms Practical course work will be awarded based on your performance in the laboratory,
regularity, recording of experiments in the Analysis and Design of Algorithms Practical Final Book,
lab quiz, regular viva-voce and end - term examination.
9. Find the answers of all the questions mentioned under the section ‘Solve the below mention
questionnaires’ at the end of each experiment in the Analysis and Design of Algorithms Practical
Book.
10. At the end of the lab, shut-down the computers, switch off power supply and put chairs properly.
CERTIFICATE

This is to certify that Mr./Ms ghhfyuu

with enrollment. No nutjuntut from Semester untut. Div nutun has

successfully completed his/her laboratory experiments in the Analysis and

Design Of Algorithms (3150703) from the department of nurrun

during the academic year 2020-2021.

Date of Submission:......................... Staff In charge:...........................

Head of Department:...........................................
TABLE OF CONTENT

Page No Mar
S Date Date of
Experiment Title Sign ks
r of Completi
(out
. Star on
T Fro of
N t
o m 10)
o
Implementation and Time 1 7
analysis of sorting
algorithms.
1
a) Bubble sort,
b) Selection sort,
c) Insertion sort.
Implementation and Time 8 16
analysis of sorting
algorithms.
2
a) Merge sort
b) Quick sort.
Implementation and Time 1 22
3 analysis of linear and 7
binary search algorithm.
Implementation of max- 2 27
4 heap sort algorithm. 3
Implementation of a knapsack 2 31
5 problem using dynamic 8
programming.
3 35
Implementation of chain
6 matrix multiplication using 2
dynamic programming.
Implementation of making a 3 38
change problem using 6
7
dynamic programming.
Page No
Mar
S Date Date of
Experiment Title Sign ks
r of Completi
(out
. Star on
T Fro of
N t
o m 10)
o

Implementation of a 3 44
knapsack problem using 9
8
greedy algorithm.

4 50
Implementation of Graph
9 and Searching (DFS) 5

5 57
Implementation of Graph 1
1 and Searching (BFS)
0
5 62
1 Implement prim’s algorithm. 8
1
6 68
1 Implement kruskal’s 3
2 algorithm.
PRACTICAL SET - 1
AIM: Implementation and Time analysis of different sorting algorithms.

Bubble Sort:

Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form
of an array with n number of elements. Bubble Sort compares all the element one by one and sort
them based on their values.

If the given array has to be sorted in ascending order, then bubble sort will start by comparing the
first element of the array with the second element, if the first element is greater than the second
element, it will swap both the elements, and then move on to compare the second and the third
element, and so on. If we have total n elements, then we need to repeat this process for n-1 times.

It is known as bubble sort, because with every complete iteration the largest element in the given
array, bubbles up towards the last place or the highest index, just like a water bubble rises up to
the water surface.

Sorting takes place by stepping through all the elements one-by-one and comparing it with the
adjacent element and swapping them if required.

Implementing Bubble Sort Algorithm

Following are the steps involved in bubble sort (for sorting a given array in ascending order):
1. Starting with the first element (index = 0), compare the current element with the next
element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, move to the next element. Repeat Step 1.

Complexity Analysis of Bubble Sort

Following are the Time and Space complexity for the Bubble Sort algorithm.
● Worst Case Time Complexity [ Big-O ]: O(n2)
● Best Case Time Complexity [Big-omega]: O(n)
● Average Time Complexity [Big-theta]: O(n2)
● Space Complexity: O(1)
AIM 1.1: Write a program to implement Bubble
sort. Code:

#include<stdio.h>

void main(){
int arr[]={80,70,50,90,10,45,20,15,55,60};
int k=0,i=0,j=0;
for(k=0;k<10;k++){
printf("%d ",arr[k]);
}
printf("\n");
for(i=0;i<10;i++){
for(j=0;j<10-i;j++){
if(arr[j]>arr[j+1]){
int swp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=swp;
}
}
}
k=0;
for(k=0;k<10;k++){
printf("%d ",arr[k]);
}

}
Output:
80 70 50 90 10 45 20 15 55 60

10 15 20 40 45 50 55 60 70 80
Selection Sort:

Selection sort is conceptually the simplest sorting algorithm. This algorithm will first find
the smallest element in the array and swap it with the element in the first position, then it will
find the second smallest element and swap it with the element in the second position, and it will
keep on doing this until the entire array issorted.
It is called selection sort because it repeatedly selects the next-smallest element and swaps it into
the right place.

Implementing Selection Sort Algorithm

Following are the steps involved in selection sort (for sorting a given array in ascending order):

1. Starting from the first element, we search the smallest element in the array, and replace itwith
the element in the first position.
2. We then move on to the second position, and look for smallest element present in
the subarray, starting from index 1, till the last index.
3. We replace the element at the second position in the original array, or we can say at thefirst
position in the subarray, with the second smallest element.
4. This is repeated, until the array is completelysorted.

Complexity Analysis of Selection Sort

The following will be the time and space complexity for selection sort algorithm:
● Worst Case Time Complexity [ Big-O ]: O(n2)
● Best Case Time Complexity [Big-omega]: O(n2)
● Average Time Complexity [Big-theta]: O(n2)
● Space Complexity: O(1)
AIM 1.2: Write a program to implement Selection
sort. Code:

#include<stdio.h>
int main()
{
int n, i, j, temp, min;
int arr[]={80,70,50,90,10,45,20,15,55,60};
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}

min = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;

temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
i=0;
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);}}

Output:
80 70 50 90 10 45 20 15 55 60

10 15 20 40 45 50 55 60 70 80

Insertion Sort:

The insertion sort works in a slightly different way. It always maintains a sorted sublist in the
lower positions of the list. Each new item is then “inserted” back into the previous sublist such
that the sorted sublist is one item larger. The shaded items represent the ordered sublists as the
algorithm makes each pass.

Implementing Selection Sort Algorithm

Following are the steps involved in insertion sort:

1. We start by making the second element of the given array, i.e. element at index 1, the key.
The key element here is the new number that we need to add to our existing sorted set of
numbers
2. We compare the key element with the element(s) before it, in this case, element at index 0:
o If the key element is less than the first element, we insert the key element before the first
element.
o If the key element is greater than the first element, then we insert it after the first element.
3. Then, we make the third element of the array as key and will compare it with elements to it's
left and insert it at the right position.
4. And we go on repeating this, until the array issorted.

Complexity Analysis of Selection Sort

● Worst Case Time Complexity [ Big-O ]: O(n2)

● Best Case Time Complexity [Big-omega]: O(n)
● Average Time Complexity [Big-theta]: O(n2)
● Space Complexity: O(1)
AIM 1.3: Write a program to implement Insertion
sort. Code:
#include <stdio.h>

int main()
{
int n, d, t, flag = 0,k;
int arr[]={80,70,50,90,10,45,20,15,55,60};

for(k=0;k<10;k++){
printf("%d ",arr[k]);
}

for (c = 1 ; c <= n - 1; c++) {

t = array[c];

for (d = c - 1 ; d >= 0; d--) {

if (array[d] > t) {
array[d+1] = array[d];
flag = 1;
}
else
break;
}
if (flag)
array[d+1] = t;
}
K=0;
for(k=0;k<10;k++){
printf("%d ",arr[k]);
}

return 0;
}
Output:

80 70 50 90 10 45 20 15 55 60
10 15 20 40 45 50 55 60 70 80

Solve the below mention questionnaires:

1) The way a card game player arranges his cards as he picks them one by one can be comparedto

a) Quick sort b) Merge sort

c) Insertion sort d). Bubble sort

2) The correct order of the efficiency of the following sorting algorithms according to theiroverall
running time comparison is

a) Insertion>selection>bubble b) Insertion>bubble>selection
c) Selection>bubble>insertion. d) bubble>selection>insertion

3) Analysis the different sorting algorithm of Bubble, Selection and Insertion Sort.
Justifyyour answer which one is better sorting algorithm among them.

No of 1000 50 10000 50000 100000

Elements 00
Bubble Sort 1000^2 5000^2 10000^2 50000^2 100000^2
Selection Sort 1000^2 5000^2 10000^2 50000^2 100000^2
Insertion Sort 1000^2 5000^2 10000^2 50000^2 100000^2

Best case time complexity of bubble,selection and insertion sort is O(n), O(n 2),
O(n) respectively. Wrost case time complexity of these three are O(n 2), O(n2), O(n2).
In Bubble and insertion sort insertion sort do less comparison than bubble sort. So
insertion sort is best among these three. Insertion sort outperform merge sort too if
number of element is less.
--------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------
------------------------------------- ------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------
PRACTICAL SET - 2
AIM: Implementation and Time analysis of Merge & Quick sort algorithms.

Merge Sort:
Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into
several sub-lists until each sublist consists of a single element and merging those sublists in a
manner that results into a sorted list.

Implementing Merge Sort Algorithm:

 Divide the unsorted list into N sublists, each containing 1 element.

 Take adjacent pairs of two singleton lists and merge them to form a list of 2
elements. N will now convert into N/2 lists of size 2.
 Repeat the process till a single sorted list of obtained.

While comparing two sublists for merging, the first element of both lists is taken into
consideration. While sorting in ascending order, the element that is of a lesser value becomes a
new element of the sorted list. This procedure is repeated until both the smaller sublists are empty
and the new combined sublist comprises all the elements of both the sublists.

Algorithm:

MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two
halves: middle m = (l+r)/2
2. Call mergeSort for first
half: Call mergeSort(arr,
l, m)
3. Call mergeSort for second
half: Call mergeSort(arr,
m+1, r)
4. Merge the two halves sorted in step 2 and
3: Call merge(arr, l, m, r)

Complexity Analysis of Merge Sort

The following will be the time and space complexity for merge sort algorithm:
 Worst Case Time Complexity [ Big-O ]: O(n logn)
 Best Case Time Complexity [Big-omega]: O(n logn)
 Average Time Complexity [Big-theta]: O(n log n)
 Space Complexity: O(n)
Example:
2.1 : Write a program to implement Merge sort.
Code:
#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 n=10,i;
int arr[]={80,70,50,90,10,45,20,15,55,60};

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

mergesort(arr,0,n-1);

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

return 0;
}

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

{
int mid;

if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid);
mergesort(a,mid+1,j);
merge(a,i,mid,mid+1,j);
}
}

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

{
int temp[50];
int i,j,k;
i=i1;
j=i2;
k=0;

while(i<=j1 && j<=j2)

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

while(i<=j1)
temp[k++]=a[i++];

while(j<=j2)
temp[k++]=a[j++];

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

Output:
80 70 50 90 10 45 20 15 55 60
10 15 20 40 45 50 55 60 70 8
Quick Sort:

Quick sort is based on the divide-and-conquer approach based on the idea of choosing one
element as a pivot element and partitioning the array around it such that: Left side of pivot
contains all the elements that are less than the pivot element Right side contains all elements
greater than the pivot.
It reduces the space complexity and removes the use of the auxiliary array that is used in merge
sort. Selecting a random pivot in an array results in an improved time complexity in most of the
cases.

Implementing Quick Sort Algorithm:

Select the first element of array as the pivot element First, we will see how the partition of the
array takes place around the pivot.
 Choose the highest index value has pivot
 Take two variables to point left and right of the list excluding pivot
 left points to the low index
 right points to the high
 while value at left is less than pivot move right
 while value at right is greater than pivot move left
 if both step 5 and step 6 does not match swap left and right
 if left ≥ right, the point where they met is new pivot

Algorithm:
quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
Complexity Analysis of Merge Sort:

The following will be the time and space complexity for merge sort algorithm:
 Worst Case Time Complexity [ Big-O ]: O(n^2)
 Best Case Time Complexity [Big-omega]: O(n logn)
 Average Time Complexity [Big-theta]: O(n log n)
 Space Complexity: O(n)
Example:
2.2 : Write a program to implement Quick sort.
Code:
#include<stdio.h>
void quicksort(int number[],int first,int last){
int i, j, pivot, temp;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}

temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);

}
}

int main(){
int i, count;
int arr[]={80,70,50,90,10,45,20,15,55,60},k;
for(k=0;k<10;k++){
printf("%d ",arr[k]);
}

quicksort(arr,0,count-1);
k=0;
for(k=0;k<10;k++){
printf("%d ",arr[k]);
}

return 0;
}

Output:

80 70 50 90 10 45 20 15 55 60
10 15 20 40 45 50 55 60 70 80
Solve the below mention questionnaires:

1) For the improvement of efficiency of quick sort the pivot can be

a) the first element b) the mean element
c) the last element d) None of the above Answer: B
( )

2) Which of the following is example of in-placealgorithm?

a) Merge Sort b) BubbleSort
c) Insertion Sort d) Quick Sort Answer: ( B )

3) Quick Sort can be categorized into which of the following?

a) Brute Force
technique b)
Dynamic
programming
c) Greedy algorithm d) Divide and conquer Answer: ( D )

4) Perform the Merge Sort operation on the given list.

54, 26, 93, 17, 77, 31, 44, 55, 20

54 26 93 17 77 31 44 55 20
/ \
54 26 93 17 77 31 44 55 20
/ \ / \
54 26 93 17 77 31 44 55 20
/ \ /\ / \ / \
54 26 93 17 77 31 44 55 20
\ / \ / \ / \ /
26 54 17 93 31 77 20 44 55
\ / \ /
17 26 54 93 20 31 44 55 77
\ /
17 20 26 31 44 54 55 77 93
PRACTICAL SET - 3
AIM: Implementation and Time analysis of linear and binary search algorithm.

Linear Search Algorithm:

Linear search algorithm finds given element in a list of elements with O(n) time complexity where
n is total number of elements in the list. This search process starts comparing of search element
with the first element in the list. If both are matching then results with element found otherwise
search element is compared with next element in the list. If both are matched, then the result is
"element found". Otherwise, repeat the same with the next element in the list until search element
is compared with last element in the list, if that last element also doesn't match, then the result is
"Element not found in the list". That means, the search element is compared with element by
element in the list.

Implementing Linear Search Algorithm:

● Read the search element from the user
● Compare, the search element with the first element in the list.
● If both are matching, then display "Given element found!!!" and terminate the function
● If both are not matching, then compare search element with the next element in the list.
● Repeat steps 3 and 4 until the search element is compared with the last element in the list.
● If the last element in the list is also doesn't match, then display "Element not found!!!"
and terminate the function.

Algorithm:

procedure linear_search (list, value)

for each item in the list
if match item == value
return the item's location
end if
end for
end procedure
Complexity Analysis of Linear Search:

● Worst Case Time Complexity [ Big-O ]: O(n)

● Best Case Time Complexity [Big-omega]: O(1)
● Average Time Complexity [Big-theta]: O(n)
● Space Complexity: O(1)
3.1 : Write a program to implement Linear Search.
Code:

#include<stdio.h>

void main(){
int arr[]={80 ,70 ,50 ,90 ,10 ,45 ,20 ,15 ,55 ,60};
printf("enter the key:");
int key,i;
scanf("%d",&key);
for(i=0;i<10;i++){
if(arr[i]==key){
printf(" found at index number %d",i);
break;
}
}
}

Output:
Enter the key:80
Found at index number 0
Binary Search Algorithm:
The binary search algorithm can be used with only sorted list of element. That means, binary
search can be used only with list of element which are already arranged in a order. The binary
search cannot be used for list of element which are in random order.
This search process starts comparing of the search element with the middle element in the
list. If both are matched, then the result is "element found". Otherwise, we check whether the
search element is smaller or larger than the middle element in the list. If the search element is
smaller, then we repeat the same process for left sublist of the middle element. If the search
element is larger, then we repeat the same process for right sublist of the middle element.
We repeat this process until we find the search element in the list or until we left with a
sublist of only one element. And if that element also doesn't match with the search element, then
the result is "Element not found in the list".

Implementing Binary Search Algorithm:

● Read the search element from the user
● Find the middle element in the sorted list
● Compare, the search element with the middle element in the sorted list.
● If both are matching, then display "Given element found!!!" and terminate the function
● If both are not matching, then check whether the search element is smaller or largerthan
middle element.
● If the search element is smaller than middle element, then repeat steps 2, 3, 4 and 5 forthe
left sublist of the middle element.
● If the search element is larger than middle element, then repeat steps 2, 3, 4 and 5 forthe
right sublist of the middle element.
● Repeat the same process until we find the search element in the list or until sublist
contains only one element.
● If that element also doesn't match with the search element, then display "Element
not found in the list!!!" and terminate the function.

Algorithm:

Procedurebinary_searc
h A ← sorted array
n ← size of array
x ← value to be searched

Set lowerBound = 1
Set upperBound = n

while x not found

if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = (lowerBound + upperBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] == x
EXIT: x found at location midPoint
end while
end procedure

Complexity Analysis of Binary Search:

● Worst Case Time Complexity [ Big-O ]: O(logn)

● Best Case Time Complexity [Big-omega]: O(1)
● Average Time Complexity [Big-theta]: O(log n)
● Space Complexity: O(1)

3.2 : Write a program to implement Binary SearchAlgorithm.

Code:
#include<stdio.h>

int binary_search(int arr[],int left,int right,int key){

int middle=left+right/2;
if(key==arr[middle]){
return middle;
}else if(key<arr[middle]){
return binary_search( arr,left,middle,key);
}else{
return binary_search(arr, middle,right,key);
}
}

void main(){
int arr[]={10 ,15 ,20 ,40 ,45 ,50 ,55 ,60 ,70 ,80};
printf("enter the key:");
int key,i;
scanf("%d",&key);
printf("found at %d",binary_search(arr,0,9,key));
}
Output:
enter the key:45
found at 4
Solve the below mention questionnaires:

1) The Number of comparisons done by sequential search

is? a). (N/2)+1 b) (N+1)/2
c). (N-1)/2 d) (N-2)/2

Answer: ( B )

2) What are the applications of binary search?

a). To find the lower/upper bound in an ordered sequence b) Union of intervals
c). Debugging d) All of
thementioned

Answer: ( D )

3) Binary search algorithm cannot be applied to …

a). sorted linked list b) sorted binary trees
c) sorted linear array d) pointer array

Answer: ( A )

Conclusion / Outcome:
I learned linear and binary search
PRACTICAL SET – 4
AIM: Implementation of max-heap sort algorithm.

Explanation: Heaps can be used in sorting an array. In max-heaps, maximum element will
always be at the root. Heap Sort uses this property of heap to sort the array. It is similar to
selection sort where we first find the maximum element and place the maximum element at the
end. We repeat the same process for remaining elements.

Heap Sort Algorithm for sorting in increasing order:

1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item
of the heap followed by reducing the size of heap by 1. Finally, heapify the root oftree.
3. Repeat above steps while size of heap is greater than 1.

How to build the heap?

Heapify procedure can be applied to a node only if its children nodes are heapified. So the
heapification must be performed in the bottom up order.
Code:
#include <stdio.h>

void swap(int *a, int *b) {

int tmp = *a;
*a = *b;
*b = tmp;
}

void heapify(int arr[], int n, int i) {

int max = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;

if (leftChild < n && arr[leftChild] > arr[max])

max = leftChild;

if (rightChild < n && arr[rightChild] > arr[max])

max = rightChild;

if (max != i) {
swap(&arr[i], &arr[max]);
heapify(arr, n, max);
}
}

void heapSort(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n - 1; i >= 0; i--) {

swap(&arr[0], &arr[i]);

heapify(arr, i, 0);
}
}

void display(int arr[], int n) {

for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[]={80,70,50,90,10,45,20,15,55,60};
int n = 10;

for(k=0;k<10;k++){
printf("%d ",arr[k]);
}
heapSort(arr, n);
for(k=0;k<10;k++){
printf("%d ",arr[k]);
}
}

Output:

80 70 50 90 10 45 20 15 55 60
10 15 20 40 45 50 55 60 70 80
Solve the below mention questionnaires:

1. In a max-heap, element with the greatest key is always in which node?

a) Leaf node c) Root node
b) First node of left sub tree d) First node of right sub tree

Answer : ( C )

2. Heap can be used as…

a) Priority queue c) A decreasing order array
b) Stack d) None of the mentioned

Answer : ( A )

3. An array consists of n elements. We want to create a heap using the

elements.The time complexity of building a heap will be in order of
a) O(n*n*logn) c) O(n*n)
b) O(n*logn) d) O(n *logn *logn)

Answer : ( B )

4. The max heap constructed from the list of numbers 30, 10, 80, 60, 15, 55 is
a) 80, 55, 60, 15, 10, 30 c) 80, 60, 55, 30, 10, 15
b) 60, 80, 55, 30, 10, 15 d) None

Answer : ( D )

5. Always heap is a
a) Binary search tree c) None
b) Full binary tree d) Complete binary tree

Answer : ( D )

Conclusion / Outcome:

I learned heap sort from this practical.

DYNAMIC PROGRAMMING

Dynamic programming is a method for solving a complex problem by breaking it down into
simpler sub-problems, solving each of those sub-problems just once, and storing their solutions –
in an array usually.

Now, every time the same sub-problem occurs, instead of recomputing its solution, the previously
calculated solutions are used, thereby saving computation time at the expense of storage space.

Dynamic programming can be implemented in two ways –

Memoization – Memoization uses the top-down technique to solve the problem i.e. it begin with
original problem then breaks it into sub-problems and solve these sub-problems in the same way.

In this approach, you assume that you have already computed all sub-problems. You typically
perform a recursive call (or some iterative equivalent) from the main problem. You ensure that the
recursive call never recomputes a sub-problem because you cache the results, and thus duplicate
sub-problems are not recomputed.

Tabulation – Tabulation is the typical Dynamic Programming approach. Tabulation uses the
bottom up approach to solve the problem, i.e., by solving all related sub-problems first, typically
by storing the results in an array. Based on the results stored in the array, the solution to the “top”
/ original problem is then computed.

Memoization and tabulation are both storage techniques applied to avoid recomputation of a sub-
problem

The idea behind dynamic programming, In general, is to solve a given problem, by solving
different parts of the problem (sub-problems), then using the cached solutions of the sub-problems
to reach an overall solution.
PRACTICAL – 5
AIM : Implementation of a knapsack problem using dynamic programming.

Explanation : The knapsack problem or rucksack problem is a problem in combinatorial

optimization: Given a set of items, each with a weight and a profit value, determine the number of
each item to include in a collection so that the total weight is less than or equal to a given limit
and the total profit value is as large as possible. This is a 0-1 knapsack problem hence we can
either take an entire item or reject it completely. We cannot break an item and fill theknapsack.

● In this problem we have a Knapsack that has a weight limit W, which representsknapsack
capacity.
● Given two integer arrays val[0..n-1] and wt[0..n-1] which represent values andweights
associated with n items respectively.
● Find out the maximum value subset of val[] such that sum of the weights of this subset
is smaller than or equal to W.

Code:

#include <stdio.h>
int max(int a,int b){
if(a>b){
return a;
}
return b;
}
void main(){
int n=3,W=50;
int t[n+1][W+1];
int wt[]={10,20,30},vl[]={60,100,120};
int i,j;
for( i=0;i<=n;i++){
for( j=0;j<=W;j++){
if( i==0||j==0){
t[i][j]=0;
}
}
}
i=0;j=0;
for(i=1;i<=n;i++){
for(j=1;j<=W;j++){
if(wt[i-1]<=j){
t[i][j]=max(t[i-1][j],(vl[i-1]+t[i-1][j-wt[i-1]]));
}else{
t[i][j]=t[i-1][j];
}
}
}
printf("%d",t[n][W]);
}

Output:

( Input is weight={10,2030} value={60,100,120} capacity=50 )

220
Solve the below mention questionnaires:

1. You are given a knapsack that can carry a maximum weight of 60. There are 4 items
with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value
of the items you can carry using the knapsack?
a) 160 c) 170
b) 200 d) 90
Answer : ( A )

2. What is the time complexity of the above dynamic programming

implementationof the Knapsack problem with n items and a maximum weight of
W?
a) O(n) c) O(nW)
b) O(n + w) d) O(n2)

Answer : ( C )

3. What is the space complexity of the above dynamic programming

implementationof the Knapsack problem with n items and a maximum weight of
W?
a) O(n) c) O(n + W)
b) O(nW) d) O(n2)

Answer : ( C )

4. 0/1 knapsack is based on

a) Greedy method c) Dynamic programming
b) Branch and bound method d) Divide and conquer

Answer : ( C)

5. Bin-packing problem is the application of

a) Knapsack c) Back tracking
b) Branch and bound d) Dynamic programming

Answer : (A )

Conclusion / Outcome:
I leaned 0/1 knapsack and how it works

PRACTICAL – 6
AIM : Implementation of chain matrix multiplication using dynamic
programming.

Explanation: Given a sequence of matrices, find the most efficient way to multiply these
matrices together. The problem is not actually to perform the multiplications, but merely to decide
in which order to perform the multiplications.

We have many options to multiply a chain of matrices because matrix multiplication is

associative. In other words, no matter how we parenthesize the product, the result will be the
same. For example, if we had four matrices A, B, C, and D, we would have:

(ABC) D = (AB) (CD) = A (BCD) =....

However, the order in which we parenthesize the product affects the number of simple arithmetic
operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30
matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

(AB) C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations

A (BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Clearly the first parenthesization requires less number of operations.

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of
dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the
minimum number of multiplications needed to multiply the chain.

This problem can be solved using Dynamic Programming. First we will compute results for sub-
chains of the original chain and store these results in a 2-D array. Then we will use these results to
compute results for larger chains.

Code:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define P printf("\n")

// ------------- DECLARATION SECTION -----------

int n,i,j,k,l,s,round;
int d[20],m[20][20],mul[5];
void PrintLine();

// ------------ MAIN SECTION -------------

void main()
{
clrscr();

printf("Enter Number of Matrix To Multiply :--> ");

scanf("%d",&n);

for(i=0;i<=n;i++)
{
printf("\nEnter D%d :--> ",i);
scanf("%d",&d[i]);
}
round=n-1;
s=0;
PrintLine();
while(s<=round)
{
if(s==0)
{
for(i=1;i<=n;i++)
{
m[i][i]=0;
printf("\nm%d%d=%d",i,i,m[i][i]);
}
PrintLine();
getch();
}

// ---------------------------------------------

if(s==1)
{
for(i=1;i<n;i++)
{
m[i][i+1]=d[i-1]*d[i]*d[i+1];
printf("\nm%d%d=%d",i,i+1,m[i][i+1]);
}
PrintLine();
getch();
getch();
}

// ---------------------------------------------

if(s>1)
{
for(i=1;i<=n-s;i++)
{
l=i+1;
j=0;
for(k=i;k<(s+i);k++)
{
mul[j]=(m[i][k]+m[l][s+i]+
d[i-1]*d[k]*d[s+i]);
l++;
j++;
}
int temp,x,y;
for(x=0;x<j-1;x++)
{
for(y=x+1;y<j;y++)
{
if(mul[x]>mul[y])
{
temp=mul[x];
mul[x]=mul[y];
mul[y]=temp;
}
}
}
m[i][i+s]=mul[0];
printf("\nm%d%d=%d",i,i+s,m[i][i+s]);
}
PrintLine();
getch();
}
s++;
}
printf("\n Minimum Number Of Multiplications :--> %d ",m[1][n]);
getch();
}

void PrintLine()
{
printf("\n-----------");
}
Output:
Enter Number of Matrix To Multiply :--> 4

Enter D0 :--> 5

Enter D1 :--> 4

Enter D2 :--> 6

Enter D3 :--> 2

Enter D4 :--> 7

-----------
m11=0
m22=0
m33=0
m44=0
-----------
m12=120
m23=48
m34=84
-----------
m13=88
m24=104
-----------
m14=158
-----------
Minimum Number Of Multiplications :--> 158
Solve the below mention questionnaires :

1. Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices

respectively. What is the number of multiplications required to multiply the two
matrices?
a) 10 * 20 c) 20 * 30
b) 10 * 30 d) 10 * 20 * 30
Answer : (D )

2. What is the time complexity of the above dynamic programming implementation

of the matrix chain problem?
a) O(1) c) O(n2)
b) O(n) d) O(n3)
Answer : (C )

3. Which of the following methods can be used to solve the matrix chain
multiplication problem?
a) Dynamic programming c) Recursion
b) Brute force d) All of the mentioned

Answer : (D )
4. Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices
respectively. What is the minimum number of multiplications required tomultiply
the three matrices?
a) 18000 c) 24000
b) 12000 d) 32000

Answer : ( C )

5. Consider the matrices P, Q, R and S which are 20 x 15, 15 x 30, 30 x 5 and 5 x 40

matrices respectively. What is the minimum number of multiplications required
to multiply the four matrices?
a) 6050 c) 7750
b) 7500 d) 12000

Answer : ( D)

Conclusion / Outcome:

I learned what is matrix chain multiplication and how it works

Practical Set-7

AIM: Implementation of making a change problem using dynamic programming.

Explanation:
Given a value N, if we want to make change for N cents, and we have infinite supply of each of
S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins
doesn\’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So
output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3},
{2,2,6}, {2,3,5} and {5,5}. So the output should be 5

Code:

#include <stdio.h>
int max(int a,int b){
if(a>b){
return a;
}
return b;
}
void main(){
int n=3,W=4;
int wt[]={1,2,3};
int t[n+1][W+1];
int i,j;
for(i=0;i<=n;i++){
for(j=0;j<=W;j++){
if(i==0){
t[i][j]=0;
}else if(j==0){
t[i][j]=1;
}
}
}
i=0;j=0;
for(i=1;i<=n;i++){
for(j=1;j<=W;j++){
if(wt[i-1]<=j){
t[i][j]=t[i-1][j]+t[i][j-wt[i-1]];
}else{
t[i][j]=t[i-1][j];
}
}
}
printf("%d ",t[i][j]);

Output:
4
Give the Answer to the below Short Questions:
1. What is time complexity of making change using dynamic programming?
O( nW ) m=size of array W= capacity

2. If S = 5 and N = {1,2,3}, means we have a sum of 5 and want to make change for thissum
using coins of denomination 1,2 and 3. There is infinite supply of these coins. We have to
find in how many ways we can make this change.
Maximum number of ways =4

Conclusion / Outcome:

I learned coin change problem using DP.

Practical Set- 8

AIM: Implementation of a knapsack problem using greedy algorithm.

Description:
Given a set of items, each with a weight and a value, determine a subset of items to include in a
collection so that the total weight is less than or equal to a given limit and the total value is as
large as possible.

The knapsack problem is in combinatorial optimization problem. It appears as a subproblem in

many, more complex mathematical models of real-world problems. One general approach to
difficult problems is to identify the most restrictive constraint, ignore the others, solve a
knapsack problem, and somehow adjust the solution to satisfy the ignored constraints.

Problem Scenario

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n
items available in the store and weight of ith item is wi and its profit is pi. What items should the
thief take?

In this context, the items should be selected in such a way that the thief will carry those items for
which he will gain maximum profit. Hence, the objective of the thief is to maximize the profit.

Based on the nature of the items, Knapsack problems are categorized as

● Fractional Knapsack
● Knapsack
Fractional Knapsack
In this case, items can be broken into smaller pieces, hence the thief can select fractions of items.

According to the problem statement,

● There are n items in the store

● Weight of ith itemwi>0wi>0
● Profit for ith item pi>0pi>0and
● Capacity of the Knapsack is W
In this version of Knapsack problem, items can be broken into smaller pieces. So, the thief may
take only a fraction xi of ith item.
0⩽xi⩽10⩽xi⩽1
The ith item contributes the weight xi.wixi.wi to the total weight in the knapsack and
profit xi.pixi.pi to the total profit.
Hence, the objective of this algorithm is to
maximize∑n=1n(xi.pi) maximize∑n=1n(xi.pi)

subject to constraint,
∑n=1n(xi.wi)⩽W∑n=1n(xi.wi)⩽W

It is clear that an optimal solution must fill the knapsack exactly, otherwise we could add a
fraction of one of the remaining items and increase the overall profit.

Thus, an optimal solution can be obtained by

∑n=1n(xi.wi)=W∑n=1n(xi.wi)=W

In this context, first we need to sort those items

according to the value of pi/wi, so that pi+1wi+1pi+1wi+1≤
pi/wi . Here, x is an array to store the fraction of items.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)

for i = 1 to n
do x[i] = 0
weight = 0
for i = 1 to
n
if weight + w[i] ≤ W
then x[i] = 1
weight = weight + w[i]
else
x[i] = (W - weight) / w[i]
weight = W
break
return x

Analysis
If the provided items are already sorted into a decreasing order of pi/wi, then the whileloop takes
a time in O(n); Therefore, the total time including the sort is in O(n logn).
Example
Let us consider that the capacity of the knapsack W = 60 and the list of provided
items are shown in the following table −

Item A B C D

Profit 2 1 1 1
8 0 2 2
0 0 0 0
Weight 4 1 2 2
0 0 0 4
Ratio 7 1 6 5
(pi)/(wi) 0
As the provided items are not sorted based on pi/wi. After sorting, the items are as shown in the
following table.

Item B A C D

Profit 1 2 1 1
0 8 2 2
0 0 0 0
Weight 1 4 2 2
0 0 0 4
Ratio 1 7 6 5
(pi/wi) 0

Solution
After sorting all the items according to pi/wi. First all of B is chosen as weight of B is less than
the capacity of the knapsack. Next, item A is chosen, as the available capacity of the knapsack is
greater than the weight of A. Now, C is chosen as the next item. However, the whole item cannot
be chosen as the remaining capacity of the knapsack is less than the weight of C.
Hence, fraction of C (i.e. (60 − 50)/20) is chosen.

Now, the capacity of the Knapsack is equal to the selected items. Hence, no more item can be
selected.

The total weight of the selected items is 10 + 40 + 20 * (10/20) = 60

And the total profit is 100 + 280 + 120 * (10/20) = 380 + 60 = 440

This is the optimal solution. We cannot gain more profit selecting any different combination of
items.
Code:

# include<stdio.h>

void knapsack(int n, float weight[], float profit[], float capacity) {

float x[20], tp = 0;
int i, j, u;
u = capacity;

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

x[i] = 0.0;

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

if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}

if (i < n)
x[i] = u / weight[i];

tp = tp + (x[i] * profit[i]);

printf("\nMaximum profit is:- %f", tp);

int main() {
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;

printf("\nEnter the no. of objects:- ");

scanf("%d", &num);

printf("\nEnter the wts and profits of each object:- ");

for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i], &profit[i]);
}

printf("\nEnter the capacityacity of knapsack:- ");

scanf("%f", &capacity);

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

ratio[i] = profit[i] / weight[i];
}

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

for (j = i + 1; j < num; 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;
}
}
}

knapsack(num, weight, profit, capacity);

return(0);
}
Output:
Enter the no. of objects:- 7

Enter the wts and profits of each object:-

2 10
35
5 15
77
16
4 18
13

Enter the capacity of knapsack:- 15

Maximum profit is:- 55.333332

Give the Answer to the below Short Questions:
1. The Knapsack problem is an example of

a) Greedy algorithm b) 2D dynamic programming Answer: ( A)

c) 1D dynamic programming d) Divide and conquer

2. Which of the following methods can be used to solve the Knapsack problem?
a) Brute force algorithm b) Recursion
c) Dynamic programming d) All of the mentioned Answer: D
(D )
3. You are given a knapsack that can carry a maximum weight of 60. There are 4 items withweights
{20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can
carry using the knapsack?
a)

160 b) 200
c) 170 d) 90 Answer: ( A)

4.
Whic o t followin proble i equivale t t 0- Knapsac proble
h f h g ms s nt o h 1 k m?
e e
a) You are given a bag that can carry a maximum weight of W. You are given N items which
have
a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items
into smaller pieces. Choose the items in such a way that you get the maximum value.

b) You are studying for an exam and you have to study N questions. The questions take {t1, t2,
t3,… .., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a
maximum of T hours. You can either study a question or leave it. Choose the questions in such a
way that your score is maximized.

c) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have
to find the minimum number of coins required to get the sum S.

d) None of the mentioned

Answer: (B )

5. The 0-1 Knapsack problem can be solved using Greedy algorithm.

a) True b) False

Answer: (B )
Practical Set-9
AIM: Implementation of Graph and Searching (DFS)
Explanation:
A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of astack.

2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the top of stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

DFS Example

Let's see how the Depth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.
We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its
adjacent vertices in the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has
already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.
After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have
completed the Depth First Traversal of the graph.

Code:

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

int DepthFirstSearch(int);

int n;

int graph[20][20], completed[10];

int DepthFirstSearch(int i)
{
int j;

printf(" %d", i);

completed[i] = 1;

for(j=0;j<n;j++)
{
if(!completed[j] && graph[i][j] == 1)
{
DepthFirstSearch(j);
}
}

return 0;
}

int main()
{
int i, j;

printf("\n enter number of vertices:");

scanf("%d",&n);

printf("\n enter adjecency matrix :\n");

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&graph[i][j]);
}
}

for(i=0;i<n;i++)
{
completed[i]=0;

printf("Depth First Search is\n");

}

DepthFirstSearch(0);

return 0;
}
Output:

Enter number of vertices:4

Enter adjecency matrix :

0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0

Depth First Search is :

0123
Give the Answer to Questions:
1. Depth First Search is equivalent to which of the traversal in the BinaryTrees?

a) Pre-order Traversal b) Post-order Traversal

c) Level-order Traversal d) In-order Traversal Answer: (D)

2. Time Complexity of DFS is? (V – number of vertices, E – number ofedges)

a) O(V + E) b) O(V)
c) O(E) d) None Answer: (A)

a) Linked List b) Tree

c) Graph with back edges d) None Answer: (b)
3. The Depth First Search traversal of a graph will result into?
4. A person wants to visit some places. He starts from a vertex and then wants to visit every
vertex till it finishes from one vertex, backtracks and then explore other vertex from same

vertex. What algorithm he should use?

a) Depth First Search b) Breadth First Search
c) Trim’s algorithm d) None Answer: (A )

Conclusion/ Outcome:
I learned deapth first search algorithm.
Practical Set-10
AIM: Implementation of Graph and Searching (BFS)
Explanation:
Traversal means visiting all the nodes of a graph. Breadth first traversal or Breadth first Search is
a recursive algorithm for searching all the vertices of a graph or tree data structure. In this article,
you will learn with the help of examples the BFS algorithm, BFS pseudocode and the code of the
breadth first search algorithm with implementation in C++, C, Java and Python programs.

BFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two categories:
1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The algorithm works as follows:

1. Start by putting any one of the graph's vertices at the back of aqueue.
2. Take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover every
vertex, we can also run the BFS algorithm on every node

BFS example

Let's see how the Breadth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.
We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and putting all its
adjacent vertices in the stack.

Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has
already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of the queue and visit 3,
which is at the front of the queue.
Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already visited. We visit it.

Since the queue is empty, we have completed the Depth First Traversal of the graph.

Code:
#include<stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;

void bfs(int v) {
for(i = 1; i <= n; i++)
if(a[v][i] && !visited[i])
q[++r] = i;
if(f <= r) {
visited[q[f]] = 1;
bfs(q[f++]);
}
}

void main() {
int v;
printf("\n Enter the number of vertices:");
scanf("%d", &n);

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

q[i] = 0;
visited[i] = 0;
}

printf("\n Enter graph data in matrix form:\n");

for(i=1; i<=n; i++) {
for(j=1;j<=n;j++) {
scanf("%d", &a[i][j]);
}
}

printf("\n Enter the starting vertex:");

scanf("%d", &v);
bfs(v);
printf("\n The node which are reachable are:\n");

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

if(visited[i])
printf("%d\t", i);
else {
printf("\n Bfs is not possible. Not all nodes are reachable");
break;
}
}
}
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:
123
Give the Answer to the below Questions:
1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal b) Post-order Traversal
c) Level-order Traversal d) In-order Traversal Answer: C

2. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of

edges)
a) O(V + E) b) O(V)
c) O(E) d) None Answer: (A)

3. The Data structure used in standard implementation of Breadth First Search is?
a) S
t
a
ck b) Queue
c) Linked List d) None Answer: (B)
4. What can be the applications of Breadth First
Search? a) Finding shortest path between two nodes
b) Finding bipartitions of a graph
c) GPS navigation system
d)
All of the mentioned Answer: (D)

5. When the Breadth First Search of a graph isunique?

a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d)
None of the mentioned Answer: (B )

Conclusion/ Outcome:
I learned breath forst algorithm
Practical Set-11

AIM: Implement prim’s algorithm.

Explanation:

The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected.
So the two disjoint subsets (discussed above) of vertices must be connected to make
a Spanning Tree. And they must be connected with the minimum weight edge to make it
a Minimum Spanning Tree.

Algorithm

1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as
INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
a) Pick a vertex u which is not there in mstSet and has minimum key value.
b) Include u to mstSet.
c) Update key value of all adjacent vertices of u. To update the key values,
iteratethrough all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is
less than the previous key value of v, update the key value as weight of u-v
The idea of using key values is to pick the minimum weight edge from cut. The key values are
used only for vertices which are not yet included in MST, the key value for these vertices indicate
the minimum weight edges connecting them to the set of vertices included in MST.

Example:

The set mstSet is initially empty and keys assigned to vertices are {0, INF, INF, INF, INF, INF,
INF, INF} where INF indicates infinite. Now pick the vertex with minimum key value. The vertex
0 is picked, include it in mstSet. So mstSet becomes {0}. After including to mstSet, update key
values of adjacent vertices. Adjacent vertices of 0 are 1 and 7. The key values of 1 and 7 are
updated as 4 and 8. Following subgraph shows vertices and their key values, only the vertices
with finite key values are shown. The vertices included in MST are shown in green color.
Pick the vertex with minimum key value and not already included in MST (not in mstSET). The
vertex 1 is picked and added to mstSet. So mstSet now becomes {0, 1}. Update the key values of
adjacent vertices of 1. The key value of vertex 2 becomes 8.

Pick the vertex with minimum key value and not already included in MST (not in mstSET).
We can either pick vertex 7 or vertex 2, let vertex 7 is picked. So mstSet now becomes {0, 1, 7}.
Update the key values of adjacent vertices of 7. The key value of vertex 6 and 8 becomes finite
(7 and 1 respectively).

Pick the vertex with minimum key value and not already included in MST (not in mstSET).
Vertex 6 is picked. So mstSet now becomes {0, 1, 7, 6}. Update the key values of adjacent
vertices of 6. The key value of vertex 5 and 8 are updated.
We repeat the above steps until mstSet includes all vertices of given graph. Finally, we get the
following graph.

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

#define infinity 9999

#define MAX 20

int G[MAX][MAX],spanning[MAX][MAX],n;

int prims();

int main()
{
int i,j,total_cost;
printf("Enter 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]);

total_cost=prims();
printf("\nspanning tree matrix:\n");

for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}

printf("\n\nTotal cost of spanning tree=%d",total_cost);

return 0;
}

int prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,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];
spanning[i][j]=0;
}

distance[0]=0;
visited[0]=1;

for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}

min_cost=0;
no_of_edges=n-1;

while(no_of_edges>0)
{

min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}

u=from[v];

spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}

min_cost=min_cost+cost[u][v];
}

return(min_cost);
}

Output:
Enter no. of vertices:6
Enter the adjacency matrix:
031600
305030
150564
605002
036006
004260
spanning tree matrix:
031000
300030
100004
000002
030000
004200
Total cost of spanning tree=13
Give the Answer to the below Questions:

1. What is the time complexi t extract a vertex from the priority queue in
Prim’s ty o
algorithm?
a) log (V) c) V.V
b) E.E d) log (E) Answer: (A
)

2. What algorithm technique is used in the implementation of Prim’s solution for the MST?
a) Greedy Technique
b) Divide-and-Conquer Technique
c) Dynamic Programming Technique
d) The algorithm combines more than one of the above techniques Answer: (A )
3. The output of Prims algorithm is MST .

4. Define Prim’s algorithm.

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected
graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the
total weight of all the edges in the tree is minimized.

5. For minimum Spanning Tree construction, Prim’s algorithm selects an edge

a) That adds a new vertex to partially constructed tree with minimal increment in cost
of MST
b) With maximum number of vertices connected to it so that MST has least diameter
c) With minimum weight so that cost of MST is always minimum.
d) That does not introduce a cycle.
Answer: ( C)

Conclusion/ Outcome:
I learned how to implement Prim’s Algorithm.
Practical Set-12

Aim: Implement Krushal’s algorithm.

Explanation:

Below are the steps for finding MST using Kruskal’s algorithm
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
cycleis not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
The algorithm is a Greedy Algorithm. The Greedy Choice is to pick the smallest weight edge that
does not cause a cycle in the MST constructed so far. Let us understand it with an example:
Consider the below input graph.

The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having
(9 – 1) = 8 edges.
After sorting:
Weig Sr Des
ht c t
1 7 6
2 8 2
2 6 5
4 0 1
4 2 5
6 8 6
7 2 3
7 7 8
8 0 7
8 1 2
9 3 4
10 5 4
11 1 7
14 3 5
Now pick all edges one by one from sorted list of edges

1. Pick edge 7-6: No cycle is formed, include it.

2. Pick edge 8-2: No cycle is formed, include it.

3. Pick edge 6-5: No cycle is formed, includeit.

4. Pick edge 0-1: No cycle is formed, include it.

5. Pick edge 2-5: No cycle is formed, include it.

6. Pick edge 8-6: Since including this edge results in cycle, discard it.

7. Pick edge 2-3: No cycle is formed, include it.

8. Pick edge 7-8: Since including this edge results in cycle, discard it.

9. Pick edge 0-7: No cycle is formed, include it.

10. Pick edge 1-2: Since including this edge results in cycle, discard it.

11. Pick edge 3-4: No cycle is formed, include it.

Since the number of edges included equals (V – 1), the algorithm stops here.
Code:
#include<stdio.h>

#define MAX 30

typedef struct edge

{
int u,v,w;
}edge;

typedef struct edgelist

{
edge data[MAX];
int n;
}edgelist;

edgelist elist;

int G[MAX][MAX],n;
edgelist spanlist;

void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();

void main()
{
int i,j,total_cost;

printf("\nEnter number 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]);

kruskal();
print();
}
void kruskal()
{
int belongs[MAX],i,j,cno1,cno2;
elist.n=0;

for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
if(G[i][j]!=0)
{
elist.data[elist.n].u=i;
elist.data[elist.n].v=j;
elist.data[elist.n].w=G[i][j];
elist.n++;
}
}

sort();

for(i=0;i<n;i++)
belongs[i]=i;

spanlist.n=0;

for(i=0;i<elist.n;i++)
{
cno1=find(belongs,elist.data[i].u);
cno2=find(belongs,elist.data[i].v);

if(cno1!=cno2)
{
spanlist.data[spanlist.n]=elist.data[i];
spanlist.n=spanlist.n+1;
union1(belongs,cno1,cno2);
}
}
}

int find(int belongs[],int vertexno)

{
return(belongs[vertexno]);
}

void union1(int belongs[],int c1,int c2)

{
int i;

for(i=0;i<n;i++)
if(belongs[i]==c2)
belongs[i]=c1;
}
void sort()
{
int i,j;
edge temp;

for(i=1;i<elist.n;i++)
for(j=0;j<elist.n-1;j++)
if(elist.data[j].w>elist.data[j+1].w)
{
temp=elist.data[j];
elist.data[j]=elist.data[j+1];
elist.data[j+1]=temp;
}
}

void print()
{
int i,cost=0;

for(i=0;i<spanlist.n;i++)
{
printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
cost=cost+spanlist.data[i].w;
}

printf("\n\nCost of the spanning tree=%d",cost);

}
Output:

Enter number of vertices:6

Enter the adjacency matrix:

031600
305030
150564
605002
036006
004260

2 0 1
5 3 2
1 0 3
4 1 3
5 2 4

Cost of the spanning tree=13

Give the Answer to the below Questions:

1. What is the time complexity to extract a vertex from the priority queue
in Krushkal’s algorithm?

a) log (V) b) V.V

c) E.E d) E log (E) Answer: A
( )
2. The output of Krushkal’s algorithm is MST .

3. Define Krushkal’s Algorithm.

Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the
graph is connected, it finds a minimum spanning tree. It is a greedy algorithm in graph theory as in
each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning
forest.

4. Assume a graph is having 10 vertices and 20 edges. In Krushkal’s minimum spanning tree
method, 5 edges are rejected. How many edges are not considered during execution of
algorithm on the given graph?
a) 6 c) 5
b) 4 d) 10 Answer: ( )

5. GREEDY Algorithm technique is used in the implementation of

Krushkal’s solution for the MST?

Conclusion/ Outcome:
I learned how to implement krushkal’s Algorithm.
References
1. http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html
2. http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Merge_sort.html
3. http://cs.uef.fi/pages/franti/asa/notes.html
4. https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/INDEX.HTM
5. IETE e Material
6. https://www.geeksforgeeks.org
7. https://www.programiz.com/
8. https://www.thecrazyprogrammer.com
9. http://c-program-example.com/2011/10
10.https://www.tutorialspoint.com/data_structures_algorith
ms 11.http://www.c4learn.com/c-programs
12.http://c-program-example.com/