LAB MANUAL

DAA Lab
BTCS-
2402(P)
B.Tech(CSE)

School of Computing Science & Engineering

Version1.1
 Table of
Contents

Write a program to sort given set of numbers in

ascending/descending order using Bubble sort and also search a

number using binary search. 2

2.Write a program to sort given set of numbers in

ascending/descending order using Insertion sort and also search

a number using linear search. 5

3.Write a program to sort given set of numbers in

ascending/descending order using Quick sort and any other

sorting algorithm. Also record the time taken by these two

programs and compare them. 7

4.Write a program to sort given set of numbers using Heap sort. 8

5.Write a program to sort given set of numbers Merge Sort. 14

6.Write a program to sort given set of numbers Counting Sort. 17

7.Write a program to implement Matrix Chain Multiplication. 13

8.Write a program to implement Knapsack using Greedy

technique. 15

9.Write a program to implement Knapsack using Dynamic

programming. 17

10.Write a program to implement Dijkstra’s Algorithm. 18

1
 11.Write a program to implement Bellman-Ford Algorithm. 20

12.Write a program to implement n-Queen Problem using

backtracking. 21

13.Write a program to implement Naive string matching

algorithm. 22

14.Write a program to implement String Matching using Rabin-

Karp algorithm. 24

Experiment No:1
Title
Write a program to sort given set of numbers in ascending/descending order using Bubble sort and
also search a number using binary search.
Objective 1.To study and Implement Bubble Sort Algorithm
2. To study and Implement Binary Search Algorithm
Pre- Knowledge of
requiesit
e  Array Data Structure

Algorith Bubble Sort Algorithm:

m

Input to the function is array A: The array to be sorted

procedure bubble Sort( A : list of sort able items )
repeat
swapped = false
for i = 1 to length(A) - 1 inclusive do:
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure

Binary Search Algorithm:

2
 Input to the algorithm is A: Array in which key is to searched, key: the key is to searched,
imin: lower index of array, imax: upper index of array.
int binary_search(int A[],int key,int imin,int imax)
{
// test if array is empty
if(imax < imin)
// set is empty, so return value showing not found
return KEY_NOT_FOUND;
else
{
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);

// three-way comparison
if(A[imid]> key)
// key is in lower subset
return binary_search(A, key, imin, imid-1);
elseif(A[imid]< key)
// key is in upper subset
return binary_search(A, key, imid+31, imax);
else
// key has been found
return imid;
}
}

Program 1.Bubble Sort

// C program for implementation of Bubble sort
#include <stdio.h>

void swap(int *xp, int *yp)

{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void bubbleSort(int arr[], int n)

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

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

if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

void printArray(int arr[], int size)

{
int i;

3
 for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

2. Binary Search
#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;

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 isn't present in the list.\n", search);

return 0;
}

4
Output 1. Bubble Sort

2. Binary Search

5
 Experiment No:2

Title
Write a program to sort given set of numbers in ascending/descending order using
Insertion sort and also search a number using linear search.
Objecti 1. .To study and Implement Insertion Sort Algorithm
ve
2. .To study and Implement Linear Search Algorithm

Pre- Knowledge of
requisi
te  Array Data Structure

Algorith Insertion Sort Algorithm:

m

Input to the function is array A: The array to be sorted

for i ← 1 to length(A)
x ← A[i]
j←i
while j > 0 and A[j-1] > x
A[j] ← A[j-1]
j←j-1
A[j] ← x

Linear Search Algorithm:

Input to the algorithm is A: Array in which key is to searched, x: the key is to

searched
LinearSearch(A, x)
Set i to n.
Repeat this loop:
If i< 0, then exit the loop.
If A[i] = x, then exit the loop.
Set i to i − 1.
Return i.
If returned value is –ve then it means item not found otherwise search successful at
location i.
Progra 1.Insertion Sort
m

6
// C program for insertion sort

#include <math.h>

#include <stdio.h>

void insertionSort(int arr[], int n)

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

// A utility function to print an array of size n

void printArray(int arr[], int n)

int i;

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

printf("%d ", arr[i]);

printf("\n");

int main()

int arr[] = { 12, 11, 13, 5, 6 };

7
 int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

2 Linear Search

#include<stdio.h>

void main ()

int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};

int item, i,flag;

printf("\nEnter Item which is to be searched\n");

scanf("%d",&item);

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

if(a[i] == item)

flag = i+1;

break;

else

flag = 0;

if(flag != 0)

printf("\nItem found at location %d\n",flag);

else

8
 {

printf("\nItem not found\n");

Output 1. Insertion sort

2. Linear Search

9
 Experiment No:3

Title
Write a program to sort given set of numbers in ascending/descending order using
Quick sort and any other sorting algorithm. Also record the time taken by these two
programs and compare them.
Objectiv To study and Implement Sort Algorithm
e

Pre- Knowledge of
requisit
e  Array Data Structure
 Divide and Conquer Technique
Algorith Quick Sort Algorithm:
m

Input to the function is array A: The array to be sorted

The following procedure implements quick sort.
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r)
3 QUICKSORT(A, p, q − 1)
4 QUICKSORT(A, q + 1, r)

To sort an entire array A, the initial call is QUICKSORT (A, 1, length[A]).

Partitioning the array
The key to the algorithm is the PARTITION procedure, which rearranges the subarray
A [p . . . r] in place.
PARTITION(A, p, r)
1 x ← A[r]
2i←p−1
3 for j ← p to r − 1
4 do if A[ j ] ≤ x
5 then i ←i + 1
6 exchange A[i ] ↔ A[ j ]
7 exchange A[i + 1] ↔ A[r]
8 return i + 1
Progra #include<stdio.h>
m
void quicksort(int number[25],int first,int last){

int i, j, pivot, temp;

if(first<last){

pivot=first;

i=first;

j=last;

10
while(i<j){

while(number[i]<=number[pivot]&&i<last)

i++;

while(number[j]>number[pivot])

j--;

if(i<j){

temp=number[i];

number[i]=number[j];

number[j]=temp;

temp=number[pivot];

number[pivot]=number[j];

number[j]=temp;

quicksort(number,first,j-1);

quicksort(number,j+1,last);

int main(){

int i, count, number[25];

printf("Enter some elements (Max. - 25): ");

scanf("%d",&count);

printf("Enter %d elements: ", count);

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

scanf("%d",&number[i]);

quicksort(number,0,count-1);

printf("The Sorted Order is: ");

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

printf(" %d",number[i]);

return 0;

11
Output

Experiment No: 4

Title
Write a program to sort given set of numbers using Heap sort.

Objective To study and Implement Heap Sort Algorithm.

Pre-requisite Knowledge of

 Array Data Structure

 Tree
Algorithm/Th The heap sort algorithm can be divided into two parts.
eory
In the first step, a heap is built out of the data.
In the second step, a sorted array is created by repeatedly removing the largest
element from the heap, and inserting it into the array. The heap is
reconstructed after each removal. Once all objects have been removed from the
heap, we have a sorted array. The direction of the sorted elements can be
varied by choosing a min-heap or max-heap in step one.
Input:- A is the array to be sorted
HEAPSORT(A)

1 BUILD-MAX-HEAP(A)
2 for i ← length[A] down to 2
3 do exchange A[1] ↔ A[i ]
4 heap-size[A] ← heap-size[A] − 1
5 MAX-HEAPIFY(A, 1)

12
 MAX-HEAPIFY are an important subroutine for manipulating max-heaps. Its
inputs are an array A and an index i into the array. When MAX-HEAPIFY is called,
it is assumed that the binary trees rooted at LEFT(i ) and RIGHT(i ) are max-
heaps, but that A[i ] may be smaller than its children, thus violating the max-
heap property. The function of MAX-HEAPIFY is to let the value at A[i ] “float
down” in the maxheap
So that the subtree rooted at index i become a max-heap.

MAX-HEAPIFY(A, i )
1 l ← LEFT(i )
2 r ← RIGHT(i )
3 if l ≤ heap-size[A] and A[l] > A[i ]
4 then largest ←l
5 else largest ←i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest ←r
8 if largest _= i
9 then exchange A[i ] ↔ A[largest]
10 MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP(A)
1 heap-size[A] ← length[A]
2 for i ← _length[A]/2down to 1
3 do MAX-HEAPIFY(A, i )
Program #include<stdio.h>
#include <conio.h>
void Adjust(int Heap_of_Numbers[],int i)
{
int j;
int copy;
int Number;
int Reference = 1;
Number=Heap_of_Numbers[0];
while(2*i<=Number && Reference==1)
{
j=2*i;
if(j+1<=Number && Heap_of_Numbers[j+1] > Heap_of_Numbers[j])
j=j+1;
if( Heap_of_Numbers[j] < Heap_of_Numbers[i])
Reference=0;
else
{
copy=Heap_of_Numbers[i];
Heap_of_Numbers[i]=Heap_of_Numbers[j];
Heap_of_Numbers[j]=copy;
i=j;
}
}
}
void Make_Heap(int heap[])
{
int i;

13
 int Number_of_Elements;
Number_of_Elements=heap[0];
for(i=Number_of_Elements/2;i>=1;i--)
Adjust(heap,i);
}
int main()
{
int heap[30];
int NumberofElements;
int i;
int LastElement;
int CopyVariable;
printf("Enter the number of elements present in the unsorted Array:");
scanf("%d",&NumberofElements);
printf("\nEnter the members of the array one by one:");
for(i=1;i<=NumberofElements;i++)
scanf("%d",&heap[i]);
heap[0]=NumberofElements;
Make_Heap(heap);
while(heap[0] > 1)
{
LastElement=heap[0];
CopyVariable=heap[1];
heap[1]=heap[LastElement];
heap[LastElement]=CopyVariable;
heap[0]--;
Adjust(heap,1);
}
printf("\nSorted Array:\n");
for(i=1;i<=NumberofElements;i++)
printf("%d ",heap[i]);
return 0;
}
Output

14
 Experiment No:5
Title
Write a program to sort given set of numbers Merge Sort.
Objectiv 1. .To study and Implement Merge Sort Algorithm
e
Pre- Knowledge of
requisit  Array Data Structure
e  Divide and Conquer Technique
Algorith Merge Sort Algorithm:
m

Input to the function is array A: The array to be sorted

MERGE-SORT(A, p, r)
1 if p < r
2 then q ← _(p + r)/2_
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)

MERGE(A, p, q, r)
1 n1 ← q − p + 1
15
 2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4 for i ← 1 to n1
5 do L[i ] ← A[p + i − 1]
6 for j ← 1 to n2
7 do R[ j ]← A[q + j ]
8 L[n1 + 1]←infinity
9 R[n2 + 1]←infinity
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i ] ≤ R[ j ]
14 then A[k] ← L[i ]
15 i ← i + 1
16 else A[k] ← R[ j ]
17 j ← j + 1
Progra /* C program for Merge Sort */
m
#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r)

{
int i, j, k;
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) {

16
 arr[k] = L[i];
i++;
k++;
}

while (j < n2) {

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[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

17
Output

Experiment No:6
Title
Write a program to sort given set of numbers Counting Sort.
Objective To study and Implement Counting Sort Algorithm
Pre- Knowledge of
requisite  Array Data Structure
Algorith Insertion Sort Algorithm:
m

Input to the function is array A: The array to be sorted

In the code for counting sort, we assume that the input is an array A [1 . . . n], and Thus length
[A] = n. We require two other arrays: the array B [1. . . n] holds the sorted output, and the array
C[0 . . k] provides temporary working storage.
COUNTING-SORT(A, B, k)
1 for i ← 0 to k
2 do C[i ] ← 0
3 for j ← 1 to length[A]
4 do C[A[ j ]] ← C[A[ j ]] + 1
18
 5 C[i] now contains the number of elements equal to i .
6 for i ← 1 to k
7 do C[i ] ← C[i ] + C[i − 1]
8 C[i] now contains the number of elements less than or equal to i .
9 for j ← length[A] down to 1
10 do B[C[A[ j ]]] ← A[ j ]
11 C[A[ j ]] ← C[A[ j ]] − 1
Program // C Program for counting sort
#include <stdio.h>
#include <string.h>
#define RANGE 255

void countSort(char arr[])

{
char output[strlen(arr)];
int count[RANGE + 1], i;
memset(count, 0, sizeof(count));
for (i = 0; arr[i]; ++i)
++count[arr[i]];

for (i = 1; i <= RANGE; ++i)

count[i] += count[i - 1];
for (i = 0; arr[i]; ++i) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}

for (i = 0; arr[i]; ++i)

arr[i] = output[i];
}

int main()
{
char arr[] = "Analysis and design of algorithm";
countSort(arr);
printf("\nSorted character array is %s", arr);
return 0;
}

19
Output

Experiment No:7
Title
Write a program to implement Matrix Chain Multiplication.
Objectiv To study and Implement Matrix chain multiplication problem.
e
Pre- Knowledge of
requisit  Dynamic Programming
e
Algorith Matrix-chain-multiplication Problem:-
m
The way we parenthesize a chain of matrices can have a dramatic impact on the cost
of evaluating the product. Consider first the cost of multiplying two matrices. The
standard algorithm is given by the following pseudocode. The attributes rows and
columns are the numbers of rows and columns in a matrix.

20
 MATRIX-MULTIPLY(A, B)
1 if columns[A] _= rows[B]
2 then error “incompatible dimensions”
3 else for i ← 1 to rows[A]
4 do for j ← 1 to columns[B]
5 do C[i, j ]← 0
6 for k ← 1 to columns[A]
7 do C[i, j ] ← C[i, j ] + A[i, k] · B[k, j ]
8 return C

We can multiply two matrices A and B only if they are compatible: the number of
columns of A must equal the number of rows of B. If A is a p ×q matrix and B is a q ×r
matrix, the resulting matrix C is a p ×r matrix. The time to compute C is dominated by
the number of scalar multiplications in line 7, which is pqr.

MATRIX-CHAIN-ORDER(p)
1 n ← length[p] − 1
2 for i ← 1 to n
3 do m[i, i ] ← 0
4 for l ← 2 to n \\ l is the chain length.
5 do for i ← 1 to n − l + 1
6 do j ←i + l − 1
7 m[i, j ]←infinity
8 for k ←i to j − 1
9 do q ← m[i, k] + m[k + 1, j ] + pi−1pk pj
10 if q < m[i, j ]
11 then m[i, j ]← q
12 s[i, j ] ← k
13 return m and s

The algorithm first computes m [i, i]← 0 for i = 1, 2. . . n (the minimum costs for chains
of length 1) in lines 2–3. During the first execution of the loop in lines 4–12. The
second time through the loop, it computes m [i, i +2] for i = 1, 2. . . n−2 (the minimum
costs for chains of length l = 3), and so forth. At each step, the m [i, j] cost computed
in lines 9–12 depends only on table entries m [i, k] and m [k + 1, j ] already computed.

Progra #include <stdio.h>

m
#include<limits.h>
#define INFY 999999999
long int m[20][20];
int s[20][20];
int p[20],i,j,n;
void print_optimal(int i,int j)
{

21
if (i == j)
printf(" A%d ",i);
else
{
printf("( ");
print_optimal(i, s[i][j]);
print_optimal(s[i][j] + 1, j);
printf(" )");
}
}
void matmultiply(void)
{
long int q;
int k;
for(i=n;i>0;i--)
{
for(j=i;j<=n;j++)
{
if(i==j)
m[i][j]=0;
else
{
for(k=i;k<j;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}}}
int MatrixChainOrder(int p[], int i, int j)
{
if(i == j)
return 0;
int k;
int min = INT_MAX;

22
 int count;
for (k = i; k <j; k++)
{
count = MatrixChainOrder(p, i, k) +
MatrixChainOrder(p, k+1, j) +
p[i-1]*p[k]*p[j];
if (count < min)
min = count;
}
return min;
}
void main()
{ int k;
printf("Enter the no. of elements: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
m[i][i]=0;
m[i][j]=INFY;
s[i][j]=0;
}
printf("\nEnter the dimensions: \n");
for(k=0;k<=n;k++)
{
printf("P%d: ",k);
scanf("%d",&p[k]);
}
matmultiply();
printf("\nCost Matrix M:\n");
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
printf("m[%d][%d]: %ld\n",i,j,m[i][j]);
i=1,j=n;
printf("\nMultiplication Sequence : ");
print_optimal(i,j);
printf("\nMinimum number of multiplications is : %d ",
MatrixChainOrder(p, 1, n));
}

23
Output

Experiment No:8
Title
Write a program to implement Knapsack using Greedy technique.
Objectiv To study and Implement Knapsack Algorithm.
e
Pre- Knowledge of
requisit  Array Data Structure
e  Greedy Programming
Algorith Knapsack Problem:
m
 Two main kinds of Knapsack Problems:
1. 0-1 Knapsack:
 N items (can be the same or different)
 Have only one of each
 Must leave or take (i.e. 0-1) each item (e.g. ingots of gold)
 DP works, greedy does not
2. Fractional Knapsack:
 N items (can be the same or different)
 Can take fractional part of each item (eg bags of gold dust)
 Greedy works and DP algorithms work
Fractional Knapsack: Greedy Solution
 Algorithm:
o Assume knapsack holds weight W and items have value vi and weight
wi
o Rank items by value/weight ratio: vi / wi
 Thus: vi / wi ≥ vj / wj, for all i ≤ j

24
 o Consider items in order of decreasing ratio
o Take as much of each item as possible
 Example: Knapsack Capacity W = 30 and
Item A B C D
Value 50 140 60 60
Size 5 20 10 12
Ratio 10 7 6 5
 Solution:
o All of A, all of B, and ((30-25)/10) of C (and none of D)
o Size: 5 + 20 + 10*(5/10) = 30
o Value: 50 + 140 + 60*(5/10) = 190 + 30 = 220

Progra #include<stdio.h>
m
int main()
{
float weight[50],profit[50],ratio[50],Totalvalue,temp,capacity,amount;
int n,i,j;
printf("Enter the number of items :");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter Weight and Profit for item[%d] :\n",i);
scanf("%f %f", &weight[i], &profit[i]);
}
printf("Enter the capacity of knapsack :\n");
scanf("%f",&capacity);

for(i=0;i<n;i++)
ratio[i]=profit[i]/weight[i];

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

for (j = i + 1; j < n; 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;

25
 temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}

printf("Knapsack problems using Greedy Algorithm:\n");

for (i = 0; i < n; i++)
{
if (weight[i] > capacity)
break;
else
{
Totalvalue = Totalvalue + profit[i];
capacity = capacity - weight[i];
}
}
if (i < n)
Totalvalue = Totalvalue + (ratio[i]*capacity);
printf("\nThe maximum value is :%f\n",Totalvalue);
return 0;
}

26
Output

Experiment No:9
Title
Write a program to implement Knapsack using Dynamic programming.
Objective .To study and Implement Knapsack Algorithm.
Pre- Knowledge of
requisite  Array Data Structure
 Dynamic Programming
Algorith Knapsack Problem:
m
 Two main kinds of Knapsack Problems:
1. 0-1 Knapsack:
 N items (can be the same or different)
 Have only one of each

27
  Must leave or take (i.e. 0-1) each item (e.g. ingots of gold)
 DP works, greedy does not
2. Fractional Knapsack:
 N items (can be the same or different)
 Can take fractional part of each item (eg bags of gold dust)
 Greedy works and DP algorithms work
0-1 Knapsack: Dynamic Solution
Here is a dynamic programming algorithm to solve the 0-1 Knapsack problem:

Input: S, a set of n items as described earlier, W the total weight of the knapsack.
(Assume that the weights and values are stored in separate arrays named w and v,
respectively.)

Output: The maximal value of items in a valid knapsack.

int w, k;
for (w=0; w <= W; w++)
B[w] = 0
for (k=0; k<n; k++) {
for (w = W; w>= w[k]; w--) {
if (B[w – w[k]] + v[k]> B[w])
B[w] = B[w – w[k]] + v[k]
}
}
Program #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]], K[i-1][w]);
else
K[i][w] = K[i-1][w];

28
 }
}

return K[n][W];
}

int main()
{
int i, n, val[20], wt[20], W;

printf("Enter number of items:");

scanf("%d", &n);

printf("Enter value and weight of items:\n");

for(i = 0;i < n; ++i){
scanf("%d%d", &val[i], &wt[i]);
}

printf("Enter size of knapsack:");

scanf("%d", &W);

printf("%d", knapSack(W, wt, val, n));

return 0;
}
Output

29
 Experiment No:10
Title
Write a program to implement Dijkstra’s Algorithm.
Objectiv To study and Implement Dijkstra’s Algorithm.
e
Pre- Knowledge of
requisit  Tree Data Structure
e  Graph
Algorith Dijkstra’s Algorithm:
m
Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted,
directed graph G = (V, E) for the case in which all edge weights are nonnegative.
Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights
from the source s have already been determined. The algorithm repeatedly selects
the vertex u € V − S with the minimum shortest-path estimate, adds u to S, and
relaxes all edges leaving u. In the following implementation, a min-priority queue Q
of vertices is used, keyed by their d values.
Inputs:
G- The Graph
w- weight matrix
s- source vertex

DIJKSTRA(G,w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← NULL
3 Q ← V[G]
4 while Q != NULL
5 do u ← EXTRACT-MIN(Q)
6 S ← S UNION {u}
7 for each vertex v € Adj[u]
8 do RELAX(u, v,w)

INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v €V[G]
2 do d[v]←∞
3 π[v]← NIL
4 d[s] ← 0

RELAX(u, v,w)
1 if d[v] > d[u] + w(u, v)

30
 2 then d[v] ← d[u] + w(u, v)
3 π[v]← u
Program #include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

int main()
{
int G[MAX][MAX],i,j,n,u;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);

printf("\nEnter the starting node:");

scanf("%d",&u);
dijkstra(G,n,u);

return 0;
}

void dijkstra(int G[MAX][MAX],int n,int startnode)

{

int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;

//pred[] stores the predecessor of each node

//count gives the number of nodes seen so far
//create the cost matrix
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
31
 else
cost[i][j]=G[i][j];

//initialize pred[],distance[] and visited[]

for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}

distance[startnode]=0;
visited[startnode]=1;
count=1;

while(count<n-1)
{
mindistance=INFINITY;

//nextnode gives the node at minimum distance

for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}

//check if a better path exists through nextnode

visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i])
{

distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
32
 //print the path and distance of each node
for(i=0;i<n;i++)
if(i!=startnode)
{
printf("\nDistance of node%d=%d",i,distance[i]);
printf("\nPath=%d",i);

j=i;
do
{
j=pred[j];
printf("<-%d",j);
}while(j!=startnode);
}
}
Output

33
 Experiment No:11
Title
Write a program to implement Bellman-Ford Algorithm.
Objectiv To study and Implement Dijkstra’s Algorithm.
e
Pre- Knowledge of
requisit  Tree Data Structure
e  Graph
Algorith Bellman-Ford Algorithm:
m
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the
general case in which edge weights may be negative. Given a weighted, directed
graph G = (V, E) with source s and weight function w : E → R, the Bellman-Ford
algorithm returns a Boolean value indicating whether or not there is a negative-
weight cycle that is reachable from the source. If there is such a cycle, the algorithm
indicates that no solution exists. If there is no such cycle, the algorithm produces the
shortest paths and their weights. The algorithm uses relaxation, progressively
decreasing an estimate d[v] on the weight of a shortest path from the source s to
each vertex v € V until it achieves the actual shortest-path weight δ(s, v). The
algorithm returns TRUE if and only if the graph contains no negative-weight cycles
that are reachable from the source.
BELLMAN-FORD(G,w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i ← 1 to |V[G]| − 1
3 do for each edge (u, v) € E[G]
4 do RELAX(u, v,w)
5 for each edge (u, v) € E[G]
6 do if d[v] > d[u] + w(u, v)
7 then return FALSE
8 return TRUE

INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v € V[G]
2 do d[v]←∞
3 π[v]← NIL
4 d[s] ← 0

RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u] + w(u, v)
3 π[v]← u
Progra #include <stdio.h>
m
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct Edge
{
int source, destination, weight;
};

34
struct Graph
{
int V, E;
struct Edge* edge;

};
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
return graph;
}
void FinalSolution(int dist[], int n)
{
printf("\nVertex\tDistance from Source Vertex\n");
int i;
for (i = 0; i < n; ++i){
printf("%d \t\t %d\n", i, dist[i]);
}
}

void BellmanFord(struct Graph* graph, int source)

{
int V = graph->V;
int E = graph->E;
int StoreDistance[V];
int i,j;
for (i = 0; i < V; i++)
StoreDistance[i] = INT_MAX;
StoreDistance[source] = 0;
for (i = 1; i <= V-1; i++)
{
for (j = 0; j < E; j++)
{
int u = graph->edge[j].source;
int v = graph->edge[j].destination;
int weight = graph->edge[j].weight;

35
if (StoreDistance[u] + weight < StoreDistance[v])
StoreDistance[v] = StoreDistance[u] + weight;
}
}
for (i = 0; i < E; i++)
{
int u = graph->edge[i].source;
int v = graph->edge[i].destination;
int weight = graph->edge[i].weight;
if (StoreDistance[u] + weight < StoreDistance[v])
printf("This graph contains negative edge cycle\n");
}
FinalSolution(StoreDistance, V);
return;
}
int main()
{
int V,E,S; //V = no.of Vertices, E = no.of Edges, S is source vertex
printf("Enter number of vertices in graph\n");
scanf("%d",&V);
printf("Enter number of edges in graph\n");
scanf("%d",&E);
printf("Enter your source vertex number\n");
scanf("%d",&S);
struct Graph* graph = createGraph(V, E);
int i;
for(i=0;i<E;i++){
printf("\nEnter edge %d properties Source, destination, weight
respectively\n",i+1);
scanf("%d",&graph->edge[i].source);
scanf("%d",&graph->edge[i].destination);
scanf("%d",&graph->edge[i].weight);
}
BellmanFord(graph, S);
return 0;
}

36
Output

37
38