BCSL-045 ASSIGNMENT SOLUTION (2018-19)

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


In this ASSIGNMENT all the below PROGRAMMINGS are written and run in Turbo C++ 3.0

We have removed clrscr( ) and getch( ) functions from each programming because of different version of C compiler.


Question 1 :

Consider a complete graph with five vertices. Write a C-program to store it by adjacency matrix and adjacency list.

Answer : -

Following is an example of an undirected graph with 5 vertices


The adjacency matrix for the above example graph is :


The adjacency list for the above example graph is :

#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[5][5];
struct list *array[5], *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<5;i++)
{
for(j=0;j<5;j++)
{
matrix[i][j] = 0;
}
}
/* Generate adjacency matrix from the inputed graph */
for(v=0;v<5;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<5;i++)
{
for(j=0;j<5;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<5;i++)
array[i] = NULL;
/* Generate adjacency list from the inputed graph */
for(v=0;v<5;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<5;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 : 7
Enter an edge (u,v) : 0 1
Enter an edge (u,v) : 0 4
Enter an edge (u,v) : 1 4
Enter an edge (u,v) : 1 3
Enter an edge (u,v) : 1 2
Enter an edge (u,v) : 2 3
Enter an edge (u,v) : 3 4

Adjacency Matrix
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0

Adjacency List
For Vertex 0 :   1   4
For Vertex 1 :   0   2   3   4
For Vertex 2 :   1   3
For Vertex 3 :   1   2   4
For Vertex 4 :   0   1   3




Question 2 :

Implement Merge Sort algorithm recursively to sort the following array

8545703025354051017

and calculate number of comparisons ,exchange operations and number of times the loops will execute in the program.

Answer : -

#include<stdio.h>

int i, j;
/* Global function declaration */
void MergeSort(int a[],int start,int end);
void Merge(int a[],int start,int middle, int end);

void main()
{
int array[]={85, 45, 70, 30, 25, 35, 40, 5, 10, 17};
MergeSort(array,0,9);
for(i=0; i<10; i++)
{
printf("\t%d",array[i]);
}
}

/* MergeSort( ) recursive function */
void MergeSort(int a[],int start,int end)
{
int mid;
if(start < end)
{
/* Divided the current array into 2 parts */
mid = (start + end) / 2;

/* Sort the first part of array */
MergeSort(a, start, mid);
/* Sort the Second part of array */
MergeSort(a, mid+1, end);

/* Merge the both parts by comparing elements of both the parts */
Merge(a, start, mid, end);
}
}

/* Merge( ) function */
void Merge(int a[],int start,int middle, int end)
{
int b[10], k=0;
i=start;
j=middle+1;
while(i <= middle && j <= end)
{
if(a[i] <= a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
}
/* Copy the remaining elements of first half, if there are any */
while(i <= middle)
b[k++]=a[i++];

/* Copy the remaining elements of Second half, if there are any */
while(j <= end)
b[k++]=a[j++];

/* Copying back the sorted list to a[ ] */
for(i=end; i>=start; i--)
a[i]=b[--k];
}



Question 3 :

Write a program to concatenate the following two strings :
String1:“ABCDEFGH”
String2: “ JKLMN”

and calculate
(i) Total number of comparison operations
(ii) Total number of times the loop will execute

Answer : -

#include<stdio.h>
void main()
{
char s1[8]="ABCDEFGH";
char s2[5]="JKLMN";
int i, pos=-1;
char s3[15];
/* Copy first string into s3 */
for(i=0;i<8;i++)
{
s3[++pos]=s1[i];
}
/* Copy second string into s3 */
for(i=0;i<5;i++)
{
s3[++pos]=s2[i];
}
s3[++pos]='\0';
puts(s3);
}




Question 4 :

Implement the Binary Search Algorithm to search for a number 50 in the following array . The array should be sorted using Bubble Sort in the ascending order.

80753244506065702714

and calculate (i)how many comparison and division operations will be required for searching for the number and(ii) the number of times the outer loop will execute in Bubble Sort

Answer : -

#include<stdio.h>

/* Global array declaration */
int array[]={80, 75, 32, 44, 50, 60, 65, 70, 27, 14};
/* Global function declaration */
void BubbleSort(int list[]);
int BinarySearch(int list[],int value);

void main()
{
int number, retn;
printf("\n Enter the number you want to search...");
scanf("%d",&number);
BubbleSort(array);
retn=BinarySearch(array,number);
if(retn == 0)
printf("\n Number not found");
else
printf("\n Number found");
}

/* BubbleSort( ) function */
void BubbleSort(int list[])
{
int len, i, j, temp;
/* Calculate the length of array */
len = (sizeof(array) / sizeof(int));
/* Sort the array using bubble sort method in ascending order*/
for(i=1;i<len;i++)
{
for(j=0;j<len-i;j++)
{
if(list[j] > list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
}
}
}

/* BinarySearch( ) function */
int BinarySearch(int list[],int value)
{
int low=0, mid, high, count=0;
/* Determine the last index number of the array */
high = (sizeof(array) / sizeof(int)) - 1;
while(low <= high)
{
mid = (low + high) / 2;
if(list[mid] == value)
{
count = 1;
break;
}
else
if(list[mid] < value)
low = mid + 1;
else
if(list[mid] > value)
high = mid - 1;
}
return count;
}



Question 5 :

Apply Prim’s algorithm to find a minimum cost spanning tree for the following graph:

Answer : -

Step - 1


Step - 2


Step - 3


Step - 4


Step - 5


Step - 6




Question 6 :

Implement Dijkstra’s algorithm to the following graph and find the shortest path from a node A to the remaining nodes

Answer : -

Process of Dijkstra’s algorithm


Start from vertex A and update distance values of its adjacent vertices which is B, C and E.
Initial STP Set { A }.
Update the distance values of adjacent vertices of A. The distance value of vertex B, C and E becomes 2, 2 and 7 respectively.


Pick the vertex with minimum distance value and not already included in SPT Set. The vertex B is picked and added to SPT Set.
So SPT Set now becomes { A , B }.
Update the distance values of adjacent vertices of B. The distance value of vertex D is 6.


Again pick the vertex with minimum distance value and not already included in SPT Set. The vertex C is picked and added to SPT Set.
So SPT Set now becomes { A , B , C }.
There is no undiscover adjacent vertices of C, but the distance value of vertex E is require to change from 7 to 5.


Next vertex E is picked and added to SPT Set.
So SPT Set now becomes { A , B , C , E }.
Update the distance values of adjacent vertices of E. The distance value of vertex F is 9.


We repeat the above steps until SPT Set doesn’t include all vertices of given graph.


Finally, we get the following Shortest Path Tree (SPT) { A , B , C , E , D , F }.



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