BCSL-045 ASSIGNMENT SOLUTION (2019-20)

If you have any queries please leave a message here
Your Message
×


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

Answer : -




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.

8545703025354051017

Answer : -

#include<stdio.h>
//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[0];
for(i=1;i<len;i++)
{
if(max < list[i])
max = list[i];
}
printf("\n Maximum Number = %d",max);
}




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.

Answer : -

#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[25][2], discovered[25], visited[25];

// 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][0],&edges[i][1]);
}
// 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[25];
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][0] == discovered[0])
{
temp[pos]=edges[i][1];
pos++;
}
}

visited_top++;
visited[visited_top]=discovered[0];
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 : -




Q5. Implement and apply Kruskal’s algorithm to find a minimum cost spanning tree and test the result for the following graph :

Answer : -

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 : -




Q7. Draw a complete graph with 6 vertices. Write a C-Program to represent the graph using adjacency matrix and adjacency list.

Answer : -

#include<stdio.h>
/* 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[20][2], matrix[6][6];
struct list *array[6], *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; i<number_of_edges; i++)
{
printf("\n Enter an edge (u,v) : ");
scanf("%d%d",&edges[i][0],&edges[i][1]);
}
AdjacencyMatrix();
AdjacencyList();
}

/* Function to print the Adjacency Matrix of the graph given above */
void AdjacencyMatrix()
{
/* Matrix initialization */
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
matrix[i][j] = 0;
}
}
/* Generate adjacency matrix from the inputed graph */
for(v=0;v<6;v++)
{
for(i=0; i<number_of_edges; i++)
{
if(edges[i][0] == v)
matrix[v][edges[i][1]] = 1;
if(edges[i][1] == v)
matrix[v][edges[i][0]] = 1;
}
}
/* Print the Matrix after calculation */
printf("\n Adjacency Matrix \n");
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf(" %d",matrix[i][j]);
}
printf("\n");
}
}

/* Function to print the Adjacency List of the graph given above */
void AdjacencyList()
{
/* Initialize the list with NULL value */
for(i=0;i<6;i++)
array[i] = NULL;
/* Generate adjacency list from the inputed graph */
for(v=0;v<6;v++)
{
for(i=0; i<number_of_edges; i++)
{
if(edges[i][0] == v)
insert(v,edges[i][1]);
if(edges[i][1] == v)
insert(v,edges[i][0]);
}
}
/* Print the List after calculation */
printf("\n Adjacency List");
for(i=0;i<6;i++)
{
temp = array[i];
printf("\n For Vertex %d : ",i);
while(temp != NULL)
{
printf("\t%d",temp->vertex);
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



ABOUT US

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


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us