Laboratory Manual

For
Analysis and Design of Algorithms
(3150703)

Branch: Computer
Engineering Academic Year:
2021 – 2022 Prepared By:
Monali Panchal

BHAGWAN ARIHANT INSTITUE OF

TECHNOLOGY, SURAT
 Bhagwan Arihant Institute of Technology
Subject: Analysis and Design of Algorithms (3150703)
Practical List

Sr. No. Title

Implementation & Time analysis of sorting algorithms. (Bubble sort, Selection sort,
1
Insertion sort, Merge sort, Quick sort).

2 Implementation & Time analysis of linear and binary search algorithm.

3 Implementation of max-heap sort algorithm.

Implementation & Time analysis of factorial program using iterative and recursive
4
method.

5 Implementation of a knapsack problem using dynamic programming.

6 Implementation of chain matrix multiplication using dynamic programming.

7 Implementation of making a change problem using dynamic programming.

8 Implementation of a knapsack problem using greedy algorithm.

9 Implementation of Graph and Searching (DFS and BFS).

10 Implement Prim’s algorithm.

11 Implement Kruskal’s algorithm.

12 Implement LCS problem.

 ADA [3150703]

PRACTICAL – 1
AIM: Implementation & Time analysis of sorting algorithms.
(Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort)
1) Bubble Sort
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 20
void bubblesort(int A[SIZE],int );
void main()
{
int A[SIZE], i, n;
clrscr();
printf("\n******************* Bubble Sort *******************\n");
printf("\nEnter the number of elements you want to enter: ");
scanf("%d",&n);
for (i=0; i<n;i++)
{
printf("\nEnter %d Element: ",i+1);
scanf("%d",&A[i]);
}
bubblesort(A,n);
getch();
}
void bubblesort(int A[SIZE],int n)
{
int i, j, m, temp;
for (i=0;i<n-1;i++)
{
for (j=0;j<n;j++)
{
if(A[j] > A[j+1])
{

BAIT, Page 1
 ADA [3150703]

temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
printf("\nSorted Array is: \n");
for (i=0;i<n;i++)
{
printf("\t%d",A[i]);
}
}

Output:

BAIT, Page 2
 ADA [3150703]

2) Selection Sort
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 20
void selection(int A[SIZE], int);
void main()
{
int A[SIZE], n, i;
clrscr();
printf("\n********************* Selection Sort *********************\n");
printf("Enter the number you want to inseart: ");
scanf("%d",&n);
for (i=0;i<n;i++)
{
printf("\nEnter %d Element: ",i+1);
scanf("%d",&A[i]);
}
selection(A, n);
getch();
}
void selection(int A[SIZE], int n)
{
int min, j, i, temp;
for (i=0; i<n-2; i++)
{
min = i;
for(j=i+1; j<=n-1; j++)
{
if(A[j]< A[min])
{
min = j;
}

BAIT, Page 3
 ADA [3150703]

}
temp = A[i];
A[i] = A[min];
A[min] = temp;
}
printf("Sorted Array is : \n");
for(i=0; i<n; i++)
{
printf("\t%d",A[i]);
}
}

Output:

BAIT, Page 4
 ADA [3150703]

3) Insertion Sort
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 20
void insertion(int A[SIZE], int n);
void main()
{
int A[SIZE],n,i;
clrscr();
printf("\n***************** Insertion Sort
*****************"); printf("\nNumber of elements you want in
Array: "); scanf("%d",&n);
for(i=0; i<n; i++)
{
printf("Enter the %d element: ",i+1);
scanf("%d",&A[i]);
}
insertion(A, n);
getch();

}
void insertion(int A[SIZE],int n)
{
int i,j,temp;
for(i=1;i<=n-1;i++)
{
temp = A[i];
j=i-1;
while((j>=0) && (A[j]>temp))
{
A[j+1]=A[j];
j--;

BAIT, Page 5
 ADA [3150703]

}
A[j+1] = temp;
}
printf("\nSorted Array is: \n");
for (i=0; i<n; i++)
{
printf("\t%d",A[i]);
}
}

Output:

BAIT, Page 6
 ADA [3150703]

4) Merge Sort
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 20
void MergeSort(int A[SIZE], int, int);
void Display(int A[SIZE], int);
void Combine(int A[SIZE], int, int, int);
void main()
{
int i,low, high, n, A[SIZE];
clrscr();
printf("\n***************** Merge Sort ******************\n");
printf("Number of Elements you want in Array: ");
scanf("%d",&n);
for (i=0; i<n; i++)
{
printf("\nEnter %d Element: ",i+1);
scanf("%d",&A[i]);
}
low = 0;
high = n-1;
MergeSort(A, low, high);
Display(A, n);
getch();
}
void MergeSort(int A[SIZE], int low, int high)
{
int mid;
if(low < high)
{
mid = (low + high)/2;
MergeSort(A, low, mid);

BAIT, Page 7
 ADA [3150703]

MergeSort(A, mid+1, high);

Combine(A, low, mid, high);
}
}
void Combine(int A[], int low, int mid, int high)
{
int i = low, k = low, j = mid+1;
int temp[SIZE];
while(i<= mid && j <= high)
{
if(A[i] <= A[j])
{
temp[k] = A[i];
i++;
k++;
}
else
{
temp[k] = A[j];
j++;
k++;
}
}
while(i<= mid)
{
temp[k] = A[i];
i++;
k++;
}
while (j <= high)
{
temp[k] = A[j];
j++;
k++;

BAIT, Page 8
 ADA [3150703]

}
for (k = low; k <= high; k++)
{
A[k] = temp[k];
}
}
void Display(int A[SIZE], int n)
{
int i;
printf("\n\nSorted Array is \n");
for (i = 0; i<n; i++)
printf("\t%d",A[i]);
}

Output:

BAIT, Page 9
 ADA [3150703]

5) Quick Sort
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 20
void Quick(int A[SIZE],int,int);
int Partition(int A[SIZE],int,int);
void swap(int A[SIZE], int*, int*);
int n;
int main()
{
int i;
int A[SIZE];
clrscr();
printf("\n**************Quick Sort Method****************\n");
printf("\n Enter Total Numbet to Insert into Array: ");
scanf("%d",&n);
for (i=0; i<n; i++)
{
printf("\n Enter %d Number: ",i+1);
scanf("%d",&A[i]);
}
Quick(A,0,n - 1); printf("\n\
tSorted Array is: \n");

for (i=0; i< n; i++)

{
printf("\t%d",A[i]);
}
getch();
return 0;
}

BAIT, Page
 ADA [3150703]

void Quick(int A[SIZE], int low, int high)

{
int m, i;

if(low < high)

{
m = Partition(A, low, high);
Quick(A, low, m - 1);
Quick(A, m + 1, high);
}
}

int Partition(int A[SIZE], int low, int high)

{
int pivot = A[low], i = low, j = high;

while (i<=j)
{
while (A[i] <= pivot)
{
i = i + 1;
}
while(A[j] >pivot){
j = j - 1;
}

if(i<j){
swap(A, &i, &j);
}

}
swap(A, &low, &j);
return j;
}

BAIT, Page
 ADA [3150703]

void swap(int A[SIZE],int *i, int *j)

{
int temp;
temp = A[*i];
A[*i] = A[*j];
A[*j] = temp;
}

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 2
AIM: Implementation & Time analysis of linear and binary search
algorithm.
1) Linear Search
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 25
int search(int A[SIZE], int, int);
void main()
{
int A[SIZE], key, st=0, n, i;
clrscr();
printf("\n**************** Linear Search ****************\n");
printf("\nNumber of elements in Array: ");
scanf("%d",&n);
for(i=0; i< n; i++)
{
printf("\nEnter %d Element: ", i+1);
scanf("%d",&A[i]);
}
printf("\nEnter the Element Which You Wish to Search: ");
scanf("%d",&key);
st = search(A, key, n);
if(st == 0)
{
printf("\nElement is Not Found");
}else
{
printf("\nElement is Present at A[%d] ",st);
}
getch();
}

BAIT, Page
 ADA [3150703]

int search(int A[SIZE], int key, int n)

{ int i;
for(i=0; i<n; i++)
{
if(A[i] == key){
return i;
}
}
}

Output:

BAIT, Page
 ADA [3150703]

2) Binary Search
Code:
#include<stdio.h>
#include<conio.h
> #define SIZE 25
int BinSearch(int A[SIZE], int, int, int);
void main()
{
int A[SIZE], key, st=0, n, i, low, high;
clrscr();
printf("\n**************** Binary Search ****************\n");
printf("\nNumber of elements in Array: ");
scanf("%d",&n);
for(i=0; i< n; i++)
{
printf("\nEnter %d Element: ", i+1);
scanf("%d",&A[i]);
}
printf("\nEnter the Element Which You Wish to Search: ");
scanf("%d",&key);
low = 0;
high = n-1;
st = BinSearch(A, key, low, high);
if(st == 0)
{
printf("\nElement is Not Found");
}else
{
printf("\nElement is Present at A[%d] ",st);
}
getch();
}
int BinSearch(int A[SIZE], int key, int low, int high)
{

BAIT, Page
 ADA [3150703]

int mid;
mid = (low+high)/2;
if(key == A[mid])
return mid;
else if(A[mid] > key)
BinSearch(A, key, low, mid - 1);
else

BinSearch(A, key, mid + 1, high);

}

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 3
AIM:Implementation of max-heap sort algorithm.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 10
int main(){
int i,n;
int arr[MAX];
void makeHeap(int arr[MAX], int n);
void heapSort(int arr[MAX], int n);
void display(int arr[MAX], int n);
for ( i = 0; i< MAX; i++)
{
arr[i] = 0;
}
printf("\n How many element you want to insert ? \n ");
scanf("%d",&n);
printf("\n Enter the element : \n ");
for ( i = 0; i< n; i++)
{
scanf("%d",&arr[i]);
}
printf("\n The elements are : ");
display(arr,n);
makeHeap(arr,n);
printf("\n Heapified ");
display(arr,n);
heapSort(arr,n);
printf("\n Element sorted by heap sort");
display(arr,n);
getch();

BAIT, Page
 ADA [3150703]

return 0;
}
void makeHeap(int arr[MAX], int n){
int i,val,j,father;
for ( i = 1; i< n; i++){
val = arr[i];
j = i;
father = (j-1)/2;
while (j>0 &&arr[father]<val){
arr[j] = arr[father];
j = father;
father = (j-1)/2;
}
arr[j] = val;
}
}
void heapSort(int arr[MAX], int n){
int i,k,temp,j;
for ( i = n-1; i> 0; i--){
temp = arr[i];
arr[i] = arr[0];
k = 0;
if (i == 1){
j = -1;
}
else{
j = 1;
}
if (i>2 &&arr[2] >arr[1]){
j = 2;
}
while (j >= 0 && temp <arr[j]){
arr[k] = arr[j];
k = j;

BAIT, Page
 ADA [3150703]

j = 2*k+1;
if (j+1 <= i-1 &&arr[j]<arr[j+1]){
j++;
}
else{
j = -1;
}
}
arr[k] = temp;
}
}
void display(int arr[MAX], int n){
int i;
for ( i = 0; i< n; i++) {
printf("\n %d",arr[i]);
}
printf("\n");
}

Output:

BAIT, Page
 ADA [3150703]

BAIT, Page
 ADA [3150703]

PRACTICAL – 4
AIM:Implementation & Time analysis of factorial program using iterative
and recursive method.
1) Iterative Method
Code:

#include<stdio.h>
#include<conio.h
void main()
{
int n;
long f;
long fact(int n);
clrscr();
printf("Enter a number: ");
scanf("%d", n);
if(n<0)
{
printf("Negative Integers are not allowed");
}else{
f = fact(n);
printf("Factorial of %n is %ld ", n, f);
}
getch();
}
long fact(int n)
{
int i;
long f = 1;
for (i=1; i<=n; i++)
{
f = f*i;
}
return f;

BAIT, Page
 ADA [3150703]

}
Output:

2) Recursive Method
Code:

#include<stdio.h>
#include<conio.h
> void main()
{
int n;
long f;
long fact(int n);
printf("Enter a Number: ");
scanf("%d", &n);
if (n<0)
{
printf("Negative integers are not allowed.");
}
else{
f = fact(n);
printf("Factorial of %d is %ld.", n, f);
}

getch();
}

long fact(int
n)
{
if (n == 0)
{
return 1;

BAIT, Page
 ADA [3150703]

BAIT, Page
 ADA [3150703]

}
else {

return (n*fact(n-1));
}
}

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 5
AIM:Implementation of a knapsack problem using dynamic programming.
Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int table[5][6];
int max(int, int);
void main()
{
int w[]={0,2,3,4,5};
int v[]={0,23,4,15,19};
int W=5;
int n=4;
int i,j;
void DKP(int n,intW,int w[],int v[]);
clrscr();
printf("\n\t\t Knapscak problem using dynamic programming:");
printf("\n given data...\n");
printf("\n w[i] v[i]");
printf("\n _");
for(i=1;i<=n;i++)
printf("\n %d %d", w[i], v[i]);
printf("\n\n Capacity = %d",W);
printf("\n\n");
for(i=0;i<=n;i++)
{
for(j=0;j<=W;j++)
{
table[i][j]=0;
}

BAIT, Page
 ADA [3150703]

}
DKP(n,W,w,v);
}
void DKP(int n,intW,int w[5],int v[5])
{
int i,j;
int val1,val2;
void find_item(int, int, int[]);
for(i=0;i<=n;i++)
{
for(j=0;j<=W;j++)
{
table[i][0]=0;
table[0][j]=0;
}
}
for(i=1;i<=W;i++)
{
for(j=1;j<=W;j++)
{
if(j < w[i])
table[i][j] = table[i-1][j];
else if(j >= w[i])
{
val1 = table[i-1][j];
val2 = v[i] + table[i-1][j-w[i]];
table[i][j] = max(val1,val2);
}
}
}
printf("\n Table constructed using dynamic programing id...\n");
for(i=0;i<=n;i++)
{
for(j=0; j<=W; j++)

BAIT, Page
 ADA [3150703]

printf(" %d\t", table[i][j]);

printf("\n");
}
find_item(n,W,w);
}
int max(int a,int b)
{
if(a>b)
{

return a;
}
else
{

return b;
}
}
void find_item(int i,intk,int w[5])
{
printf("\n Solution for the knapsack...");
while(i>0 && k>0)
{
if(table[i][k] != table[i-1][k])
{
printf("\n Item %d is selected",i);
i=i-1;
k = k-w[i];
}
else
i=i-1;
}
}

BAIT, Page
 ADA [3150703]

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 6
AIM: Implementation of chain matrix multiplication using dynamic
programming.
Code:
#include<stdio.h>
#include<conio.h>

void main()
{
int n, i, cost, p[100], s[20][20];
int Matrix_chain(int s[20][20], int p[], int, int);
void display_matrix_order(int s[20][20], int i, int j);
clrscr();
printf("\n\t\tChain Matrix Multiplication Using Dynamic Programming\n");
printf("\n Enter the number of matrices: ");
scanf("%d", &n);
for(i=0; i<n+1; i++)
{
printf("\n Enter the Dimension of the matrix: ");
scanf("%d", &p[i]);
}
cost = Matrix_chain(s, p, 1, n);
printf("\n The Optimal Cost: %d\n", cost);
printf("\n The Optimal Order: ");
display_matrix_order(s, 1, n);
getch();
}

int Matrix_chain(int s[20][20], int p[], int i, int j)

{
int k, count;
long min = 9999999;
if(i == j)

BAIT, Page
 ADA [3150703]

return 0;
for(k=i; k<j; k++)
{
count = Matrix_chain(s, p, i, k) + Matrix_chain(s, p, k+1, j) + p[i-1] *
p[k] *
p[j];
if (count < min)
{
min = count;
s[i][j]= k;
}
}
return min;
}
void display_matrix_order(int s[20][20], int i, int j)
{
if(i == j)
printf("A%d ", i);
else
{

printf("( ");
display_matrix_order(s, i, s[i][j]);
display_matrix_order(s, s[i][j] + 1, j);
printf(") ");
}
}

BAIT, Page
 ADA [3150703]

BAIT, Page
 ADA [3150703]

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 7
AIM: Implementation of making a change problem using dynamic
programming.
Code:
#include<stdio.h>
#include<conio.h>
#define MAX 20

int main()
{
int d[5];
int NumberofCoins(int [10], int, int);
int n,N,i;

printf("\nEnter the number of Units: ");

scanf("%d", &n);
printf("\nEnter the value of coins: ");
for(i=1; i<= n; i++)
scanf("%d", &d[i]);
printf("\nEnter total units for which the changes if required: ");
scanf("%d",&N);
printf("\nMinimum Number of Coins %d ", NumberofCoins(d, n, N));
getch();
return 0;
}

int NumberofCoins(int d[MAX], int n, int N)

{
int minval(int x, int y);
int i,j, c[10][10];
for (i=0; i<=n; i++)
for(j =0; j<=N; j++)
c[i][j] = 999;

BAIT, Page
 ADA [3150703]

for(i=0; i<= n; i++)

c[i][0] = 0;
for (j=1; j<= N; j++)
c[0][j] = j;

for(j =1; j<= N; j++)

{
for(i=1; i<= n; i++)
{
if(i == 1)
{
if(j < d[i])
c[i][j] = 9999;
else
c[i][j] = 1+c[i][j - d[1]];
}
else if(j < d[i])
c[i][j] = c[i-1][j];
else
c[i][j] = minval(c[i-1][j], 1+c[i][j - d[i]]);
}
}
printf("\n Printing the table for number of coins\n");

for(i =0; i<= n; i++)

{
for(j=0; j<=N; j++)
{
printf("%d ", c[i][j]);
}
printf("\n");
}
return c[n][N];
}

BAIT, Page
 ADA [3150703]

int minval(int x, int y)

{
if(x<y)

return x;
else

return y;
}

Output:

BAIT, Page
 ADA [3150703]

BAIT, Page
 ADA [3150703]

PRACTICAL – 8
AIM:Implementation of a knapsack problem using greedy programming.
Code:

#include<stdio.h>
#include<conio.h>

void knapsack(int n,float m, float w[], float p[]);

void main()
{
int i, j, n;
float p[15], w[15], c[15], temp, m;
clrscr();
printf("\n Enter Number of Objects: ");
scanf("%d", &n);
printf("\n Enter Weights: ");
for(i=0; i<n; i++)
scanf(" %f", &w[i]);
flushall();
printf("\n Enter Profit: ");
for(i = 0;i<n;i++)
scanf(" %f", &p[i]);
printf("\n Enter knapsack size: ");
scanf(" %f", &m);

for(i=0; i<n; i++)

c[i] = p[i]/w[i];

for(i=0; i<n;i++)
{
for(j=0; j<n-1; j++)
{

BAIT, Page
 ADA [3150703]

if(c[i] < c[i+1])

{
temp = c[j];
c[j] = c[j+1];
c[j+1] = temp;

temp = w[i];
w[i] = w[i+1];
w[i+1] = temp;

temp = p[j];
p[j] = p[j+1];
p[j+1] = temp;
}
}
}
printf("\n The items are arranged as....\n");
printf("\n\n\tItems\tWeight\tProfit");

for(i=0;i<n; i++)
printf("\n\tx[%i]\t%.0f\t%.0f", i, w[i], p[i]);
knapsack(n, m, w, p);
getch();
}

void knapsack(int n, float m, float w[], float p[])

{
float x[15], U, profit = 0.0, weight = 0.0;
int i;
U = m;

for(i=0; i<n;i++)
x[i] = 0.0;
for (i=0; i<n; i++)

BAIT, Page
 ADA [3150703]

if(w[i] >U)
break;
x[i] = 1.0;
U= U-w[i];
}
if(i<n
)
x[i] = U/w[i];

printf("\n The Solution Vector is: ");

for(i=0; i<n ; i++)

printf("\n %d\t%.2f", i, x[i]);

for(i=0; i<n; i++)

{
w[i] = w[i] * x[i];
p[i] = p[i] * x[i];
}

for(i=0; i<n; i++)

{
profit = profit + p[i];
weight = weight + w[i];
}

printf("\n Maximum Profit is: ");

printf("\n\t\t %.2f", profit); printf("\
n Maximum Weight is: "); printf("\
n\t\t %.2f", weight);
}

BAIT, Page
 ADA [3150703]

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 9
AIM:Implementation of Graph and Searching (DFS and BFS).
1) Depth First
Search Code:

#include<stdio.h>
#include<conio.h
> #define MAX
20
#define TRUE 1
#define FALSE 0

int g[MAX][MAX];
int v[MAX];
int n;

void main()
{
int v1, v2;
char ans;
void
create();
void DFS(int);
clrscr();
create();
printf("The Adjacency Matrix For The Graph is\n");
for (v1 = 0; v1<n; v1++)
{
for(v2=0; v2<n; v2++)
{
printf("%d ", g[v1][v2]);
}
printf("\n");
}

BAIT, Page
 ADA [3150703]

getch();

BAIT, Page
 ADA [3150703]

do{
for(v1=0;v1<n; v1++)
v[v1] = FALSE;
printf("Enter the Vertex from yo want to traverse: ");
scanf("%d", &v1);
if(v1 >= MAX)
printf("Invaild Vertex\n");
else
{

printf("The Depth First Search of the Graph is \n");

DFS(v1);
}

printf("\n Do you want to traverse by any other node(y or n)? ");

ans = getch();
}while(ans == 'y');
}

void create()
{
int ch, v1, v2, flag;
char ans = 'y';
printf("\n\t\t This is Program to Create Graph");
printf("\n\t\t The Display is in Depth First Manner");
getch();
flushall();
for (v1=0; v1<n; v1++)
for(v2=0; v2<n; v2++)
g[v1][v2] = FALSE;
printf("\n Enter no. Nodes");
scanf("%d", &n);
printf("\n Enter the Vertices no. starting from 0");
do{
printf("\nEnter the vertices v1 and v2 ");
BAIT, Page
 ADA [3150703]

scanf("%d%d", &v1, &v2);

if(v1 >= n || v2>= n)
printf("Invalid Vertex Value\n");
else
{

g[v1][v2] = TRUE;
g[v2][v1] = TRUE;
}
printf("\n\n Add more edges(y or n)");
ans= getch();
}while(ans == 'y');
}

void DFS(int v1)

{
int v2;
printf("%d", v1);
v[v1] = TRUE;
for (v2 = 0; v2<MAX; v2++)
if(g[v1][v2] == TRUE && v[v2] == FALSE)
DFS(v2);
}

BAIT, Page
 ADA [3150703]

Output:

2) Breath First Search

Code:

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define size 20
#define TRUE 1
#define FALSE 0

int g[size][size];
int visit[size];

BAIT, Page
 ADA [3150703]

int Q[size];
int front,rear;
int n;

void main()
{
int v1,v2;
char ans= 'y';
void create(),bfs(int);
clrscr();
create();
printf("The adjacency for the graph is \n");
for(v1=1;v1<n;v1++)
{
for(v2=0;v2<n;v2++)
printf("%d ",g[v1][v2]);
printf("\n");
}
do
{
for(v1=0;v1<n;v1++)
visit[v1]=FALSE;

printf("Enter thye vertex from which you want to traverse:");

scanf("%d",&v1);
if(v1>=n)
printf("invalid vertex \n");
else
{

printf("The breadth First search of the graph is: \n");

bfs(v1);
}

printf("\n Do you want to traverse from any other node?");

ans=getche();
BAIT, Page
 ADA [3150703]

}while(ans=='y');
getch();

}
void create()
{
int v1,v2;
char ans='y';
printf("\n\t\t This is a program to create a graph:");
printf("\n\t\t The Display is in Breadth First manner:");
printf("\n Enter no.of nodes:");
scanf("%d",&n);
for(v1=0;v1<n;v1++)
for(v2=0;v2<n;v2++)
g[v1][v2]=FALSE;
printf("\n Enter the vertices no. staring from 0:");
do
{
printf("\n Enter the vertices v1&v2:");
scanf("%d%d",&v1,&v2); if(v1>=n||
v2>=n)
printf("invalid vertex value: \n");
else
{

g[v1][v2]=TRUE;
g[v2][v1]=TRUE;
}
printf("\n\n Add more edges??(Y/N):");
ans=getche();
}while(ans=='y');
}
void bfs(int v1)
{
int v2;

BAIT, Page
 ADA [3150703]

visit[v1]=TRUE;
front=rear=-1;
Q[++rear]=v1;
while(front!
=rear)
{
v1 = Q[++front];
printf("%d\n",v1);
for(v2=0;v2<n;v2++)
{
if(g[v1][v2]==TRUE && visit[v2]==FALSE)
{
Q[++rear]=v2;
visit[v2]=TRUE;

}
}
}

}
Output:

BAIT, Page
 ADA [3150703]

BAIT, Page
 ADA [3150703]

BAIT, Page
 ADA [3150703]

PRACTICAL – 10
AIM:Implement Prim’s algorithm.
Code:

#include<stdio.h>
#include<conio.h
> #define SIZE 20
#define INFINITY 999
void main()
{
int G[SIZE][SIZE], nodes;
int v1, v2, length, i, j, n;
void prims(int G[SIZE][SIZE], int nodes);
clrscr();
printf("\n\t Prim's Algorithm \n");
printf("\n Enter Number of Nodes in The Graph: ");
scanf("%d", &nodes);
printf("\n Enter Number of Edges in The Graph: ");
scanf("%d", &n);

for (i=0; i<nodes; i++)

for(j=0; j<nodes;j++)
G[i][j] = 0;
printf("\nEnter edge and weights \n");
for( i=0; i<n; i++)
{
printf("\n Enter Edge by V1 and V2 ");
printf("[Read the Graph from strating node 0]");
scanf ("%d %d", &v1, &v2);
printf("\n Enter corresponding weight: ");
scanf("%d", &length);
G[v1][v2] = G[v2][v1] = length;
}

BAIT, Page
 ADA [3150703]

getch(); printf("\
n\t"); prims(G,
nodes); getch();
}
void prims(int G[SIZE][SIZE], int nodes)
{
int tree[SIZE], i, j, k;
int min_disk, v1, v2, total = 0;
for (i=0; i<nodes; i++)
tree[i] = 0;
printf("\nThe Minimal Spaning Tree is: ");
tree[0] = 1;
for(k = 1; k<=nodes-1;k++)
{
min_disk = INFINITY;
for (i=0; i<=nodes-1; i++)
{
for(j=0; j<=nodes-1; j++)
{
if(G[i][j] && ((tree[i] && !tree[j]) || (!tree[i] &&
tree[j])))
{
if(G[i][j] <min_disk)
{
min_disk = G[i][j];
v1 = i;
v2 = j;
}
}
}
}
printf("\n Edge (%d %d) and Weight = %d", v1, v2, min_disk);
tree[v1] = tree[v2] = 1;

BAIT, Page
 ADA [3150703]

total = total + min_disk;

}
printf("\n\n\t Total Path length is = %d", total);
}

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 11
AIM:Implement Kruskal’s algorithm.
Code:

#include<stdio.h>
#include<conio.h>

#define INFINITY 999

typedef struct Graph

int v1;

int v2;

int cost;

}GR;

GR G[20];

int tot_edges, tot_nodes;

void create();

void spanning_tree();

int minimum(int);

void main()

clrscr();

printf("\n\t Graph Creation by adjecency Matrix \n");

create();

spanning_tree();

getch();

void create()

BAIT, Page
 ADA [3150703]

int k;

printf("\n Enter Total Number of nodes: ");

scanf("%d", &tot_nodes);

printf("\n Enter Total Number of edges: ");

scanf("%d", &tot_edges);

for(k=0; k<tot_edges; k++)

printf("\n Enter Edges in (V1 V2) from: ");

scanf("%d%d", &G[k].v1, &G[k].v2);

printf("\n Enter Corresponding Cost: ");

scanf("%d", &G[k].cost);

void spanning_tree()

int count, k, v1, v2, tree[10][10], pos, parent[10];

int sum, i, j;

int find(int v2, int parent[]);

void Union(int i, int j, int parent[]);

count = 0;

k = 0;

sum = 0;

for(i=0; i<tot_nodes; i++)

parent[i] = i;

BAIT, Page
 ADA [3150703]

while(count!=tot_nodes-1)

pos = minimum(tot_edges);

if (pos == -1)

break;

v1 = G[pos].v1;

v2 = G[pos].v2;

i = find(v1, parent);

j = find(v2, parent);

if (i!=j)

tree[k][0] = v1;

tree[k][1] = v2;

k++;

count++;

sum += G[pos].cost;

Union(i, j, parent);

G[pos].cost = INFINITY;

if(count == tot_nodes-1)

printf("\n Spanning Tree is.....");

for(i=0; i<tot_nodes-1; i++)

BAIT, Page
 ADA [3150703]

printf("[%d", tree[i][0]);

printf("-");

printf("%d", tree[i][1]);

printf("]");

printf("\n Cost of Spanning Tree is = %d", sum);

}else{

printf("There is No Spanning Tree");

int minimum(int n)

int i, small, pos;

small = INFINITY;

pos = -1;

for(i=0; i<n; i++)

if(G[i].cost< small)

small = G[i].cost;

pos = i;

return pos;

BAIT, Page
 ADA [3150703]

int find(int v2, int parent[])

while(parent[v2] != v2)

v2 = parent[v2];

return v2;

void Union(int i, int j, int parent[])

if(i<j)

parent[j] = i;

else

parent[i] = j;

BAIT, Page
 ADA [3150703]

Output:

BAIT, Page
 ADA [3150703]

PRACTICAL – 12
AIM:Implement LCS problem.
Code:

#include<stdio.h>
#include<conio.h>
#include<string.h>
#define SIZE 20
void compute_LCS(char A[SIZE], char B[SIZE]);

void main()
{
char A[SIZE],B[SIZE];
clrscr();
printf("\n Enter first sequence:");
scanf("%s",A);
printf("Enter second sequence:");
scanf("%s",B);
compute_LCS(A,B);
getch();
}
void compute_LCS(char A[],char B[])
{
int m,n,i,j;
int c[SIZE][SIZE];
char d[SIZE][SIZE];
void display(char[][SIZE],char[],int,int);
m = strlen(A);
n = strlen(B);

for(i=0;i<=m;i++)
c[i][0]=0;
for(i=0;i<=n;i++)

BAIT, Page
 ADA [3150703]

c[0][i]=0;

for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(A[i-1]==B[j-1])
{
c[i][j]=c[i-1][j-1]+1;
d[i][j]='\ ';
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
d[i][j] = '^';
}
else
{
c[i][j]=c[i][j-1];
d[i][j]='<-';
}
}
}
printf("\n Table is...\n");
for(i=0;i<=m;i++)
{
for(j=0; j<=n;j++)
{
printf("%3d",c[i][j]);
}
printf("\n");
}
printf("\n The longest common subsequence is...\n");
display(d,A,m,n);

BAIT, Page
 ADA [3150703]

}
void display(char d[][SIZE],char A[],int i,int j)
{
if(i==0||j==0)
return;
if(d[i][j]=='\ ')
{
display(d,A,i-1,j-1);
printf("%c",A[i-1]);
}
else if(d[i][j]=='^')
display(d,A,i-1,j);
else

display(d,A,i,j-1);
}

Output:

BAIT, Page