Lab Assignment

Design and Analysis of Algorithms

Submitted By:-

Name : Rojbela kisku

Univ. Registration No. : BBMK-S1904753

Univ. Roll No. : 200081018215

Course : BCA
Semester : 4 th

Department Of BCA,
P. K. Roy Memorial College,
Dhanbad-826004.

1 | Page
 .

1 3-5
To sort the given set of elements
using quick sort method.

2 6-8
To sort the given set of elements
using merge sort method.

3 9 - 11
To check the connectivity of a
given graph using DFS method.

4 Find a subset of a given set 12 - 13

S = {S 1 ,S 2 ,…,S n } of n
positive
integers whose sum is equal to a
given positive number d.

5 14 - 17
To ind the minimum cost
spanning tree of a given
undirected graph using Prim’s
Algorithm.
EXPERIMENT NO - 1

QUICK SORT
OBJECTIVE:

Sort a given set of elements using the Quick sort method and determine the time required
to sort the elements. Repeat the experiment for different values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n. The
elements can be read from a file or canbe generated using the random number generator.

2 | Page
PACKAGES / SOFTWARE REQUIRED:

Code Blocks

THEORY:

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions
the givenarray around the picked pivot.

There are many different versions of QuickSort that pick pivot in different ways.
(i) Always pick first element as pivot.
(ii) Always pick last element as pivot (implemented below) (iii)
Pick a random element as pivot. (iv) Pick median as pivot.

The key process in QuickSort is partition. Target of partitions is, given an array and an element
x of array as pivot, put x at its correct position in sorted array and put all smaller elements
(smaller than x) before x, and put all greater elements (greater than x) after x.

PROGRAMMING LOGIC:

PROCEDURE:

1. Create: Open Dev C++, write a program with QuickSort program logic, after that save the program
with .c extension.
2. Compile: Alt + F9
3. Execute: Ctrl + F10

SOURCE CODE:

#include<stdio.h>

void swap(int* a, int* b)

{

3 | Page
 int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int low, int high)

{
int pivot =
arr[high]; int i =
(low - 1);

for (int j = low; j <= high- 1; j++)

{

if (arr[j] <= pivot)

{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1],
&arr[high]); return (i + 1);
}

void quickSort(int arr[], int low, int high)

{
if (low < high)
{
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1,
high);
}
}
void printArray(int arr[], int size)
{

int i;

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

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

4 | Page
 int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n =
sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

INPUT/ OUTPUT:

EXPERIMENT - 2

MERGE SORT
OBJECTIVE:
Implement merge sort algorithm to sort a given set of elements and determine the time required
to sort the elements. Repeat the experiment for different values of n, the number of elements
in the list to be sorted and plot a graph of the time taken versus n. The elements can be read
from a file or can be generated using the random number generator.

PACKAGES / SOFTWARE REQUIRED:

Code Blocks

THEORY:

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls
itself for the two halves, and then merges the two sorted halves. The merge() function is used
for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and
arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

PROGRAMMING LOGIC:

5 | Page
 PROCEDURE:

Create: Open Dev C++, write a program with MergeSort logic after that save the program with .c
extension. Compile: Alt + F9
Execute: Ctrl + F10

6 | Page
SOURCE CODE:

/* C program for Merge Sort

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

void merge(int arr[], int l, int m, int r)

{
int i, j, k;
int n1 = m - l +
1; int n2 = r - m;

int L[n1], R[n2];

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

L[i] = arr[l +
i]; for (j = 0; j < n2;
j++)
R[j] = arr[m + 1 + j];

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{ if (L[i] <= R[j]) {
arr[k] =
L[i]; i++;
}
else { a
r
r
} k++; [
} k
]
=
R
[
j
]
;
j
+
+
;

7 | Page
 while (i < n1) {
arr[k] =
L[i]; i++;

8 | Page
 k++;
}
while (j < n2) {
arr[k] =
R[j]; j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) { int m = l + (r - l)
/ 2;
10 | Page
mergeSort(arr, l, m);

mergeSort(arr, m + 1,

r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)

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

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 }; int
arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is
\n"); printArray(arr,
arr_size); return 0;
}

INPUT/ OUTPUT:
11 | Page
12 | Page
EXPERIMENT - 3

DEPTH FIRST SEARCH (GRAPH TRAVERSAL)

OBJECTIVE:
To check connectivity of given graph using DFS method

PACKAGES / SOFTWARE REQUIRED:

Code Blocks

THEORY:

Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a stack
to remember to get the next vertex to start a search.

(i) Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
(ii) If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the
verticesfrom the stack, which do not have adjacent vertices.) (iii) Repeat Rule 1 and
Rule 2 until the stack is empty.

PROGRAMMING LOGIC:
13 | Page
PROCEDURE:

Create: Open Dev C++, write a program after that save the program with .c
extension.
Compile: Alt + F9
Execute: Ctrl + F10

SOURCE CODE:

#include<iostream>
#define NODE 5 using
namespace std;
int graph[NODE][NODE] = {{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 1},
{0, 1, 1, 0, 1}, {0, 0, 1, 1, 0}};
void traverse(int u, bool visited[])
{
visited[u] = true; //mark v as visited
for(int v = 0; v<NODE; v++) {
if(graph[u][v]) {
if(!visited[v]) {
traverse(v, visited);
}
}
}
bool isConnected() {
bool *vis = new bool[NODE];
for(int u; u < NODE; u++) {
for(int i = 0; i<NODE; i++)
vis[i] = false; traverse(u,
vis);
for(int i = 0; i<NODE; i++) {
if(!vis[i])
return false;
}
}
return true;
}

int main() {
if(isConnected()) {
cout << "The Graph is connected.";

13 | Page
 }
else
cout << "The Graph is not connected.";
}

14 | Page
INPUT / OUTPUT

Checking whether a given graph is connected or not using DFS method

15 | Page
 EXPERIMENT - 4

SUM OF SUB SETS PROBLEM

OBJECTIVE:

Find a subset of a given set S = {sl, s2 sn} of n positive integers whose sum is equal to a given
positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1, 2, 6} and {1,
8}.A suitable message is to be displayed if the given problem instance doesn't have a solution.

PACKAGES / SOFTWARE REQUIRED:

Code Blocks

THEORY:

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set
with sum equal to given sum.

PROGRAMMING LOGIC:

PROCEDURE:

Create: Open Dev C++, write a program after that save the program with .cpp extension.
Compile: Alt + F9
Execute: Ctrl + F10
SOURCE CODE:

12 | Page
 #include <iostream>
using namespace
std;

void displaySubset(int subSet[], int size) {

for(int i = 0; i < size; i++) {
cout << subSet[i] << " ";
}
cout << endl;
}

void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
displaySubset(subSet, subSize); subsetSum(set,subSet,n,subSize-1,total-
set[nodeCount],nodeCount+1,sum); return;
}else {
for( int i = nodeCount; i < n; i++ ) { subSet[subSize] =
set[i]; subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);
}
}
}

void findSubset(int set[], int size, int sum) {

int *subSet = new int[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
delete[] subSet;
}

int main() {
int weights[] = {10, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size,
35);

INPUT/ OUTPUT

EXPERIMENT - 5

13 | Page
 MINIMUM COST SPANNING TREE

OBJECTIVE:

Find Minimum Cost Spanning Tree of a given undirected graph using Prim's algorithm.

PACKAGES / SOFTWARE REQUIRED:

Code Blocks

THEORY:

Prim’s algorithm is also a Greedy Algorithm. It starts with an empty spanning tree. The idea is to
maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set
contains the vertices not yet included. At every step, it considers all the edges that connect the two sets,
and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint
of the edge to the set containing MST.

PROGRAMMING LOGIC:

PROCEDURE:

Create: Open Dev C++, write a program after that save the program with .c extension.
Compile: Alt + F9
Execute: Ctrl + F10

14 | Page
 SOURCE CODE :

#include <limits.h>

#include <stdbool.h>

#include <stdio.h>

#define V 5

int minKey(int key[], bool mstSet[])

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) if (mstSet[v]

== false && key[v] < min) min =

key[v], min_index = v;

return min_index;

int printMST(int parent[], int graph[V][V])

printf("Edge \tWeight\n"); for (int i = 1; i < V; i++)

printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);

void primMST(int graph[V][V])

{
int parent[V];

15 | Page
 int key[V];

bool mstSet[V];

for (int i = 0; i < V; i++) key[i] =

INT_MAX, mstSet[i] = false;

key[0] = 0;

parent[0] = -1;

for (int count = 0; count < V - 1; count++) {

int u = minKey(key, mstSet);

mstSet[u] = true;

for (int v = 0; v < V; v++) if (graph[u][v] && mstSet[v] == false

&& graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v];

16 | Page
 printMST(parent, graph);

int main()

int graph[V][V] = { { 0, 2, 0, 6, 0 },

{ 2, 0, 3, 8, 5 },

{ 0, 3, 0, 0, 7 },

{ 6, 8, 0, 0, 9 },

{ 0, 5, 7, 9, 0 } };

primMST(graph);

return 0;

INPUT/ OUTPUT

17 | Page
18 | Page