KRISHNA ENGINEERING COLLEGE

(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program - 01
Objective: Implementation of Insertion Sort
Algorithm:
Insertion Sort(A)
1. for j2 to length(A)
2. do key  A[j]
3. |> comment insert A[j] into the second sequence
4. ij-1
5. while i>0 and A[i]>key
6. do A[i+1] A[i]
7. ii-1
8. A[i+1]key

CODE:
#include <stdio.h>
void insert(int a[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

void printArr(int a[], int n)

{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are -
\n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are -
\n");
printArr(a, n);
return 0;
}
Output:
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-02
Objective: Implementation of Selection Sort
Algorithm:
Selection Sort(A,n)
1.For i=1 to n-1
2.Min=i
3.For j=j+1 to n
4. If A[j]< A[min]
6. Min=j
7. If min!=i
8. A[min]<->A[i]

CODE:
#include <stdio.h>
void selection(int arr[], int n)
{
int i, j, small;
for (i = 0; i < n-1; i++)
{
small = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[small])
small = j;
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}
void printArr(int a[], int n)
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are -
\n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are -
\n");
printArr(a, n);
return 0;
}
Output:
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-03

Objective: Implementation of Shell Sort

Algorithm:
The algorithm for shell sort can be defined in two steps--
Step 1 : Divide the original list into smaller lists
Step 2 : Sort individual sub list using any known sorting algorithm.

Code:
#include <stdio.h>
void shellSort(int array[], int n) {
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / size of(data[0]);
shellSort(data, size);
printf("Sorted array: \n");
printArray(data, size);
}

Output:
KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-04

Objective:- Implementation of Bubble Sort

Algorithm:-
begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

Code:-
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
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]);
for (c = 0 ; c < n - 1; c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1])
{
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}

Output:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-05

Objective:- Implementation of Merge Sort

Algorithm:-
MERGE_SORT(arr, beg, end)

if beg < end

set mid = (beg + end)/2
MERGE_SORT(arr, beg, mid)
MERGE_SORT(arr, mid + 1, end)
MERGE (arr, beg, mid, end)
end of if

END MERGE_SORT

Code:-
#include <stdio.h>
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = M[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[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 arr[], int size) {
for (int i = 0; i < size; i++)
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

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

printf("\n");
}
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}

Output:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-06

Objective:- Implementation of Quick Sort

Algorithm:-
Ouick sort(A,p,r)
1. if p<r
2. then q partition(A,p,r)
3. quick sort (A,p,q-1)
4 quick sort (A,p+1,r)
PARTITION (A,p,r)
1. XA[r]
2. ip-1
3. For jp to r-1
4. do if A[j] <= x
5. Theni i+1
6. Exchange A[i]A[j]
7. Exchange A[i+1]A[r]
8. Return i+1

CODE:-
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

for (int j = low; j < high; j++) {

if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
}
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Output:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-07

Objective:- Implementation of Linear and Binary Search

Algorithm:-
Linear Search
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
1. Def. binary Search (A, x):
2. N = only (A)
3. Beg=0
4. End = n – 1
5. Result = -1
6. While (beg <= end):
7. Mid = (beg + end)/2
8. If (A[mid] <= x):
9. Beg = mid + 1
10.result = mid
11.Else:
12.end = mid – 1
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Return result

Code:-
Linear search
#include <stdio.h>
int search(int array[], int n, int x) {
for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}
int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);
int result = search(array, n, x);
(result == -1) ? printf("Element not found") :
printf("Element found at index: %d", result);
}
Binary search
#include <stdio.h>
int binarySearch(int array[], int x, int low, int
high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}

Output:-
Linear Search:

Binary Search:
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-08

Objective:- Implementation of Heap Sort

Algorithm:-
Heapsort (A)
Build MaxHeap[A]
1. for i<-- length [A] downto 2
2. do exchange A[I] ← A[i].
3. Heap. Size (A) ← heapsize [A]-l
4. Max Heapefy (A,l)
Max Heapify (A, i)
1. l<-- left [i]
2. r<-- right [i]
3. if I <= heapsize [A] and A[l]>A[I]
4. then largest <-- I
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 enchange A [i]<--> A[largest]
10.Max Heapify (A, Largest)

Code:-
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Output:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-09
Objective:- Implementation of Gready Fractional
Knapsack.
Algorithm:-
Gready Fractional Knapsack()
1. {
2. For i=1 to n
3. do x[i]=0
4. Weight =0;
5. For i1 to n
6. If weight +w<=W
7. Then xi=1
8. Weight = weight +w[i]
9. Else x[i]=(w-weight )/wi
10. Weight =w
11. Break
12. Return x
13. }

CODE:-
#include <stdio.h>
int n = 5;
int c[10] = {12, 1, 2, 1, 4};
int v[10] = {4, 2, 2, 1, 10};
int W = 15;
void simple_fill() {
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)v[i]/c[i]
> (float)v[maxi]/c[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= c[maxi];
tot_v += v[maxi];
if (cur_w >= 0)
printf("Added object %d (%d$, %dKg)
completely in the bag. Space left: %d.\n", maxi +
1, v[maxi], c[maxi], cur_w);
else {
printf("Added %d%% (%d$, %dKg) of
object %d in the bag.\n", (int)((1 +
(float)cur_w/c[maxi]) * 100), v[maxi], c[maxi],
maxi + 1);
tot_v -= v[maxi];
tot_v += (1 + (float)cur_w/c[maxi]) *
v[maxi];
}
}
printf("Filled the bag with objects worth
%.2f$.\n", tot_v);
}
int main(int argc, char *argv[]) {
simple_fill();
return 0;
}
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Output:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-10
Objective:- Implementation of MST using Kruskal
Method.
Algorithm:-
1. A(|)
2. for each vertex u (- V (G)
3. do Make Set (v)
4. sort the edge of E into nondecreasing order by weight W
5. for each edge (u,v) (- E taken in nondecresing order by weight W
6. do if find set (u) =/ find set (v)
7. then AAU{(u,v)}
8. union(u,v)
9. return A

CODE:-
#include <stdio.h>
#define MAX 30
typedef struct edge {
int u, v, w;
} edge;
typedef struct edge_list {
edge data[MAX];
int n;
} edge_list;
edge_list elist;
int Graph[MAX][MAX], n;
edge_list spanlist;
void kruskalAlgo();
int find(int belongs[], int vertexno);
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

void applyUnion(int belongs[], int c1, int c2);

void sort();
void print();
void kruskalAlgo() {
int belongs[MAX], i, j, cno1, cno2;
elist.n = 0;
for (i = 1; i < n; i++)
for (j = 0; j < i; j++) {
if (Graph[i][j] != 0) {
elist.data[elist.n].u = i;
elist.data[elist.n].v = j;
elist.data[elist.n].w = Graph[i][j];
elist.n++;
}
}

sort();
for (i = 0; i < n; i++)
belongs[i] = i;
spanlist.n = 0;
for (i = 0; i < elist.n; i++) {
cno1 = find(belongs, elist.data[i].u);
cno2 = find(belongs, elist.data[i].v);
if (cno1 != cno2) {
spanlist.data[spanlist.n] = elist.data[i];
spanlist.n = spanlist.n + 1;
applyUnion(belongs, cno1, cno2);
}
}
}
int find(int belongs[], int vertexno) {
return (belongs[vertexno]);
}
void applyUnion(int belongs[], int c1, int c2) {
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

int i;
for (i = 0; i < n; i++)
if (belongs[i] == c2)
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 - %d : %d", spanlist.data[i].u,
spanlist.data[i].v, spanlist.data[i].w);
cost = cost + spanlist.data[i].w;
}
printf("\nSpanning tree cost: %d", cost);
}
int main() {
int i, j, total_cost;
n = 6;
Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 4;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 0;
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Graph[0][6] = 0;
Graph[1][0] = 4;
Graph[1][1] = 0;
Graph[1][2] = 2;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 0;
Graph[1][6] = 0;
Graph[2][0] = 4;
Graph[2][1] = 2;
Graph[2][2] = 0;
Graph[2][3] = 3;
Graph[2][4] = 4;
Graph[2][5] = 0;
Graph[2][6] = 0;
Graph[3][0] = 0;
Graph[3][1] = 0;
Graph[3][2] = 3;
Graph[3][3] = 0;
Graph[3][4] = 3;
Graph[3][5] = 0;
Graph[3][6] = 0;
Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 4;
Graph[4][3] = 3;
Graph[4][4] = 0;
Graph[4][5] = 0;
Graph[4][6] = 0;
Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][2] = 2;
Graph[5][3] = 0;
Graph[5][4] = 3;
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Graph[5][5] = 0;
Graph[5][6] = 0;
kruskalAlgo();
print();
}
Output:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-11
Objective:- Implementation of N-Queens problem.
Algorithm:-
N-Queens(k,n)
1. for i1 to n
2. do if place(k,i)
3. then n[k]i
4. if(k=n)
5. then write (n,(1….n))
6. else N-Queens(k+1,n);

PLACE(k,i)
1. for j1 to k-1
2. do if (x(j)=1) or abs(x(j)-1) = (abs (j-k))
3. then return false
4. else return true

CODE:-
#include<stdio.h>
#include<math.h>
int board[20],count;
int main()
{
int n,i,j;
void queen(int row,int n);
printf(" - N Queens Problem Using Backtracking -");
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

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))
return 0;
}
return 1;
}
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

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:-
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

Program-12
Objective:- Implementation of Travelling Salesman
Problem.
Algorithm:-
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)

CODE:-
#include <stdio.h>
int matrix[25][25], visited_cities[10], limit, cost
= 0;
int tsp(int c)
{
int count, nearest_city = 999;
int minimum = 999, temp;
for(count = 0; count < limit; count++)
{
if((matrix[c][count] != 0) &&
(visited_cities[count] == 0))
{
if(matrix[c][count] < minimum)
{
minimum = matrix[count][0] + matrix[c][count];
}
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

temp = matrix[c][count];
nearest_city = count;
}
}
if(minimum != 999)
{
cost = cost + temp;
}
return nearest_city;
}
void minimum_cost(int city)
{
int nearest_city;
visited_cities[city] = 1;
printf("%d ", city + 1);
nearest_city = tsp(city);
if(nearest_city == 999)
{
nearest_city = 0;
printf("%d", nearest_city + 1);
cost = cost + matrix[city][nearest_city];
return;
}
minimum_cost(nearest_city);
}
int main()
{
int i, j;
printf("Enter Total Number of Cities:\t");
scanf("%d", &limit);
printf("\nEnter Cost Matrix\n");
for(i = 0; i < limit; i++)
{
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)
Department of Information Technology

Session 2023-24 ODD semester

printf("\nEnter %d Elements in Row[%d]\n", limit,

i + 1);
for(j = 0; j < limit; j++)
{
scanf("%d", &matrix[i][j]);
}
visited_cities[i] = 0;
}
printf("\nEntered Cost Matrix\n");
for(i = 0; i < limit; i++)
{
printf("\n");
for(j = 0; j < limit; j++)
{
printf("%d ", matrix[i][j]);
}
}
printf("\n\nPath:\t");
minimum_cost(0);
printf("\n\nMinimum Cost: \t");
printf("%d\n", cost);
return 0;
}
OUTPUT:-