BCSL-045 ASSIGNMENT SOLUTION (2018-19)

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.

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

 85 45 70 30 25 35 40 5 10 17

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

 #include 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, 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

#include<stdio.h>
void main()
{
char s1="ABCDEFGH";
char s2="JKLMN";
int i, pos=-1;
char s3;
/* 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.

 80 75 32 44 50 60 65 70 27 14

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

 #include /* 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 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: 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 Process of Dijkstra’s algorithm

• 1) Create a set "SPT Set" (Shortest Path Tree Set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.

• 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.

• 3) While sptSet doesn’t include all vertices -

• Pick a vertex u which is not there in sptSetand has minimum distance value.
• Include u to sptSet.
• Update distance value of all adjacent vertices of u.

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 }. 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 