BCSL-045 ASSIGNMENT SOLUTION (2019-20)

Q1. Write a program to compute Xn, where both X and n and integer numbers using left to right binary exponentiation algorithm.

Q2. Write a program to find the largest number in the five array using linear search algorithm. Calculate the total no of comparison operations and the number of times the loop will execute.

 85 45 70 30 25 35 40 5 10 17

 #include //Global array declaration int list[]={ 85, 45, 70, 30, 25, 35, 40, 5, 10, 17 }; void main() { int i, len, max; len=(sizeof(list)/sizeof(int)); max = list; for(i=1;i

Q3. Write a program to traverse a graph using BFS. Apply this algorithm to the following graph and write the sequence of vertices to be travelled. Also calculate the number of times the loop(s) will execute. #include<stdio.h>
#include<stdlib.h>
//Global Function Declaration
void BFS();

// Global Variable Declaration
int number_of_vertices, number_of_edges, discover_top=-1, visited_top=-1, v, i, j, k;
int edges, discovered, visited;

// main( ) function begins
void main()
{
// Input number of vertices present in the graph
printf("\n Enter number of vertices : ");
scanf("%d",&number_of_vertices);
// Input number of edges present in the graph
printf("\n Enter number of edges : ");
scanf("%d",&number_of_edges);
for(i=0; i<number_of_edges; i++)
{
printf("Enter an edge (u,v)...");
scanf("%d%d",&edges[i],&edges[i]);
}
// Input the vertex from where searching process is start
printf("\n Enter the start vertex...");
scanf("%d",&v);
BFS();
printf("\n\n\n Final Visited List : ");
for(i=0; i<=visited_top; i++)
printf("\t%d",visited[i]);
}

// BFS( ) function begins
void BFS()
{
int temp;
int pos,z;
discover_top++;
discovered[discover_top]=v;
printf("\n\n\n Discovered List : \n");
printf("\t%d",v);
for(z=1; z<=number_of_vertices; z++)
{
// Print Discover List
printf("\n\n Discover List : ");
for(i=0;i<=discover_top;i++)
{
printf("\t%d",discovered[i]);
}

// Print Visited List
printf("\n Visited List : ");
for(i=0;i<=visited_top;i++)
{
printf("\t%d",visited[i]);
}

// Find the vertices which connected with the discover vertex
pos=0;
for(i=0; i<number_of_edges; i++)
{
if(edges[i] == discovered)
{
temp[pos]=edges[i];
pos++;
}
}

visited_top++;
visited[visited_top]=discovered;
for(i=1;i<=discover_top;i++)
{
discovered[i-1]=discovered[i];
}
discover_top--;

// Check whether the vertices which connected with the new discover vertex are already discover or not
for(i=0; i<=discover_top; i++)
{
for(j=0;j<pos;j++)
{
if(discovered[i] == temp[j])
{
for(k=j; k<pos-1; k++)
temp[k]=temp[k+1];
pos--;
}
}
}

// Check whether the vertices which connected with the new discover vertex are already visited or not
for(i=0; i<=visited_top; i++)
{
for(j=0;j<pos;j++)
{
if(visited[i] == temp[j])
{
for(k=j; k<pos-1; k++)
temp[k]=temp[k+1];
pos--;
}
}
}

// pos > 0 means that the vertices present in the temp[ ] array are not discovered or visited
if(pos > 0)
{
// Sort the temp[ ] array using Bubble Sort
for(i=1;i<pos;i++)
{
for(j=1;j<=pos-i;j++)
{
if(temp[j-1] > temp[j])
{
v=temp[j-1];
temp[j-1]=temp[j];
temp[j]=v;
}
}
}
// Put all the vertices present in the temp[ ] array into discovered[ ] array
for(i=0;i<pos;i++)
{
discover_top++;
discovered[discover_top]=temp[i];
}
}
}
}

Output

Enter number of vertices : 7

Enter number of edges : 10
Enter an edge (u,v) . . . 1 2
Enter an edge (u,v) . . . 1 4
Enter an edge (u,v) . . . 1 5
Enter an edge (u,v) . . . 2 3
Enter an edge (u,v) . . . 3 5
Enter an edge (u,v) . . . 3 6
Enter an edge (u,v) . . . 4 5
Enter an edge (u,v) . . . 5 6
Enter an edge (u,v) . . . 5 7
Enter an edge (u,v) . . . 6 7

Enter the start vertex . . . 1

 Discover List : 1 Visited List : Discover List : 2     4     5 Visited List : 1 Discover List : 4     5     3 Visited List : 1     2 Discover List : 5     3 Visited List : 1     2     4 Discover List : 3     6     7 Visited List : 1     2     4     5 Discover List : 6     7 Visited List : 1     2     4     5     3 Discover List : 7 Visited List : 1     2     4     5     3     6

Final Visited List : 1     2     4     5     3     6     7 Figure 3.1 - Initial Input Graph Figure 3.2 - After we visit A Figure 3.3 - After we visit B Figure 3.4 - After we visit D Figure 3.5 - After we visit E Figure 3.6 - After we visit C Figure 3.7 - After we visit F Figure 3.8 - After we visit G

Q4. Implement GCD (Greatest common divisor) problem using Euclid’s algorithm. Apply this algorithm to find the output of GCD of 225 and 15. Also calculate how many times the mod and equal operations will execute.

Answer : - The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.

 // Iterative function to calculate GCD of two numbers using Euclid’s algorithm int Euclid(int a int b) { // Do until the two numbers become equal while(a != b) { // Replace large number by its difference with the smaller number if(a > b) a = a - b; else b = b - a; } return a;// or 'b' (since both are equal) }

The version of the Euclidean algorithm described above can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder).

 // Iterative function to calculate GCD of two numbers using Euclid’s algorithm int Euclid(int a int b) { // Do until the remainder become 0 // We assume that 'b' is smaller then 'a' while(b > 0) { // Find the remainder r = a % b; // 'a' becomes 'b' and 'b' becomes 'r' a = b; b = r; } return a; }

Output of GCD of 225 and 15

225 / 15 = 15 and remainder 0. So, GCD of 225 and 15 is 15.

Q5. Implement and apply Kruskal’s algorithm to find a minimum cost spanning tree and test the result for the following graph : fd is the sortest edge, with length 1, so it is highlighted. Next cd is the sortest edge, with length 2, so it is highlighted as the second edge. The next shortest edges are cf and dg, both with length 5. The edge cf is not highlighted because there already exists a path between c and f, so it would form a cycle (cdf) if it were chosen.

dg is highlighted as the third edge. The next smallest edges ate ab and de, both with length 6. ab is chosen arbitrarily, and is highlighted. de is now the sortest edge, with length 6, so it is highlighted. Next sortest edge is ef, with length 7. ef is not highlighted because there already exists a path between e and f.

Next sortest edge is cg, with length 8. cg is also not highlighted because of existence of a path between c and g.

The process continues to highlight the next smallest edge, bf, with length 9. The remaining three edges ac, bc and be with length 10, 12 and 14 respectively are not highlighted, because each edge form a cycle.

Therefore minimum cost spanning tree is - Q6. Implement Karatsuba’s method using Divide & Conquer method to multiply two integer numbers. Test the result in multiplication of the following numbers and count the number of multiplication operations.

532680 * 43286

Answer : - Basically Karatsuba stated that if we have to multiply two n-digit numbers x and y, this can be done with the following operations, assuming that B is the base of m and m < n (for instance: m = n/2)

First both numbers x and y can be represented as x1, x2 and y1, y2 with the following formula :

x = x1 * Bm + x2

y = y1 * Bm + y2

Therefore,   xy = (x1 * Bm + x2)(y1 * Bm + y2)

⇒   xy = x1 * y1 * B2m + x1 * y2 * Bm + x2 * y1 * Bm + x2 * y2

⇒   xy = x1 * y1 * B2m + Bm(x1 * y2 + x2 * y1) + x2 * y2

Let   a = x1 * y1,   b = x1 * y2 + x2 * y1   and   c = x2 * y2

Finally, x * y becomes : xy = a * B2m + b* Bm + c

That is why Karatsuba came up with the brilliant idea to calculate b with the following formula :

b = (x1 + x2)(y1 + y2) - a - c

Example

Consider the following multiplication : 25 * 48

x = 25
x = 2 * 10 + 5   [ x = x1 * Bm + x2 ]

x1 = 2   and   x2 = 5

y = 48
y = 4 * 10 + 8   [ y = y1 * Bm + y2 ]

y1 = 4   and   y2 = 8

a = x1 * y1 = 2 * 4 = 8

c = x2 * y2 = 5 * 8 = 40

b = [(x1 + x2)(y1 + y2) - a - c] = [7 * 12 - 8 - 40] = [84 - 48] = 36

Therefore,   xy = 8 * 102 + 36 * 10 + 40   [ xy = a * B2m + b* Bm + c ]

532680 * 43286

x = 532680
x = 532 * 103 + 680   [ x = x1 * Bm + x2 ]

x1 = 532   and   x2 = 680

y = 43286
y = 43 * 103 + 286   [ y = y1 * Bm + y2 ]

y1 = 43   and   y2 = 286

a = x1 * y1 = 532 * 43 = 22876

c = x2 * y2 = 680 * 286 = 194480

b = [(x1 + x2)(y1 + y2) - a - c] = [1212 * 329 - 22876 - 194480] = 181392

Therefore,   xy = 22876 * 106 + 181392 * 103 + 194480   [ xy = a * B2m + b* Bm + c ]

Q7. Draw a complete graph with 6 vertices. Write a C-Program to represent the graph using adjacency matrix and adjacency list. #include /* Structure Declaration for Adjacency List */ struct list { int vertex; struct list *next; }; /* Global Function Declaration */ void AdjacencyMatrix(); void AdjacencyList(); void insert(int v1,int v2); /* Global Variable Declaration */ int number_of_edges, i, j, v; int edges, matrix; struct list *array, *temp, *p; /* main( ) Function Declaration */ void main() { /* Input number of edges present in the graph */ printf("\n Enter number of edges : "); scanf("%d",&number_of_edges); for(i=0; ivertex); temp = temp->next; } } } /* Function to insert value dynamically */ void insert(int v1,int v2) { if(array[v1] == NULL) { array[v1]=(struct list *) malloc(sizeof(struct list)); array[v1]->vertex = v2; array[v1]->next = NULL; } else { p=(struct list *) malloc(sizeof(struct list)); p->vertex = v2; p->next = NULL; temp=array[v1]; while(temp->next != NULL) temp = temp->next; temp->next = p; } } Output Enter number of edges : 15 Enter an edge (u,v) : 0 1 Enter an edge (u,v) : 0 2 Enter an edge (u,v) : 0 3 Enter an edge (u,v) : 0 4 Enter an edge (u,v) : 0 5 Enter an edge (u,v) : 1 2 Enter an edge (u,v) : 1 3 Enter an edge (u,v) : 1 4 Enter an edge (u,v) : 1 5 Enter an edge (u,v) : 2 3 Enter an edge (u,v) : 2 4 Enter an edge (u,v) : 2 5 Enter an edge (u,v) : 3 4 Enter an edge (u,v) : 3 5 Enter an edge (u,v) : 4 5 Adjacency Matrix 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 Adjacency List For Vertex 0 :   1   2   3   4   5 For Vertex 1 :   0   2   3   4   5 For Vertex 2 :   0   1   3   4   5 For Vertex 3 :   0   1   2   4   5 For Vertex 4 :   0   1   2   3   5 For Vertex 5 :   0   1   2   3   4

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.

MORE TOPIC

WHAT WE DO

 Follow Us 