lOMoARcPSD|8580907

BCSL-045 - SOLVED ASSIGNMENT

Bachelor of computer application (Indira Gandhi National Open University)

StuDocu is not sponsored or endorsed by any college or university

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)
 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
Q1.
Write and test a program to sort the following array of 10 integer numbers using
Selection Sort . Calculate the numbers of times the outer loop, inner loop, if
statement and and swap operation will execute in this example. Show all the
intermediate steps.

15 45 60 25 35 8 40 5 10 27

Ans1.
The selection sort algorithm sorts an array by repeatedly finding the minimum element
(considering ascending order) from unsorted part and putting it at the beginning. The
algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order)
from the unsorted subarray is picked and moved to the sorted subarray.
Following example explains the above steps:
arr[] = 15 45 60 25 35 8 40 5 10 27

// Find the minimum element in arr[0...10]

// and place it at beginning
5 15 45 60 25 35 8 40 10 27

// Find the minimum element in arr[1...9]

// and place it at beginning of arr[1...9]
5 8 10 15 45 60 25 35 40 27

// Find the minimum element in arr[2...8]

// and place it at beginning of arr[2...8]
5 8 10 15 45 60 25 35 40 27

// Find the minimum element in arr[3...7]

// and place it at beginning of arr[3...7]
5 8 10 15 45 60 25 35 40 27
// Find the minimum element in arr[4...6]
// and place it at beginning of arr[4...6]
5 8 10 15 25 45 60 35 40 27
// Find the minimum element in arr[5...5]
// and place it at beginning of arr[5...5]
5 8 10 15 25 27 45 60 35 40
// Find the minimum element in arr[6...4]
// and place it at beginning of arr[6...4]
5 8 10 15 25 27 35 40 45 60

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
// Find the minimum element in arr[7...3]
// and place it at beginning of arr[7...3]
5 8 10 15 25 27 35 40 45 60
// Find the minimum element in arr[8...2]
// and place it at beginning of arr[8...2]
5 8 10 15 25 27 35 40 45 60
// Find the minimum element in arr[9...1]
// and place it at beginning of arr[9...1]
5 8 10 15 25 27 35 40 45 60

Q2.
Implement Binary Search algorithm to search for a number 70 in the following sorted
array of 10 integer numbers. Calculate the total no of mid operations, if statement and
else if comparison operations and the number of times the loop will execute.
5 10 25 30 37 46 55 60 65 70

Ans2.
Search 70
5 10 25 30 37 46 55 60 65 70

70>37
Take 2nd half
L=0 M=4 H=9
5 10 25 30 37 46 55 60 65 70

70>60
Take 1st half L=5 M=7 H=9
5 10 25 30 37 46 55 60 65 70

Found 70,
Return 5
5 10 25 30 37 46 55 60 65 70

A Binary Search is a sorting algorithm, that is used to search an element in a sorted array.
A binary search technique works only on a sorted array, so an array must be sorted to apply

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
binary search on the array. It is a searching technique that is better then the liner search
technique as the number of iterations decreases in the binary search.

The logic behind the binary search is that there is a key. This key holds the value to be
searched. The highest and the lowest value are added and divided by 2. Highest and lowest
and the first and last element in the array. The mid value is then compared with the key. If
mid is equal to the key, then we get the output directly. Else if the key is greater then mid
then the mid+1 becomes the lowest value and the process is repeated on the shortened
array. Else if the key value is less then mid, mid-1 becomes the highest value and the
process is repeated on the shortened array. If it is not found anywhere, an error message is
displayed.

Let us move further with this Binary Search In C article and see an example,

Let’s look at the code:

#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100];
printf("Enter number of elementsn");
scanf("%d",&n);
printf("Enter %d integersn", n);
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Enter value to findn");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high) {
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key) {
printf("%d found at location %d.n", key, mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("Not found! %d isn't present in the list.n", key);
return 0;
}
Output:
If the key is present

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21

Q3.
Write a program to traverse a graph using DFS. Apply this algorithm to the following
graph and write the sequence of vertices to be travelled. Also calculate the number of
times the for loop and if condition will execute in this example.

Ans3.
Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The
only catch here is, unlike trees, graphs may contain cycles, a node may be visited twice. To avoid
processing a node more than once, use a boolean visited array.

Example:

Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3

Explanation:

DFS Diagram

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21

Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Output: DFS from vertex 2 : 2 0 1 3

Explanation:

DFS Diagram:

Q4.
Write a program to find the maximum of the following list of integer numbers:
15, 20, 5, 4, 3, 17, 35.
Calculate (i) the number of times the loop will execute and (ii) the number of times the if
statement will run in this s example.

Ans4.

Algorithm:

Step 1: Start
Step 2: Read n and a[i] as integers

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
Step 3: Declare maxpos as 1
Step 4: Assign max ← A[1]
Step 5: for i: 1 to n increment i by 1
begin
if(max < A[i])
begin
max ← A[i];
maxpos ← i;
end
end
Step 6: Assign min← A[1];
Declare minpos as 1;
Step 7: for i: 1 to n increment i by 1
begin
if(min>A[i])
begin
min ← A[i];
minpos ← i;
end
end

Program:

#include <stdio.h>
#include <conio.h>
void main()
{
int a[25], i, large, small, n;
clrscr();
printf("Enter the size of array(max 35)\n");
scanf("%d", &n);
printf("Enter any %d integer array elements\n",n);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
large = a[0];
small = a[0];
for(i = 1; i < n ; i++)
{
if(a[i] > large)
{
large = a[i];
}
if(a[i] < small)
{
small = a[i];
}
}

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
printf("The largest element from the given array is %d \nThe smallest element from the given
array is %d", large, small);
getch();
}

Input & Output:

Enter the size of array(max 35)

5
Enter any 5 integers array elements
15, 20, 5, 4, 3, 17, 35.
The largest element from the given array is 35
The smallest element from the given array is 3

Q5.
Implement Prim’s algorithm to find a minimum cost spanning tree of the following graph and
print the result . Represent the graph through adjacency matrix,

Ans5.
We have discussed Kruskal’s algorithm for Minimum Spanning Tree. Like Kruskal’s algorithm,
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.
A group of edges that connects two set of vertices in a graph is called cut in graph theory. So, at
every step of Prim’s algorithm, we find a cut (of two sets, one contains the vertices already
included in MST and other contains rest of the vertices), pick the minimum weight edge from the
cut and include this vertex to MST Set (the set that contains already included vertices).
How does Prim’s Algorithm Work? 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.

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
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, iterate through 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.

Let us understand with the following 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 the 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.

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
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 (1
and 7 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.

Q6.
Implement Horner’ rule for evaluating the following polynomial expression at x =5. Calculate the
total number of times additions and multiplication operations will ocuur in this example
p(x) = 3𝑥5 - 4𝑥4+5𝑥3 - 6x + 9

Ans6.
Given a polynomial of the form cnxn + cn-1xn-1 + cn-2xn-2 + … + c1x + c0 and a value of
x, find the value of polynomial for a given value of x. Here cn, cn-1, .. are integers (may be
negative) and n is a positive integer.
Input is in the form of an array say poly[] where poly[0] represents coefficient for xn and poly[1]
represents coefficient for xn-1 and so on.

Examples:
// Evaluate value of 2x3 - 6x2 + 2x - 1 for x = 5
Input: poly[] = {2, -6, 2, -1}, x = 5
Output: 5

// Evaluate value of 2x3 + 3x + 1 for x = 5

Input: poly[] = {2, 0, 3, 1}, x = 2
Output: 23

A naive way to evaluate a polynomial is to one by one evaluate all terms. First calculate xn,
multiply the value with cn, repeat the same steps for other terms and return the sum. Time

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
complexity of this approach is O(n2) if we use a simple loop for evaluation of xn. Time
complexity can be improved to O(nLogn) if we use O(Logn) approach for evaluation of xn.
Horner’s method can be used to evaluate polynomial in O(n) time. To understand the method, let
us consider the example of 2x3 – 6x2 + 2x – 1. The polynomial can be evaluated as ((2x – 6)x +
2)x – 1. The idea is to initialize result as coefficient of xn which is 2 in this case, repeatedly
multiply result with x and add next coefficient to result. Finally return result.

#include <iostream>
using namespace std;

// returns value of poly[0]x(n-1) + poly[1]x(n-2) + .. + poly[n-1]

int horner(int poly[], int n, int x)
{
int result = poly[0]; // Initialize result

// Evaluate value of polynomial using Horner's method

for (int i=1; i<n; i++)
result = result*x + poly[i];

return result;
}

// Driver program to test above function.

int main()
{
// Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
int poly[] = {2, -6, 2, -1};
int x = 3;
int n = sizeof(poly)/sizeof(poly[0]);
cout << "Value of polynomial is " << horner(poly, n, x);
return 0;
}

Output:
Value of polynomial is 5

Q7.
Write a program to count the number of times an integer number 12 has occurred in the following
array of 10 integer numbers.
15, 20, 35, 12, 11, 8 ,12, 7, 12, 16
Calculate the number of times (i) loop statement and (ii) increment operations will execute in this
example.

Ans7.
Given an array of positive integers. All numbers occur even number of times except one number
which occurs odd number of times. Find the number in O(n) time & constant space.

Examples:

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3

Input : arr = {5, 7, 2, 7, 5, 2, 5}

Output : 5

A Simple Solution is to run two nested loops. The outer loop picks all elements one by one and
inner loop counts number of occurrences of the element picked by outer loop. Time complexity
of this solution is O(n2).
Below is the implementation of the brute force approach:
// C++ program to find the element
// occurring odd number of times
#include<bits/stdc++.h>
using namespace std;

// Function to find the element

// occurring odd number of times
int getOddOccurrence(int arr[], int arr_size)
{
for (int i = 0; i < arr_size; i++) {

int count = 0;

for (int j = 0; j < arr_size; j++)

{
if (arr[i] == arr[j])
count++;
}
if (count % 2 != 0)
return arr[i];
}
return -1;
}

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)

 lOMoARcPSD|8580907

NAME: VIKASH JOSHI

COURSE CODE: BCSL-045
COURSE TITILE: Introduction to Algorithm design Lab
ASSIGNMENT NUMBER: BCA(4)/L-045/Assignment/2020-21
// driver code
int main()
{
int arr[] = { 2, 3, 5, 4, 5, 2,
4, 3, 5, 2, 4, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);

// Function calling
cout << getOddOccurrence(arr, n);

return 0;
}
Output :
5

Downloaded by vishwas bhati (vishwasbhati96@gmail.com)