DESIGN AND ANALYSIS OF ALGORITHM

LAB FILE (BCS553)

DEPARTMENT OF COMPUTER SCIENCE AND
ENGINEERING – ARTIFICIAL INTELLIGENCE

ACADEMIC SESSION 2025-26

COURSE: [Link] (CSE-AI)

SEMESTER: 5th

Paramjeet Singh Ms. Salma Khatoon

2301921520127
CSAI3

–
 DEPARTMENT OF COMPUTER SCIENCE AND
ENGINEERING – ARTIFICIAL INTELLIGENCE

PRACTICAL DAA Lab [BCS 553]

LIST

SESSION: 2025-26 SEMESTER-ODD

FACULTY NAME:

[Link] PRACTICAL LIST

1 Program for Recursive Binary & Linear Search.

2 Program for Heap Sort.

3 Program for Merge Sort.
4 Program for Selection Sort.
5 Program for Insertion Sort.
6 Program for Quick Sort.
7 Knapsack Problem using Greedy Solution

8 Perform Travelling Salesman Problem

9 Find Minimum Spanning Tree using Kruskal’s Algorithm

10 Implement N Queen Problem using Backtracking

11 Sort a given set of n integer elements using Quick Sort method and compute its time
complexity. Run the program for varied values of n> 5000 and record the time taken
to sort. Plot a graph of the time taken versus non graph sheet. The elements can be
read from a file or can be generated using the random number generator.
Demonstrate using Java how the divide and- conquer method works along with its
time complexity analysis: worst case, average case and best case.
12 Sort a given set of n integer elements using Merge Sort method and compute its time
complexity. Run the program for varied values of n> 5000, and record the time taken
to sort. Plot a graph of the time taken versus non graph sheet. The elements can be
read from a file or can be generated using the random number generator.
Demonstrate how the divide and- conquer method works along with its time
complexity analysis: worst case, average case and best case.
13 Implement the 0/1 Knapsack problem using
(a) Dynamic Programming method (b) Greedy method

2
 1. RECURSIVE BINARY & LINEAR SEARCH
A linear search scans one item at a time, without jumping to any item.
 The worst-case complexity is O(n), sometimes known an O(n) search
 Time taken to search elements keep increasing as the number of elements are increased.

A binary search however, cut down your search to half as soon as you find middle of a sorted
list.
 The middle element is looked to check if it is greater than or less than the value to be
searched.
 Accordingly, search is done to either half of the given list

Important Differences
 Input data needs to be sorted in Binary Search and not in Linear Search
 Linear search does the sequential access whereas Binary search access data randomly.
 Time complexity of linear search is O(n) & Binary search has time complexity O(log n).
 Linear search performs equality comparisons and Binary search performs ordering
comparisons

ALGORITHM

Linear Search (Array A, Value x)

1. Set i to 1
2. if i > n then go to step 7
3. if A[i] = x then go to step 6
4. Set i to i + 1
5. Go to Step 2
6. Print Element x Found at index i and go to step 8
7. Print element not found
8. Exit

Binary Search (Array A, Value x)

1. Start with the middle element:
a. If the target value is equal to the middle element of the array, then return the
index of the middle element.
b. If not, then compare the middle element with the target value,
i. If the target value is greater than the number in the middle index, then pick
the elements to the right of the middle index and start with Step 1.
ii. If the target value is less than the number in the middle index, then pick
the elements to the left of the middle index and start with Step 1.
2. When a match is found, return the index of the element matched.
3. If no match is found, then return -1

4
PSEUDO-CODE

procedure linear_search (list,

value) for each item in the list
if match item == value
return the item's
location
end if
end for

end procedure

Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched

Set lowerBound =
1 Set upperBound
=n

while x not found

if upperBound < lowerBound
EXIT: x does not exist.

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] = x
EXIT: x found at location midPoint
end while

end procedure

PROGRAM

#include <stdio.h>
#define MAX_LEN 10
void l_search_recursive(int l[],int num,int ele);
void b_search_recursive(int l[],int num,int ele);
void read_list(int l[],int num);
void print_list(int l[],int num);

void main ( )
{
int l[MAX_LEN], num, ele;
int ch;

clrscr();

printf("======================================================");
printf("\n\t\t\tMENU");
printf("\n=====================================================");
printf("\n[1] Linary Search");
printf("\n[2] Binary Search");
printf("\n\nEnter your
Choice:"); scanf("%d",&ch);

if(ch<=2 & ch>0)

{
printf("Enter the number of elements
:"); scanf("%d",&num);
read_list(l,num);
printf("\nElements present in the list are:\n\n");
print_list(l,num);
printf("\n\nElement you want to search:\n\n");
scanf("%d",&ele);

switch(ch)
{
case 1:printf("\n**Linear Search**\n");
l_search_recursive(l,num,ele);
getch();
break;

case 2:printf("\n**Binary Search**\n");

b_search_recursive(l,num,ele);
getch();
break;
}
}
getch();
}
/*end main*/

/* Recursive Linear Search Method*/

void l_search_recursive(int l[],int num,int ele)
{
int f = 0;

if( l[num] == ele)

{
printf("\nThe element %d is present at position %d in list\
n",ele,num); f=1;
}
else
{
if((num==0) && (f==0))
{
printf("The element %d is not found.",ele);
}
else
{
l_search(l,num-1,ele);
}
}
getch();
}

/* Recursive Binary Search Method*/

int b_search_recursive(int l[],int arrayStart,int arrayEnd,int a)
{
int m,pos;
if (arrayStart<=arrayEnd)
{
m=(arrayStart+arrayEnd)/2;
if (l[m]==a)
 return m;
else if (a<l[m])
return b_search_recursive(l,arrayStart,m-1,a);
else
return b_search_recursive(l,m+1,arrayEnd,a);
}
return -1;
}
 2. HEAPSORT
Combines the better attributes of merge sort and insertion sort.
Like merge sort, but unlike insertion sort, running time is O(n lg
n). Like insertion sort, but unlike merge sort, sorts in place.
Introduces an algorithm design technique
Create data structure (heap) to manage information during the execution of an
algorithm. The heap has other applications beside sorting- Priority Queues.

Heap Procedures for Sorting

 MaxHeapify O(lg n)
 BuildMaxHeap O(n)
 HeapSort O(n lg n)

Example

ALGORITHM

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item
of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
 3. Repeat above steps while size of heap is greater than 1.

PSEUDO-CODE

MaxHeapify(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. MaxHeapify(A, largest)

BuildMaxHeap(A)
1. heap-size[A]  length[A]
2. for i  length[A]/2 downto 1
3. do MaxHeapify(A, i)

HeapSort(A)
1. Build-Max-Heap(A)
2. for i  length[A] downto 2
3. do exchange A[1]  A[i]
4. heap-size[A]  heap-size[A] – 1
5. MaxHeapify(A, 1)

PROGRAM

#include<stdio.h>
#include<conio.h>
void max_heapify(int *,int);
void build_max_heap(int*,int);
 void heapsort(int *,int);
void swap(int,int);
int heapsize;
int main()
{
int *arr,n,i;
printf("Enter no. of elements = ");
scanf("%d",&n);
arr=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
{
printf("Enter array elements =
"); scanf("%d",&arr[i]);
}
//heapsize = n;
heapsort(arr,n); printf("\
nAfter heapsort \n");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
void heapsort(int *arr,int len)
{
int i;
build_max_heap(arr,len);
for(i= len-1;i>=1;i--)
{
swap(&arr[0],&arr[i]);
heapsize = heapsize -1;
max_heapify(arr,0);
}
}
void max_heapify(int *arr,int i)
{
int l=2*i,r=2*i+1,largest;
if(l<heapsize &&
arr[l]>arr[i])
largest = l;
 else
largest = i;
if(r<heapsize &&
arr[r]>arr[largest]) largest = r;

if(largest != i)
{
swap(&arr[i],&arr[largest]);
max_heapify(arr,largest);
}
}
void build_max_heap(int *arr,int len)
{
heapsize =
len; int i;
for(i =len/2;i>=0;i--)
{
max_heapify(arr,i);
}
}
void swap(int *a ,int *b)
{
int temp = *a;
*a= *b;
*b= temp;
}
 3. MERGE SORT

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element
is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1
sublist remaining. This will be the sorted list.

Example:

ALGORITHM:

If it is only one element in the list it is already sorted, return.

Divide the list recursively into two halves until it can no more be
divided. Merge the smaller lists into new list in sorted order.

PSEUDO-CODE

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
) 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

PROGRAM

#include <iostream>
using namespace
std; #include
<conio.h>
void merge(int *,int, int , int );
void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
void merge(int *a, int low, int high, int mid)
{
int i, j, k,
c[50]; i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[i];
k++;
i++;
}
while (j <= high)
{ c[k] = a[j];
 k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}

int main()
{
int a[20], i, b[20];
cout<<"enter the elements\
n"; for (i = 0; i < 5; i++)
{
cin>>a[i];
}
mergesort(a, 0, 4);
cout<<"sorted array\n";
for (i = 0; i < 5; i++)
{
cout<<a[i];
}
cout<<"enter the elements\
n"; for (i = 0; i < 5; i++)
{
cin>>b[i];
}
mergesort(b, 0, 4);
cout<<"sorted array\n";
for (i = 0; i < 5; i++)
{
cout<<b[i];
}
getch();
}
 4. SELECTION SORT
The selection sort algorithm sorts an array by repeatedly finding the minimum element
considering ascending order) from unsorted part and putting it at the beginning. The algorithm
maintains two subarrays in a given array.
1. The subarray which is already sorted.
2. Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from
the unsorted subarray is picked and moved to the sorted subarray.
Time Complexity: O(n2) as there are two nested loops.

Example:

ALGORITHM

1. Set MIN to location 0

2. Search the minimum element in the list
3. Swap with value at location MIN
4. Increment MIN to point to next element
5. Repeat until list is sorted

PSEUDO-CODE

procedure selection
sort list : array of
items n : size of list
 for i = 1 to n - 1
/* set current element as minimum*/
min = i

/* check the element to be minimum

*/ for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for

/* swap the minimum element with the current

element*/ if indexMin != i then
swap list[min] and
list[i] end if
end for

end procedure

PROGRAM

#include <stdio.h>

void swap(int *xp, int *yp)

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

void selectionSort(int arr[], int n)

{
int i, j, min_idx;

// One by one move boundary of unsorted

subarray for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
 min_idx = j;

// Swap the found minimum element with the first

element swap(&arr[min_idx], &arr[i]);
}
}

/* Function to print an array */

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

// Driver program to test above

functions int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n =
sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
 5. INSERTION SORT

Insertion sort algorithm removes an element from the sorting list, and placing it into the
correct position in the already sorted part of the list, until no input elements left. The insertion
sort algorithm complexity depends on the input list. If the list is already sorted we have best
case,which has linear complexity O(n). If the list is reversed then we have worst case, quadratic
running time O(n^2). And the average case is also quadratic running time O(n^2), which make
the insertion sort not practical algorithm of choice for large n( where n is number of element in
the data structure), however insertion sort is one of the fastest algorithms for sorting very small
arrays.

Insertion Sorting Algorithm Complexity

1. Worst case performance O(n^2)
2. Best case performance O(n)
3. Average case performance O(n^2)

Example: Consider unsorted array

A[]=[7,4,5,2].

ALGORITHM

1. If it is the first element, it is already sorted. return 1;

2. Pick next element
3. Compare with all elements in the sorted sub-list
 4. Shift all the elements in the sorted sub-list that is greater than the value to be sorted
5. Insert the value
6. Repeat until list is sorted

PSEUDO-CODE

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

PROGRAM:

#include <cstdlib>
#include <iostream>

using namespace std;

//member function
void insertion_sort(int arr[], int
length); void print_array(int array[],int
size);

int main()
{
int array[5]=
{5,4,3,2,1};
insertion_sort(array,5);
return 0;
}//end of main

void insertion_sort(int arr[], int length)

{
int i, j ,tmp;
for (i = 1; i < length; i++){

j = i;
while (j > 0 && arr[j - 1] > arr[j]) {
 tmp = arr[j];
arr[j] = arr[j -
1]; arr[j - 1] =
tmp;
j--;
}//end of while loop
print_array(arr,5);
}//end of for loop
}//end of insertion_sort.

void print_array(int array[], int size)

{ cout<< "sorting: ";

int j;
for (j=0; j<size;j++)
for (j=0; j<size;j++)
cout <<" "<<
array[j]; cout <<
endl;
}//end of print_array
 6. QUICK SORT
Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two
smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively
sort the sub-arrays.
The steps are:

1. Pick an element, called a pivot, from the array.

2. Partitioning: reorder the array so that all elements with values less than the pivot come
before the pivot, while all elements with values greater than the pivot come after it
(equal values can go either way). After this partitioning, the pivot is in its final position.
This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values
and separately to the sub-array of elements with greater values.

Example:
The shaded element is the pivot. It is always chosen as the last element of the partition. However,
always choosing the last element in the partition as the pivot in this way results in
poorperformance (O(n²)) on already sorted arrays, or arrays of identical elements. Since sub-
arrays ofsorted / identical elements crop up a lot towards the end of a sorting procedure on a
large set, versions of the quicksort algorithm which choose the pivot as the middle element run
much morequickly than the algorithm described in this diagram on large sets of numbers.

ALGORITHM

a) Quick Sort Pivot Algorithm

1. Choose the highest index value has pivot
2. Take two variables to point left and right of the list excluding pivot
3. left points to the low index
4. right points to the high
5. while value at left is less than pivot move right
6. while value at right is greater than pivot move left
7. if both step 5 and step 6 does not match swap left and right
8. if left ≥ right, the point where they met is new pivot

b) Quick Sort Algorithm

1. Make the right-most index value pivot
2. partition the array using pivot value
3. quicksort left partition recursively
4. quicksort right partition recursively

PSEUDO-CODE

a) Quick Sort Pivot Pseudo-code

function partitionFunc(left, right,

pivot) leftPointer = left
rightPointer = right - 1

while True do
while A[++leftPointer] < pivot do
//do-nothing
end while

while rightPointer > 0 && A[--rightPointer] > pivot do

//do-nothing
end while
 if leftPointer >=
rightPointer break
else
swap leftPointer,rightPointer
end if

end while

swap leftPointer,right
return leftPointer

end function

b) Quick Sort Pseudo-code

procedure 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)
end if

end procedure

PROGRAM

#include <iostream>
#include <vector>
using namespace
std;

/**
* Partition the elements of A, such that you first have elements smaller than
* "who", followed by eleemnts larger than "who". Return the last poistion of an
* element smaller or equal to "who".
*/
int partition(vector<int>& A, int left, int right, int who) {

for (int i=left; i<right; ++i) {

 if (A[i] <= who) {
swap(A[i], A[left]);
left ++;
}
}
return left - 1;
}

/**
* Quick sort vector A, between index "left" and index "right".
*/
void qsort(vector<int>& A, int left, int right)
{ if (left >= right) return;

int middle = left + (right - left) / 2;

swap(A[middle], A[left]);
int midpoint = partition(A, left + 1, right, A[left]);
swap(A[left], A[midpoint]);
qsort(A, left, midpoint);
qsort(A, midpoint + 1,
right);
}

void printVector(vector<int>& A)
{ for (int i=0; i<[Link](); ++i) {
cout << A[i] << " ";
}
cout << endl;
}

void testPartition() {
int elements[] = {1, 3, 1, 1, 3};
vector<int> A(elements, elements +
5); int n = partition(A, 0, 5, 1);
cout << n <<
endl;
printVector(A);
}
void testSort() {
int elements[] = {1, 12, 2, 2, 2, 6, 20, 22};
 vector<int> A(elements, elements +
8); qsort(A, 0, [Link]());
printVector(A);
}

int main ()
{
testPartition();
cout << "--------------" << endl;
testSort();
return 0;
}
 7. KNAPSACK PROBLEM USING GREEDY SOLUTION
Given a set of items, each with a weight and a value, determine a subset of items to include in a
collection so that the total weight is less than or equal to a given limit and the total value is as
large as possible.

The knapsack problem is in combinatorial optimization problem. It appears as a sub-problem in

many, more complex mathematical models of real-world problems. One general approach to
difficult problems is to identify the most restrictive constraint, ignore the others, solve a
knapsack problem, and somehow adjust the solution to satisfy the ignored constraints.

Applications: In many cases of resource allocation along with some constraint, the problem can
be derived in a similar way of Knapsack problem. Following is a set of example.

 Finding the least wasteful way to cut raw materials

 Portfolio optimization
 Cutting stock problems

Problem Scenario

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n
items available in the store and weight of ith item is w i and its profit is pi. What items should the
thief take?

In this context, the items should be selected in such a way that the thief will carry those items for
which he will gain maximum profit. Hence, the objective of the thief is to maximize the profit.

In the case of fractional knapsack, items can be broken into smaller pieces, hence the thief can
select fractions of items. According to the problem statement,

There are n items in the store

 Weight of ith item wi>0

 Profit for ith item pi>0 and
 Capacity of the Knapsack is W

In this fractional Knapsack problem, items can be broken into smaller pieces. So, the thief may
take only a fraction xi of ith item.

0⩽xi⩽1
The ith item contributes the weight [Link] to the total weight in the knapsack and profit [Link] to
the total profit.

Hence, the objective of this algorithm is to

subject to constraint,

It is clear that an optimal solution must fill the knapsack exactly, otherwise we could add a
fraction of one of the remaining items and increase the overall profit. Thus, an optimal solution
can be obtained by

In this context, first we need to sort those items according to the value of pi/wi, so that
(pi+1)/(wi+1)
≤ pi/wi . Here, x is an array to store the fraction of items.

ALGORITHM

 Assume knapsack holds weight W and items have value pi and weight wi
 Rank items by value/weight ratio: pi / wi
 Thus: pi / wi ≥ pj / wj, for all i ≤ j
 Consider items in order of decreasing ratio
 Take as much of each item as possible

PSEUDO-CODE

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

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

PROGRAM

# 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)
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 wts and profits of each object:-

"); for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i], &profit[i]);
}

printf("\nEnter the capacityacity 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;

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

knapsack(num, weight, profit,

capacity); return(0);
}
 8. TRAVELLING SALESMAN PROBLEM
A traveler needs to visit all the cities from a list, where distances between all the cities are known
and each city should be visited just once. The traveler seeks for the shortest possible route such
that he visits each city exactly once and returns to the origin city.

Travelling salesman problem is the most notorious computational problem. We can use brute-
force approach to evaluate every possible tour and select the best one. For n number of vertices
in a graph, there are (n - 1)! number of possibilities. Instead of brute-force using dynamic
programming approach, the solution can be obtained in lesser time, though there is no
polynomial time algorithm.

Let us consider a graph G = (V, E), where V is a set of cities and E is a set of weighted edges. An
edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is
d(u, v), which should be non-negative.

Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this
is a partial tour. We certainly need to know j, since this will determine which cities are most
convenient to visit next. We also need to know all the cities visited so far, so that we don't repeat
any of them. Hence, this is an appropriate sub-problem.

For a subset of cities S Є {1, 2, 3, ... , n} that includes 1, and j Є S, let C(S, j) be the length of the
shortest path visiting each node in S exactly once, starting at 1 and ending at j.

When |S| > 1, we define C(S, 1) = 𝖺 since the path cannot start and end at 1.

Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We
should select the next city in such a way that

C(S,j) = min C(S−{j},i) + d(i,j) where i∈S and i≠jc(S,j)

= min C(s−{j},i) + d(i,j) where i∈S and i≠j

There are at the most 2n.n sub-problems and each one takes linear time to solve. Therefore, the
total running time is O(2 n.n2).

ALGORITHM

1. Consider city 1 as the starting and ending point. Since route is cyclic, we can
consider any point as starting point.
2. Generate all (n-1)! permutations of cities.
3. Calculate cost of every permutation and keep track of minimum cost permutation.
4. Return the permutation with minimum cost.
PSEUDO-CODE

C ({1}, 1) = 0
for s = 2 to n do
for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
C (S, 1) = ∞
for all j Є S and j ≠ 1
C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

PROGRAM

#include<stdio.h>

int ary[10][10],completed[10],n,cost=0;

void takeInput()
{
int i,j;

printf("Enter the number of villages:

"); scanf("%d",&n);

printf("\nEnter the Cost Matrix\

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

{
printf("\nEnter Elements of Row: %d\n",i+1);

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

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

completed[i]=0;
}

printf("\n\nThe cost list is:");

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

{
printf("\n");

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

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

void mincost(int city)

{
int i,ncity;

completed[city]=1;

printf("%d--->",city+1);
ncity=least(city);

if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=ary[city][ncity];

return;
}

mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;

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

{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i]; kmin=ary[c]
[i];
nc=i;
}
}

if(min!=999)
cost+=kmin;

return nc;
}
int main()
{
takeInput();

printf("\n\nThe Path is:\n");

mincost(0); //passing 0 because starting

vertex printf("\n\nMinimum cost is %d\n

",cost);

return 0;
}
 9. MINIMUM SPANNING TREE (KRUSKAL’S ALGORITHM)
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted
undirected graph. This means it finds a subset of the edges that forms a tree that includes every
vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by
building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the
cheapest possible connection from the tree to another vertex.

The algorithm may informally be described as performing the following steps:

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in
the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 (until all vertices are in the tree).

ALGORITHM

1. Sort all the edges in non-decreasing order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far.
If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

PSEUDO-CODE

A=∅
foreach v ∈ G.V
MAKE-SET(v)
foreach (u, v) in G.E ordered by weight(u, v),
increasing if FIND-SET(u) ≠ FIND-SET(v)
A = A 𝖴 {(u, v)}
UNION(FIND-SET(u), FIND-SET(v))
return A

PROGRAM

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

// a structure to represent a weighted edge in graph

struct Edge
{
int src, dest, weight;
};

// a structure to represent a connected, undirected

// and weighted
graph struct Graph
{
// V-> Number of vertices, E-> Number of edges
int V, E;

// graph is represented as an array of edges.

// Since the graph is undirected, the edge
// from src to dest is also edge from dest
// to src. Both are counted as 1 edge
here. struct Edge* edge;
};

// Creates a graph with V vertices and E

edges struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new
Graph; graph->V = V;
graph->E = E;

graph->edge = new Edge[E];

return graph;
}

// A structure to represent a subset for union-

find struct subset
{
int parent;
int rank;
};

// A utility function to find set of an element i

// (uses path compression
technique) int find(struct subset
subsets[], int i)
{
// find root and make root as parent of i
// (path compression)
if (subsets[i].parent != i)
 subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// A function that does union of two sets of x and y

// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);

// Attach smaller rank tree under root of high

// rank tree (Union by Rank)
if (subsets[xroot].rank <
subsets[yroot].rank) subsets[xroot].parent
= yroot;
else if (subsets[xroot].rank >
subsets[yroot].rank) subsets[yroot].parent =
xroot;

// If ranks are same, then make one as root and

// increment its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

// Compare two edges according to their weights.

// Used in qsort() for sorting an array of
edges int myComp(const void* a, const
void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}

// The main function to construct MST using Kruskal's

algorithm void KruskalMST(struct Graph* graph)
{
int V = graph->V;
struct Edge result[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
// Step 1: Sort all the edges in non-decreasing
// order of their weight. If we are not allowed to
// change the given graph, we can create a copy of
// array of edges
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);

// Allocate memory for creating V

ssubsets struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );

// Create V subsets with single

elements for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}

// Number of edges to be taken is equal to V-

1 while (e < V - 1 && i < graph->E)
{
// Step 2: Pick the smallest edge. And increment
// the index for next iteration
struct Edge next_edge = graph->edge[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets,
next_edge.dest);

// If including this edge does't cause cycle,

// include it in result and increment the index
// of result for next edge
if (x != y)
{
result[e++] =
next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}

// print the contents of result[] to display the

// built MST
printf("Following are the edges in the constructed MST\n");
for (i = 0; i < e; ++i)
printf("%d -- %d == %d\n", result[i].src, result[i].dest,
 result[i].weight); return;
}