Design And Analysis Of Algorithm Project.docx

DESIGN AND ANALYSIS OF ALGORITHMS PROJECT

1

1. Implement a program in C to search an element from a sorted array using binary search

ALGORITHM Algorithm BinarySearch(a,n,x) { low = 1; high = n; while (low <= high) do { mid = [(low+high)/2]; if (x < a[mid]) then high = mid - 1; else if (x > a[mid]) then low = mid + 1; else return mid; } return 0; }

CODE #include <stdio.h> int main() { int c, first, last, middle, n, search, array[100]; printf("Enter number of elements\n"); scanf("%d",&n); printf("Enter %d integers\n", n); for (c = 0; c < n; c++) scanf("%d",&array[c]); printf("Enter value to find\n"); scanf("%d", &search); first = 0; last = n - 1; middle = (first+last)/2;

2

while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) { printf("%d found at location %d.\n", search, middle+1); break; } else last = middle - 1; middle = (first + last)/2; } if (first > last) printf("Not found! %d is not present in the list.\n", search); return 0; }

OUTPUT Enter number of elements 6 Enter 6 integers 12 19 5 33 2 24 Enter value to find 5 5 found at location 3.

3

2. Implement a program in C to sort an array using Quick Sort

ALGORITHM Algorithm Partition(left, right, pivot) { leftPointer = left; rightPointer = right – 1; while (True) do{ while A[++leftPointer] < pivot do ; while rightPointer > 0 && A[--rightPointer] > pivot do ; if (leftPointer >= rightPointer) break; else swap leftPointer,rightPointer; } swap leftPointer,right; return leftPointer; } Algorithm QuickSort(left, right) if (right-left <= 0) return; else { pivot = A[right]; partition = partitionFunc(left, right, pivot); quickSort(left,partition-1); quickSort(partition+1,right); } }

4

CODE #include<stdio.h> void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition (int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); int j; for (j = low; j <= high- 1; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1);

5

quickSort(arr, pi + 1, high); } } void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("n"); } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr, 0, n-1); printf("Sorted array: n"); printArray(arr, n); return 0; }

OUTPUT Sorted Array: n1 5 7 8 9 10 11n

3. Implement a program in C to sort an array using Merge Sort

ALGORITHM procedure mergesort(var a as array) if ( n == 1 ) return a var l1 as array = a[0] ... a[n/2] var l2 as array = a[n/2+1] ... a[n] l1 = mergesort( l1 )

6

l2 = mergesort( l2 ) return merge( l1, l2 ) end procedure procedure merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure

CODE #include<stdlib.h> #include<stdio.h> void merge(int arr[], int l, int m, int r) { int i, j, k;

7

int n1 = m - l + 1; int n2 =

r - m;

int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2)

8

{ arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l+(r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m+1, r);

merge(arr, l, m, r); } } void printArray(int A[], int size) { int i; for (i=0; i < size; i++) printf("%d ", A[i]); printf("\n"); } int main() { int arr[] = {8, 5, 1, 4, 7, 9}; int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is: \n"); printArray(arr, arr_size);

9

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is: \n"); printArray(arr, arr_size); return 0; }

OUTPUT Given array is: 8, 5, 1, 4, 7, 9 Sorted array is: 1, 4, 5, 7, 8, 9

4. Implement a program in C to find the maximum and minimum element from an array of integers using Divide and Conquer approach

ALGORITHM Algorithm MaxMinDC(x, y) if x – y ≤ 1 then return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) else (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) return (max(max1, max2), min(min1, min2))

CODE #include<stdio.h> #include<stdio.h> int max, min; int a[100];

10

void maxmin(int i, int j) { int max1, min1, mid; if(i==j) { max = min = a[i]; } else { if(i == j-1) { if(a[i] min1)

11

min = min1; } } } int main () { int i, num; printf ("\nEnter the total number of numbers : "); scanf ("%d",&num); printf ("Enter the numbers : \n"); for (i=1;i<=num;i++) scanf ("%d",&a[i]); max = a[0]; min = a[0]; maxmin(1, num); printf ("Minimum element in array : %d\n", min); printf ("Maximum element in array : %d\n", max); return 0; }

OUTPUT Enter the total number of numbers : 5 Enter the numbers : 24

20

33

15

36

Minimum element in array : 15 Maximum element in array : 36

5. Implement a program in C to sove Knapsack problem using Greedy Method

ALGORITHM Algorithm(Greedy-Fractional-Knapsack (w[1..n], p[1..n], W))

12

for i = 1 to n do x[i] = 0 weight = 0 for i = 1 to n if weight + w[i] ≤ W then x[i] = 1 weight = weight + w[i] else x[i] = (W - weight) / w[i] weight = W break return x

CODE # include<stdio.h> void knapsack(int n, float weight[], float profit[], float capacity) { float x[20], tp = 0; int i, j, u; u = capacity; for (i = 0; i < n; i++) x[i] = 0.0; for (i = 0; i < n; i++) { if (weight[i] > u) break; else { x[i] = 1.0; tp = tp + profit[i]; u = u - weight[i]; } } if (i < n)

13

x[i] = u / weight[i]; tp = tp + (x[i] * profit[i]); printf("\nThe result vector is: "); for (i = 0; i < n; i++) printf("%f\t", x[i]); printf("\nMaximum profit is: %f", tp); } int main() { float weight[20], profit[20], capacity; int num, i, j; float ratio[20], temp; printf("\nEnter the no. of objects: "); scanf("%d", &num); printf("\nEnter the weights and profits of each object: "); for (i = 0; i < num; i++) { scanf("%f %f", &weight[i], &profit[i]); } printf("\nEnter the capacity of knapsack: "); scanf("%f", &capacity); for (i = 0; i < num; i++) { ratio[i] = profit[i] / weight[i]; } for (i = 0; i < num; i++) { for (j = i + 1; j < num; j++) { if (ratio[i] < ratio[j]) { temp = ratio[j]; ratio[j] = ratio[i]; ratio[i] = temp; temp = weight[j]; weight[j] = weight[i]; weight[i] = temp;

14

temp = profit[j]; profit[j] = profit[i]; profit[i] = temp; } } } knapsack(num, weight, profit, capacity); return(0); }

OUTPUT Enter the no. of objects: 7 Enter the weights and profits of each object: 2 10 3 5 5 15 7 7 1 6 4 18 1 3 Enter the capacity of knapsack: 15 The result vector is: 1.000000

1.000000

0.666667

1.000000 0.000000

Maximum profit is: 55.333332

6. Implement a program in C to solve 0/1 Knapsack Problem

ALGORITHM Dynamic-0-1-Knapsack (v, w, n, W) { for w = 0 to W do

15

1.000000

1.000000

c[0, w] = 0 for i = 1 to n do c[i, 0] = 0 for w = 1 to W do if wi ≤ w then if vi + c[i-1, w-wi] then c[i, w] = vi + c[i-1, w-wi] else c[i, w] = c[i-1, w] else c[i, w] = c[i-1, w] }

CODE #include<stdio.h> int max(int a, int b) { return (a > b)? a : b; } int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[n+1][W+1]; for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], else K[i][w] = K[i-1][w]; } }

16

K[i-1][w]);

return K[n][W]; } int main() { int val[] = {60, 100, 120}; int wt[] = {10, 20, 30}; int

W = 50;

int n = sizeof(val)/sizeof(val[0]); printf("%d", knapSack(W, wt, val, n)); return 0; }

OUTPUT 220

7. Implement a program in C to solve the job sequencing with deadline problem using Greedy Method

ALGORITHM Algorithm JobSequencingWithDeadline (D, J, n, k) { D(0) := J(0) := 0 k := 1 J(1) := 1 for i = 2 … n do r := k while D(J(r)) > D(i) and D(J(r)) ≠ r do r := r – 1 if D(J(r)) ≤ D(i) and D(i) > r then for l = k … r + 1 by -1 do J(l + 1) := J(l)

17

J(r + 1) := i k := k + 1 }

CODE #include <stdio.h> #define MAX 100 struct Job { char id[5]; int deadline; int profit; }; void jobSequencingWithDeadline(Job jobs[], int n); int minValue(int x, int y) { if(x < y) return x; return y; } int main(void) { int i, j; Job jobs[5] = { {"j1", 2,

60},

{"j2", 1, 100}, {"j3", 3,

20},

{"j4", 2,

40},

{"j5", 1,

20},

}; Job temp; int n = 5; for(i = 1; i < n; i++) { for(j = 0; j < n - i; j++) { if(jobs[j+1].profit > jobs[j].profit) {

18

temp = jobs[j+1]; jobs[j+1] = jobs[j]; jobs[j] = temp; } } } printf("%10s %10s %10s\n", "Job", "Deadline", "Profit"); for(i = 0; i < n; i++) { printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit); } jobSequencingWithDeadline(jobs, n); return 0; } void jobSequencingWithDeadline(Job jobs[], int n) { int i, j, k, maxprofit; int timeslot[MAX]; int filledTimeSlot = 0; int dmax = 0; for(i = 0; i < n; i++) { if(jobs[i].deadline > dmax) { dmax = jobs[i].deadline; } } for(i = 1; i <= dmax; i++) { timeslot[i] = -1; } printf("dmax: %d\n", dmax); for(i = 1; i <= n; i++) { k = minValue(dmax, jobs[i - 1].deadline); while(k >= 1) { if(timeslot[k] == -1) {

19

timeslot[k] = i-1; filledTimeSlot++; break; } k--; } if(filledTimeSlot == dmax) { break; } } printf("\nRequired Jobs: "); for(i = 1; i <= dmax; i++) { printf("%s", jobs[timeslot[i]].id);

if(i < dmax) { printf(" --> "); } } maxprofit = 0; for(i = 1; i <= dmax; i++) { maxprofit += jobs[timeslot[i]].profit; } printf("\nMax Profit: %d\n", maxprofit); }

OUTPUT Following is maximum profit sequence of jobs c a e

8. Implement a program in C to find the solution of N-queens problem using backtracking 20

ALGORITHM Algorithm Place(k,i) { for j:=1 to k-1 do if ((x[j] = i) or (Abs(x[j] – i) = Abs (j-k))) then return false return true } Algorithm NQueens(k,n) { for i:=1 to n do { if Place(k,i) then { x[k] := I; if (k==n) then write x (x[1:n]); else NQueens(k+1,n); } } }

CODE #include<stdio.h> #include<math.h> int board[20],count; int main() { int n,i,j; void queen(int row,int n); printf("\nEnter number of Queens:");

21

scanf("%d",&n); queen(1,n); return 0; } void print(int n) { int i,j; printf("\n\nSolution %d:\n\n",++count); for(i=1;i<=n;++i) printf("\t%d",i); for(i=1;i<=n;++i) { printf("\n\n%d",i); for(j=1;j<=n;++j) { if(board[i]==j) printf("\tQ"); else printf("\t-"); } } } int place(int row,int column) { int i; for(i=1;i<=row-1;++i) { if(board[i]==column) return 0; else if(abs(board[i]-column)==abs(i-row))

22

return 0; } return 1; } void queen(int row,int n) { int column; for(column=1;column<=n;++column) { if(place(row,column)) { board[row]=column; if(row==n) print(n); else queen(row+1,n); } } }

OUTPUT Enter number of Queens: 4 Solution 1: 1

2

3

4

1

-

Q

-

-

2

-

-

-

Q

3

Q

-

-

-

4

-

-

Q

-

2

3

4

Solution 2: 1

23

1

-

-

Q

-

2

Q

-

-

-

3

-

-

-

Q

4

-

Q

-

-

9. Implement a program in C to find the solutions of m-colouring problem using backtracking

ALGORITHM Algorithm mColoring(k) { repeat { NextValue(k); if (x[k] = 0) then return; if (k = n) then write (x[1:n]); else mColoring(k+1); } until (false); } Algorithm NextValue(k) { repeat { x[k] = (x[k] + 1) mod (m+1); if (x[k] =0) then return; for j=1 to n do { if ((G(k,j) != 0) and (x[k] = x[j])) then break; } if (j=n+1) then return;

24

} until (false); }

CODE #include<stdio.h> #define V 4 void printSolution(int color[]); bool isSafe (int v, bool graph[V][V], int color[], int c) { for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true; } bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) { if (v == V) return true; for (int c = 1; c <= m; c++) { if (isSafe(v, graph, color, c)) { color[v] = c; if (graphColoringUtil (graph, m, color, v+1) == true) return true; color[v] = 0; } } return false; } bool graphColoring(bool graph[V][V], int m)

25

{ int *color = new int[V]; for (int i = 0; i < V; i++) color[i] = 0; if (graphColoringUtil(graph, m, color, 0) == false) { printf("Solution does not exist"); return false; } printSolution(color); return true; } void printSolution(int color[]) { printf("Solution Exists:" " Following are the assigned colors \n"); for (int i = 0; i < V; i++) printf(" %d ", color[i]); printf("\n"); } int main() { bool graph[V][V] = {{0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}, }; int m = 3; graphColoring (graph, m); return 0; }

26

OUTPUT Solution Exists: Following are the assigned colors 1

2

3

2

10. Implement a program in C to find the Hamiltonian Cycle from a graph using backtracking

ALGORITHM Algorithm Hamiltonian (k) { repeat { NextValue(k); if (x[k] = 0) then return; if (k = n) then write (x[1:n]); else Hamiltonian (k+1); } until (false); } Algorithm NextValue(k) { repeat { x[k] = (x[k] + 1) mod (n + 1); if (x[k] = 0) then return; if (G[x[k-1],x[k]] ≠ 0) then { for j=1 to k-1 do if (x[j] = x[k]) then break; if (j=k) then if ((k < n) or ((k=n) and G[x[n],x[1]] ≠ 0)) then return; }

27

} until (false); }

CODE #include<stdio.h> #define V 5 void printSolution(int path[]); bool isSafe(int v, bool graph[V][V], int path[], int pos) { if (graph [ path[pos-1] ][ v ] == 0) return false; for (int i = 0; i < pos; i++) if (path[i] == v) return false; return true; } bool hamCycleUtil(bool graph[V][V], int path[], int pos) { if (pos == V) { if ( graph[ path[pos-1] ][ path[0] ] == 1 ) return true; else return false; } for (int v = 1; v < V; v++) { if (isSafe(v, graph, path, pos)) { path[pos] = v; if (hamCycleUtil (graph, path, pos+1) == true)

28

return true;

path[pos] = -1; } } return false; } bool hamCycle(bool graph[V][V]) { int *path = new int[V]; for (int i = 0; i < V; i++) path[i] = -1; path[0] = 0; if ( hamCycleUtil(graph, path, 1) == false ) { printf("\nSolution does not exist"); return false; } printSolution(path); return true; } void printSolution(int path[]) { printf ("Solution Exists:" " Following is one Hamiltonian Cycle \n"); for (int i = 0; i < V; i++) printf(" %d ", path[i]); printf(" %d ", path[0]); printf("\n"); } int main()

29

{ bool graph1[V][V] = {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 1}, {0, 1, 1, 1, 0}, }; hamCycle(graph1); bool graph2[V][V] = {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 0}, {0, 1, 1, 0, 0}, }; hamCycle(graph2); return 0; }

OUTPUT Solution Exists: Following is one Hamiltonian Cycle 0

1

2

4

3

0

Solution does not exist

11. Implement a program in C to find the order of matrix chain multiplication with minimum cost using dynamic programming

ALGORITHM Algorithm MCM(C) { repeat for i=1 to n m[i][i] = 0;

30

x=2; repeat for i=1 to n-1 { j=x; repeat while (j ≤ n) m[i][j] = ∞ x= x + 1; } x = 2; repeat while (x ≤ n) { i = 1; j = x; repeat while (i ≤ n) { if (j ≤ n) { repeat for k = i to j-1 { m[i][j] = min(m[i][j],m[i][k] + m[k+1][j] + Pi-1PkPj); S[i][j]=k; } j=j+1; } Write Cost of multiplication = m[1][n]; } }

CODE #include<stdio.h> #include<stdlib.h>

31

int minimum_cost(int matrix[20], int t) { int x, small; if(t == 1) { return matrix[0]; } else { small = matrix[0]; for(x = 1; x < t; x++) { if(matrix[x] < small) { small = matrix[x]; } } return small; } } int main() { int t, i, l, j, k, limit; int matrix[30], multiplier[10][15], columns[15], rows[15], temp[15]; printf("\nEnter Total Number of Matrices:\t"); scanf("%d", &limit); for(i = 0; i < limit; i++) { printf("\nEnter Number of Columns of Matrix %d:\t", i + 1); scanf("%d", &columns[i]); printf("Enter Number of Rows of Matrix %d:\t", i + 1);

32

scanf("%d", &rows[i]); } for(i = 0; i < limit; i++) { temp[i] = columns[i]; } temp[i] = rows[i - 1]; printf("\n"); for(k = 1; k <= limit; k++) { for(j = k, i = 1; j <= limit; j++, i++) { multiplier[i][j] = 0; } } for(l = 2; l <= limit; l++) { for(j = l, i = 1; j <= limit; j++, i++) { t = 0; for(k = i; k < j; k++) { matrix[t++] = (multiplier[i][k] + multiplier[k + 1][j]) + (temp[i - 1] * temp[k] * temp[j]); } multiplier[i][j] = minimum_cost(matrix, t); } } printf("\nMinimum Scalar Multiplications:\t%d\n", multiplier[1][limit]); return 0; }

33

OUTPUT Enter Total Number of Matrices: 3 Enter Number of Columns of Matrix 1:

3

Enter Number of Rows of Matrix 1:

5

Enter Number of Columns of Matrix 2:

5

Enter Number of Rows of Matrix 2:

4

Enter Number of Columns of Matrix 3:

4

Enter Number of Rows of Matrix 3:

6

Minimum Scalar Multiplications: 132

12. Implement a program in C to find the minimum cost spanning tree using Prim’s algorithm

ALGORITHM 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Make a queue (Q) with all the vertices of G (V); For each member of Q set the priority to INFINITY; Only for the starting vertex (s) set the priority to 0; The parent of (s) should be NULL; While Q isn’t empty Get the minimum from Q – let’s say (u); (priority queue); For each adjacent vertex to (v) to (u) If (v) is in Q and weight of (u, v) < priority of (v) then The parent of (v) is set to be (u) The priority of (v) is the weight of (u, v)

CODE #include<stdio.h> #include<stdlib.h> #define infinity 9999 #define MAX 20 int G[MAX][MAX],spanning[MAX][MAX],n; int prims(); int main() { int i,j,total_cost; printf("Enter no. of vertices:"); scanf("%d",&n);

34

printf("\nEnter the adjacency matrix:\n"); for(i=0;i
35

for(i=1;i0) { min_distance=infinity; for(i=1;i
u=from[v]; spanning[u][v]=distance[v]; spanning[v][u]=distance[v]; no_of_edges--; visited[v]=1; for(i=1;i
36

return(min_cost); }

OUTPUT Enter no. of vertices: 3 Enter the adjacency matrix: 5

7

9

4

0

4

12

1

6

Total cost of spanning tree = 11

13. Implement a program in C to find minimum cost spanning tree using Kruskal’s algorithm

ALGORITHM 1. 2. 3. 4.

T (the final spanning tree) is defined to be the empty set; For each vertex v of G, make the empty set out of v; Sort the edges of G in ascending (non-decreasing) order; For each edge (u, v) from the sored list of step 3. If u and v belong to different sets Add (u,v) to T; Get together u and v in one single set; 5. Return T CODE #include<stdio.h> #define MAX 30 typedef struct edge { int u,v,w; }edge; typedef struct edgelist { edge data[MAX]; int n;

37

}edgelist; edgelist elist; int G[MAX][MAX],n; edgelist spanlist; void kruskal(); int find(int belongs[],int vertexno); void union1(int belongs[],int c1,int c2); void sort(); void print(); void main() { int i,j,total_cost; printf("\nEnter number of vertices:"); scanf("%d",&n); printf("\nEnter the adjacency matrix:\n"); for(i=0;i
for(i=1;i
38

elist.data[elist.n].u=i; elist.data[elist.n].v=j; elist.data[elist.n].w=G[i][j]; elist.n++; } } sort(); for(i=0;i
39

belongs[i]=c1; } void sort() { int i,j; edge temp; for(i=1;i<elist.n;i++) for(j=0;j<elist.n-1;j++) if(elist.data[j].w>elist.data[j+1].w) { temp=elist.data[j]; elist.data[j]=elist.data[j+1]; elist.data[j+1]=temp; } } void print() { int i,cost=0; for(i=0;i<spanlist.n;i++) { printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w); cost=cost+spanlist.data[i].w; } printf("\n\nCost of the spanning tree=%d",cost); }

OUTPUT Enter number of vertices: 4 Enter the adjacency matrix: 1001 1110

40

1010 1011 1

0

1

2

0

1

3

0

1

Cost of the spanning tree = 3

14. Implement a program in C to find the all pairs shortest path using Floyd’s Algorithm

ALGORITHM Algorithm Floyd(D, P) for k in 1 to n do for i in 1 to n do for j in 1 to n do if D[i][j] > D[i][k] + D[k][j] then D[i][j] = D[i][k] + D[k][j] P[i][j] = P[k][j] return P

CODE #include<stdio.h> #define V 4 #define INF 99999 void printSolution(int dist[][V]); void floydWarshall (int graph[][V]) { int dist[V][V], i, j, k; for (i = 0; i < V; i++) for (j = 0; j < V; j++) dist[i][j] = graph[i][j]; for (k = 0; k < V; k++)

41

{ for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } printSolution(dist); } void printSolution(int dist[][V]) { printf ("Following matrix shows the shortest distances" " between every pair of vertices \n"); for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][j] == INF) printf("%7s", "INF"); else printf ("%7d", dist[i][j]); } printf("\n"); } } int main() { int graph[V][V] = { {0,

5,

INF, 10},

42

{INF, 0,

3, INF},

{INF, INF, 0,

1},

{INF, INF, INF, 0} }; floydWarshall(graph); return 0; }

OUTPUT Following matrix shows the shortest distances between every pair of vertices 0

5

8

9

INF

0

3

4

INF

INF

0

1

INF

INF

INF

0

15. Implement a program in C to find the BFS traversal sequence from a given graph

ALGORITHM Algorithm BFT (G,n) { for i=1 to n do visited[i] = 0; for i=1 to n do if (visited[i] = 0) then BFS (i); }

CODE #include<stdio.h> int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1; void bfs(int v) { for(i = 1; i <= n; i++)

43

if(a[v][i] && !visited[i]) q[++r] = i; if(f <= r) { visited[q[f]] = 1; bfs(q[f++]); } } void main() { int v; printf("\n Enter the number of vertices:"); scanf("%d", &n); for(i=1; i <= n; i++) { q[i] = 0; visited[i] = 0; } printf("\n Enter graph data in matrix form:\n"); for(i=1; i<=n; i++) { for(j=1;j<=n;j++) { scanf("%d", &a[i][j]); } } printf("\n Enter the starting vertex:"); scanf("%d", &v); bfs(v); printf("\n The node which are reachable are:\n"); for(i=1; i <= n; i++) { if(visited[i]) printf("%d\t", i); else { printf("\n Bfs is not possible. Not all nodes are reachable"); break;

44

} } }

OUTPUT Enter the number of vertices: 3 Enter graph data in matrix form: 0

1

1

0

1

0

1

0

0

Enter the starting vertex: 1 The nodes which are reachable are: 1

2

3

16. Implement a program in C to find DFS traversal from a given graph

ALGORITHM Algorithm DFS(v) { visited [v] = 1; for each vertex w adjacent from v do { if (visited[w] = 0) then DFS (w); } }

CODE #include<stdio.h> #include int a[20][20],reach[20],n; void dfs(int v)

45

{ int i; reach[v]=1; for(i=1;i<=n;i++) if(a[v][i] && !reach[i]) { printf("\n %d->%d",v,i); dfs(i); } } void main() { int i,j,count=0; printf("\n Enter number of vertices:"); scanf("%d",&n); for(i=1;i<=n;i++) { reach[i]=0; for(j=1;j<=n;j++) a[i][j]=0; } printf("\n Enter the adjacency matrix:n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); dfs(1); printf("n"); for(i=1;i<=n;i++) { if(reach[i]) count++;

46

} if(count==n) printf("\n Graph is connected"); else printf("\n Graph is not connected"); }

OUTPUT Enter number of vertices: 3 Enter the adjacency matrix: 1

1

0

0

0

1

1

0

1

1->2 2->3 Graph is connected

17. Implement a program in C to solve 15-puzzle problem using Branch and Bound Technique

CODE #include<stdio.h> #include int m=0,n=4; int cal(int temp[10][10],int t[10][10]) { int i,j,m=0; for(i=0;i < n;i++) for(j=0;j < n;j++) { if(temp[i][j]!=t[i][j]) m++;

47

} return m; } int check(int a[10][10],int t[10][10]) { int i,j,f=1; for(i=0;i < n;i++) for(j=0;j < n;j++) if(a[i][j]!=t[i][j]) f=0; return f; } void main() { int p,i,j,n=4,a[10][10],t[10][10],temp[10][10],r[10][10]; int m=0,x=0,y=0,d=1000,dmin=0,l=0; printf("\nEnter the matrix to be solved,space with zero :\n"); for(i=0;i < n;i++) for(j=0;j < n;j++) scanf("%d",&a[i][j]); printf("\nEnter the target matrix,space with zero :\n"); for(i=0;i < n;i++) for(j=0;j < n;j++) scanf("%d",&t[i][j]); printf("\nEntered Matrix is :\n"); for(i=0;i < n;i++) { for(j=0;j < n;j++) printf("%d\t",a[i][j]); printf("\n"); }

48

printf("\nTarget Matrix is :\n"); for(i=0;i < n;i++) { for(j=0;j < n;j++) printf("%d\t",t[i][j]); printf("\n"); } while(!(check(a,t))) { l++; d=1000; for(i=0;i < n;i++) for(j=0;j < n;j++) { if(a[i][j]==0) { x=i; y=j; } } for(i=0;i < n;i++) for(j=0;j < n;j++) temp[i][j]=a[i][j]; if(x!=0) { p=temp[x][y]; temp[x][y]=temp[x-1][y]; temp[x-1][y]=p; } m=cal(temp,t); dmin=l+m;

49

if(dmin < d) { d=dmin; for(i=0;i < n;i++) for(j=0;j < n;j++) r[i][j]=temp[i][j]; } for(i=0;i < n;i++) for(j=0;j < n;j++) temp[i][j]=a[i][j]; if(x!=n-1) { p=temp[x][y]; temp[x][y]=temp[x+1][y]; temp[x+1][y]=p; } m=cal(temp,t); dmin=l+m; if(dmin < d) { d=dmin; for(i=0;i < n;i++) for(j=0;j < n;j++) r[i][j]=temp[i][j]; } for(i=0;i < n;i++) for(j=0;j < n;j++) temp[i][j]=a[i][j]; if(y!=n-1) { p=temp[x][y];

50

temp[x][y]=temp[x][y+1]; temp[x][y+1]=p; } m=cal(temp,t); dmin=l+m; if(dmin < d) { d=dmin; for(i=0;i < n;i++) for(j=0;j < n;j++) r[i][j]=temp[i][j]; } for(i=0;i < n;i++) for(j=0;j < n;j++) temp[i][j]=a[i][j]; if(y!=0) { p=temp[x][y]; temp[x][y]=temp[x][y-1]; temp[x][y-1]=p; } m=cal(temp,t); dmin=l+m; if(dmin < d) { d=dmin; for(i=0;i < n;i++) for(j=0;j < n;j++) r[i][j]=temp[i][j]; } printf("\nCalculated Intermediate Matrix Value :\n");

51

for(i=0;i < n;i++) { for(j=0;j < n;j++) printf("%d\t",r[i][j]); printf("\n"); } for(i=0;i < n;i++) for(j=0;j < n;j++) { a[i][j]=r[i][j]; temp[i][j]=0; } printf("Minimum cost : %d\n",d); } getch(); }

OUTPUT Enter the matrix to be solved,space with zero: 1

2

3

4

5

6

0

8

9

10

7

11

13 14

15

12

Enter the target matrix,space with zero : 1

2

3

4

5

6

7

8

9

10

11

12

13 14

15

0

Entered Matrix is : 1

2

3

4

5

6

0

8

52

9

10

7

11

13

14

15

12

Target Matrix is : 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

Calculated Intermediate Matrix Value : 1

2

3

4

5

6

7

8

9

10

0

11

13

14

15

12

Minimum cost : 4 Calculated Intermediate Matrix Value : 1

2

3

4

5

6

7

8

9

10

11

0

13

14

15

12

Minimum cost : 4 Calculated Intermediate Matrix Value : 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

Minimum cost : 3

53