FINAL LAB ASSIGNMENT

DESIGN AND ANALYSIS OF ALGORITHMS

(ITC 502)
Submitted to :- Submitted by:-
Mr. Sandeep Sikarwar Name -Manish Kumar
Branch- IT
Roll no :- 12012048
Serial no. PROGRAMS Page no.
1. QUICK SORT ALGORITHM 03 - 04
2. PROGRAM FOR FINDING MIN-MAX 04 - 05
3. PROGRAM FOR MERGE SORT. 06 - 08
4. HEAP SORT ALGORITHM 08 - 12
( a ) MAX HEAP ALGORITHM 09 - 10
( b ) MIN HEAP ALGORITHM 10 - 12
5. GREEDY ALGORITHM IMPLEMENTATION 12 - 24
1. KNAPSACK PROBLEM 12 - 13
2. Job Sequence 14 -15
3. Huffman coding 15 - 18
4. Kruskal algorithm 18 - 22
5. Prim's algorithm 22 - 24

6. DYNAMIC PROGRAMMING IMPLEMENTATION 25 - 33

(a) Matrix chain multiplication. 25 - 26
(b) Longest Common sequence. 26 -27

(c) 0/1 knapsack. 27 - 28

(d) Bellman ford. 28 - 31
(e) Floyd-Warshall algorithm. 32 - 33

7. Implement the backtrack algorithms: 34 - 44

(a) Queen Problem. 34 - 35
(b) Vertex cover graph coloring. 35 - 37
(c)Hamiltonian cycles. 37 – 39
(d) Branch and bound technique. 39 - 41
(e) 0/1 Knapsack problem. 42 – 43
(f) Traveling Salesman Problem. 43 - 44
1 .PROGRAM FOR QUICK SORT ALGORITHM
#include <iostream>
using namespace std;
int partition(int A[], int l, int h)
{
int pivot = A[l];
int i = l, j = h, t;
while (i < j)
{
do
{
i++;
} while (A[i] <= pivot);
do
{
j--;
} while (A[j] > pivot);
if (i < j)
{
t = A[i];
A[i] = A[j];
A[j] = t;
}
}
t = A[j];
A[j] = A[l];
A[l] = t;
return j;
}
void quickSort(int l, int h, int a[])
{
int j;
if (l < h)
{
j = partition(a, l, h);
quickSort(l, j, a);
quickSort(j + 1, h, a);
}
}
void display(int arr[], int n)
{

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

{
cout << arr[i] << " ";
}
}
int main()
{
int a[] = {8, 43, 6, 9, 56, 12};
cout << "Array before Sorting: ";
display(a, 6);
quickSort(0, 6, a);
cout << endl;
cout << "Array after Sorting: ";
display(a, 6);
return 0;
}

Output:-

2. Program for finding Min-Max

#include <iostream>
using namespace std;
void min_max(int a[], int l, int h, int *min, int *max)
{
if (l == h)
{
*min = a[l];
*max = a[l];
}
else
{
if (l == h - 1)
{
if (a[l] > a[h])
{
*min = a[h];
*max = a[l];
}
else
{
*min = a[l];
 *max = a[h];
}
}
else
{
int mid = (l + h) / 2;
int min1, max1;
min1 = INT32_MAX;
max1 = INT32_MIN;
min_max(a, l, mid, min, max);
min_max(a, mid + 1, h, &min1, &max1);
if (*max < max1)
{
*max = max1;
}
if (*min > min1)
{
*min = min1;
}
}
}
}
int main()
{
int a[] = {12, 57, 22, 11, 1, 6, 75, 25};
int min, max;
max = min = a[0];
min_max(a, 0, 8, &min, &max);
cout << "Max Number of elements in the array " << max << endl;
cout << "Min Number of elements in the array " << min << endl;
return 0;
}

Output:-
3. WRITE A PROGRAM FOR MERGE SORT.
#include <iostream>

using namespace std;

void Merge(int *a, int low, int high, int mid)

{

int i, j, k, temp[high - low + 1];

i = low;
k = 0;
j = mid + 1;

while (i <= mid && j <= high)

{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}

while (i <= mid)

{
temp[k] = a[i];
k++;
i++;
}

while (j <= high)

{
temp[k] = a[j];
k++;
j++;
}

for (i = low; i <= high; i++)

{
a[i] = temp[i - low];
}
}

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

}
}

int main()
{
system("cls");
int n, i;
cout << "\nEnter the number of data element to be sorted: ";
cin >> n;

int arr[n];
for (i = 0; i < n; i++)
{
cout << "Enter element " << i + 1 << ": ";
cin >> arr[i];
}

MergeSort(arr, 0, n - 1);

cout << "\nSorted Data ";

for (i = 0; i < n; i++)
cout << "->" << arr[i];

return 0;
}
OUTPUT

4. WRITE A PROGRAM FOR MIN HEAP, MAX HEAP AND

MAX HEAP WITH APPLY HEAP SORT.
MAX HEAP PROGRAM :-
#include <iostream>
using namespace std;
void maxHeapinsert(int a[], int n)
{
int temp = a[n];
int i = n;
while (i > 1 && temp > a[i / 2])
{
a[i] = a[i / 2];
i = i / 2;
}
a[i] = temp;
}
void maxDelete(int a[], int n)
{
int x, i, j;
x = a[1];
a[1] = a[n];
i = 1, j = 2 * i;
while (j < n - 1)
 {
if (a[j + 1] > a[j])
{
j = j + 1;
}
if (a[i] < a[j])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
i = j;
j = 2 * i;
}
else
break;
}
a[n] = x;
}
int main()
{
int n;
cout << "Number of Elements you want to enter in a max heap: ";
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 2; i <= n; i++)
{
maxHeapinsert(a, i);
}
cout << endl;
cout << "Max Heap formed :- " << endl;
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
int x = n;
for (int i = 1; i <= n; i++)
{
maxDelete(a, x--);
}
cout << "Sorted numbers" << endl;
}
MAX HEAP OUTPUT :-

MIN HEAP PROGRAM :-

#include <iostream>
using namespace std;
void minHeapinsert(int a[], int n)
{
int temp = a[n];
int i = n;
while (i > 1 && temp < a[i / 2])
{
a[i] = a[i / 2];
i = i / 2;
}
a[i] = temp;
}
void minDelete(int a[], int n)
{
int x, i, j;
x = a[1];
a[1] = a[n];
i = 1, j = 2 * i;
while (j < n - 1)
{
if (a[j + 1] < a[j])
{
j = j + 1;
}
if (a[i] > a[j])
{
int t = a[i];
 a[i] = a[j];
a[j] = t;
i = j;
j = 2 * i;
}
else
break;
}
a[n] = x;
}
int main()
{
int n;
cout << "how many elements you want to enter in a min heap: ";
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 2; i <= n; i++)
{
minHeapinsert(a, i);
}
cout << endl;
cout << "Min Heap formed:";
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
int x = n;
for (int i = 1; i <= n; i++)
{
minDelete(a, x--);
}
cout << "Sorted numbers " << endl;
for (int i = n; i >= 1; i--)
{
cout << a[i] << " ";
}
return 0;
}
MIN HEAP OUTPUT :-

ASSIGNMENT 5
GREEDY ALGORITHM IMPLEMENTATION
• Knapsack Problem:
CODE:
#include <iostream>
using namespace std;
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];
}
 }

return K[n][W];
}

int main()
{
system("cls");
cout << "Enter the number of items in a Knapsack:";
int n, W;
cin >> n;
int val[n], wt[n];
for (int i = 0; i < n; i++)
{
cout << "Enter value and weight for item " << i << ":";
cin >> val[i];
cin >> wt[i];
}

cout << "Enter the capacity of knapsack: ";

cin >> W;
cout << knapSack(W, wt, val, n);
return 0;
}

OUTPUT:
 • JOB SEQUENCING:
CODE:
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

class job
{
public:
int deadLine, profit;
};
bool compare(job A, job B)
{
return A.profit > B.profit;
}
int main()
{
system("cls");
int n;
cout << "Enter the total number: ";
cin >> n;

job arr[n];

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

cin >> arr[i].deadLine >> arr[i].profit;

sort(arr, arr + n, compare);

int profit[n], totalProfit = 0;

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

profit[i] = -1;

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

{
int deadLine = arr[i].deadLine;

for (int j = deadLine; j >= 1; j--)

{
 if (profit[j] == -1)
{
profit[j] = arr[i].profit;
break;
}
}
}

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

{
if (profit[i] > -1)
totalProfit += profit[i];
}

cout << "Total Profit = " << totalProfit << endl;

return 0;
}

OUTPUT:

• HUFFMAN CODING:
CODE:
#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

class Huffman_Codes
{
struct New_Node
{
 char data;
size_t freq;
New_Node *left;
New_Node *right;
New_Node(char data, size_t freq) : data(data),
freq(freq),
left(NULL),
right(NULL)
{
}
~New_Node()
{
delete left;
delete right;
}
};

struct compare
{
bool operator()(New_Node *l, New_Node *r)
{
return (l->freq > r->freq);
}
};

New_Node *top;

void print_Code(New_Node *root, string str)

{
if (root == NULL)
return;

if (root->data == '$')
{
print_Code(root->left, str + "0");
print_Code(root->right, str + "1");
}

if (root->data != '$')
{
cout << root->data << " : " << str << "\n";
print_Code(root->left, str + "0");
print_Code(root->right, str + "1");
}
}

public:
Huffman_Codes(){};
 ~Huffman_Codes()
{
delete top;
}
void Generate_Huffman_tree(vector<char> &data, vector<size_t> &freq,
size_t size)
{
New_Node *left;
New_Node *right;
priority_queue<New_Node *, vector<New_Node *>, compare> minHeap;

for (size_t i = 0; i < size; ++i)

{
minHeap.push(new New_Node(data[i], freq[i]));
}

while (minHeap.size() != 1)
{
left = minHeap.top();
minHeap.pop();

right = minHeap.top();
minHeap.pop();

top = new New_Node('$', left->freq + right->freq);

top->left = left;
top->right = right;
minHeap.push(top);
}
print_Code(minHeap.top(), "");
}
};
int main()
{
system("cls");
int n, f;
char ch;
Huffman_Codes set1;
vector<char> data;
vector<size_t> freq;
cout << "Enter the number of elements \n";
cin >> n;
cout << "Enter the characters \n";
for (int i = 0; i < n; i++)
{
cin >> ch;
data.insert(data.end(), ch);
}
 cout << "Enter the frequencies \n";
for (int i = 0; i < n; i++)
{
cin >> f;
freq.insert(freq.end(), f);
}
size_t size = data.size();
set1.Generate_Huffman_tree(data, freq, size);

return 0;
}

OUTPUT:

• KRUSKAL ALGORITHM:
CODE:
#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

class edge
{
public:
int s;

int d;

int w;

edge()
{
}

edge(int src, int des, int wei)

{

s = src;

d = des;

w = wei;
}
};

bool compare(edge e1, edge e2)

{

return e1.w < e2.w;

}

int findparent(int i, int *parent)

{

if (parent[i] == i)

return i;

return findparent(parent[i], parent);

}

class graph
{

public:
int e, n;

edge *v;

graph(int n, int e)
{
 this->n = n;

this->e = e;

v = new edge[e];

for (int i = 0; i < e; i++)

int x, y, w;

cout << "ENTER VERTICES AND WEIGHT OF EDGE " << i + 1 << " : ";

cin >> x >> y >> w;

edge e(x, y, w);

v[i] = e;
}
}

edge *unionfind()
{

int *parent = new int[n];

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

{

parent[i] = i;
}

sort(v, v + e, compare);

edge *output;

output = new edge[n - 1];

int count = 0, i = 0;

while (count != n - 1)
{

edge c = v[i];

int sourceparent = findparent(v[i].s, parent);

 int desparent = findparent(v[i].d, parent);

if (sourceparent != desparent)
{

output[count] = c;

parent[sourceparent] = desparent;

count++;
}

i++;
}

int sum = 0;

cout << endl

<< "-------MST-------\n";

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

{

cout << output[i].s << " " << output[i].d << " " << output[i].w
<< endl;

sum += output[i].w;
}

cout << "\nWEIGHT OF MST IS " << sum;

return output;
}
};

int main()
{
system("cls");

int n, e;

cout << "KRUSKAL'S ALGORITHM\nENTER NUMBER OF VERTICES : ";

cin >> n;

cout << "ENTER NUMBER OF EDGEES : ";

 cin >> e;

graph g(n, e);

edge *mst = g.unionfind();

}

OUTPUT:

• PRIM’S ALGORITHM:
CODE:
#include <iostream>

using namespace std;

// Number of vertices in the graph

const int V = 6;
int min_Key(int key[], bool visited[])
{
int min = 999, min_index; // 999 represents an Infinite value

for (int v = 0; v < V; v++)

 {
if (visited[v] == false && key[v] < min)
{
// vertex should not be visited
min = key[v];
min_index = v;
}
}
return min_index;
}

// Function to print the final MST stored in parent[]

int print_MST(int parent[], int cost[V][V])
{
int minCost = 0;
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
{
cout << parent[i] << " - " << i << " \t" << cost[i][parent[i]] << "
\n";
minCost += cost[i][parent[i]];
}
cout << "Total cost is: " << minCost;
}
void find_MST(int cost[V][V])
{
int parent[V], key[V];
bool visited[V];

// Initialize all the arrays

for (int i = 0; i < V; i++)
{
key[i] = 999; // 99 represents an Infinite value
visited[i] = false;
parent[i] = -1;
}

key[0] = 0; // Include first vertex in MST by setting its key vaue to 0.

parent[0] = -1;
for (int x = 0; x < V - 1; x++)
{

int u = min_Key(key, visited);

visited[u] = true; // Add the minimum key vertex to the MST

// Update key and parent arrays

for (int v = 0; v < V; v++)
 {

if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])

{
parent[v] = u;
key[v] = cost[u][v];
}
}
}

// print the final MST

print_MST(parent, cost);
}

// main function
int main()
{
system("cls");
int cost[V][V];
cout << "Enter the vertices for a graph with 6 vetices";
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cin >> cost[i][j];
}
}
find_MST(cost);
return 0;
}
OUTPUT:
Assignment-6
IMPLEMENT THE DYNAMIC PROGRAMMING ALGORITHM:
• MATRIX CHAIN MULTIPLICATION ALGO
#include <bits/stdc++.h>
using namespace std;

int MatrixChainOrder(int p[], int i, int j)

{
if (i == j)
return 0;
int k;
int mini = INT_MAX;
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];

mini = min(count, mini);

}

return mini;
}

int main()
{
int arr[] = {3, 4, 7, 5, 2, 8};
int N = sizeof(arr) / sizeof(arr[0]);

cout << "Minimum number of multiplications is "

<< MatrixChainOrder(arr, 1, N - 1);
return 0;
}
OUTPUT:-

• LONGEST COMMON SEQUENE

#include <bits/stdc++.h>
using namespace std;

int lcs(char *X, char *Y, int m, int n)

{
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}

int main()
{
char X[] = "MANISH Kumar";
char Y[] = "PRAJA PATI";

int m = strlen(X);
int n = strlen(Y);

cout << "Length of LCS is " << lcs(X, Y, m, n);

return 0;
}
OUTPUT :-

• 0/1 KNAPSACK ALGO

#include <bits/stdc++.h>
using namespace std;

int max(int a, int b) { return (a > b) ? a : b; }

int knapSack(int W, int wt[], int val[], int n)

{

if (n == 0 || W == 0)
return 0;

if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

else
return max(
val[n - 1] + knapSack(W - wt[n - 1],
wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
int main()
{
int val[] = {80, 200, 320};
int wt[] = {102, 206, 56};
int W = 500;
int n = sizeof(val) / sizeof(val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
OUTPUT :-

• BELLMAN FORD ALGO

#include <bits/stdc++.h>
using namespace std;

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

struct Graph
{

int V, E;

struct Edge *edge;

};

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;
}
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}

void BellmanFord(struct Graph *graph, int src)

{
int V = graph->V;
int E = graph->E;
int dist[V];

for (int i = 0; i < V; i++)

dist[i] = INT_MAX;
dist[src] = 0;

for (int i = 1; i <= V - 1; i++)

{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}

for (int i = 0; i < E; i++)

{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
{
printf("Graph contains negative weight cycle");
return;
}
}

printArr(dist, V);

return;
}

int main()
{
 int V = 5;
int E = 8;
struct Graph *graph = createGraph(V, E);

graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -6;

graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 3;

graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 5;

graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 3;

graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 8;

graph->edge[5].src = 2;
graph->edge[5].dest = 2;
graph->edge[5].weight = 3;

graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;

BellmanFord(graph, 0);

return 0;
}
OUTPUT :-

• FLOYD- WARSHALL ALGO

#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++)
{

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(
"The 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, 8, INF, 16},

{INF, 0, 7, INF},
{INF, INF, 0, 9},
{INF, INF, INF, 0}};

floydWarshall(graph);
return 0;
}
OUTPUT:-
 ASSIGNMENT 7
BACKTRACKING ALGORITHM IMPLEMENTATION

1. QUEEN PROBLEMS
#include <bits/stdc++.h>
#define N 4
using namespace std;
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << " " << board[i][j] << " ";
printf("\n");
}
}
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;

return true;
}
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++)
{
if (isSafe(board, i, col))
{
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
 }
bool solveNQ()
{
int board[N][N] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}};

if (solveNQUtil(board, 0) == false)
{
cout << "Solution does not exist";
return false;
}

printSolution(board);
return true;
}
int main()
{
solveNQ();
return 0;
}

Output:-

2.VERTEX COVER GRAPH COLOURING PROBLEM

#include <bits/stdc++.h>
using namespace std;
#define V 4
void printSolution(int color[]);
bool isSafe(bool graph[V][V], int color[])
{
for (int i = 0; i < V; i++)
for (int j = i + 1; j < V; j++)
if (graph[i][j] && color[j] == color[i])
return false;
return true;
}
bool graphColoring(bool graph[V][V], int m, int i,
int color[V])
{
if (i == V)
{
if (isSafe(graph, color))
{
printSolution(color);
return true;
}
return false;
}
for (int j = 1; j <= m; j++)
{
color[i] = j;
if (graphColoring(graph, m, i + 1, color))
return true;

color[i] = 0;
}

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

return 0;
}
 Output:-

3.HAMILTONIAN CYCLES
#include <bits/stdc++.h>
using namespace std;
#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)
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)
{
cout << "\nSolution does not exist";
return false;
}

printSolution(path);
return true;
}
void printSolution(int path[])
{
cout << "Solution Exists:"
" Following is one Hamiltonian Cycle \n";
for (int i = 0; i < V; i++)
cout << path[i] << " ";
cout << path[0] << " ";
cout << endl;
}
int main()
{
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:-

4.Branch and bound technique Problem

#include <bits/stdc++.h>
using namespace std;
#define N 4
struct Node
{
Node *parent;
int pathCost;
int cost;
int workerID;
int jobID;
bool assigned[N];
};
Node *newNode(int x, int y, bool assigned[],
Node *parent)
{
Node *node = new Node;

for (int j = 0; j < N; j++)

node->assigned[j] = assigned[j];
node->assigned[y] = true;

node->parent = parent;
node->workerID = x;
node->jobID = y;

return node;
}
int calculateCost(int costMatrix[N][N], int x,
int y, bool assigned[])
{
int cost = 0;
bool available[N] = {true};
for (int i = x + 1; i < N; i++)
 {
int min = INT_MAX, minIndex = -1;
for (int j = 0; j < N; j++)
{
if (!assigned[j] && available[j] &&
costMatrix[i][j] < min)
{
minIndex = j;
min = costMatrix[i][j];
}
}
cost += min;
available[minIndex] = false;
}
return cost;
}
struct comp
{
bool operator()(const Node *lhs,
const Node *rhs) const
{
return lhs->cost > rhs->cost;
}
};
void printAssignments(Node *min)
{
if (min->parent == NULL)
return;

printAssignments(min->parent);
cout << "Assign Worker " << char(min->workerID + 'A')
<< " to Job " << min->jobID << endl;
}
int findMinCost(int costMatrix[N][N])
{
priority_queue<Node *, std::vector<Node *>, comp> pq;
bool assigned[N] = {false};
Node *root = newNode(-1, -1, assigned, NULL);
root->pathCost = root->cost = 0;
root->workerID = -1;
pq.push(root);
while (!pq.empty())
{
Node *min = pq.top();
pq.pop();
int i = min->workerID + 1;
if (i == N)
{
 printAssignments(min);
return min->cost;
}
for (int j = 0; j < N; j++)
{
if (!min->assigned[j])
{
Node *child = newNode(i, j, min->assigned, min);
child->pathCost = min->pathCost + costMatrix[i][j];
child->cost = child->pathCost +
calculateCost(costMatrix, i, j, child-
>assigned);
pq.push(child);
}
}
}
}
int main()
{
int costMatrix[N][N] =
{
{9, 2, 7, 8},
{6, 4, 3, 7},
{5, 8, 1, 8},
{7, 6, 9, 4}};
cout << "\nOptimal Cost is "
<< findMinCost(costMatrix);
return 0;
}
// job assignment using branch and bound technique

Output:-
5. 0/1 Knapsack problem.
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
void printknapSack(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];
}
}
int res = K[n][W];
cout << res << endl;
w = W;
for (i = n; i > 0 && res > 0; i--)
{
if (res == K[i - 1][w])
continue;
else
{
cout << " " << wt[i - 1];
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
int main()
{
int val[] = {80, 110, 120};
int wt[] = {20, 30, 40};
int W = 80;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0;
}
Output:-

6.Traveling Salesman Problem.

#include <bits/stdc++.h>
using namespace std;
#define V 4
void tsp(int graph[][V], vector<bool> &v, int currPos,
int n, int count, int cost, int &ans)
{
if (count == n && graph[currPos][0])
{
ans = min(ans, cost + graph[currPos][0]);
return;
}
for (int i = 0; i < n; i++)
{
if (!v[i] && graph[currPos][i])
{
v[i] = true;
tsp(graph, v, i, n, count + 1,
cost + graph[currPos][i], ans);
v[i] = false;
}
}
};

int main()
{
int n = 4;
int graph[][V] = {
{0, 20, 15, 20},
{10, 0, 15, 25},
 {15, 35, 0, 10},
{25, 25, 30, 0}};
vector<bool> v(n);
for (int i = 0; i < n; i++)
v[i] = false;
v[0] = true;
int ans = INT_MAX;
tsp(graph, v, 0, n, 1, 0, ans);
cout << ans;
return 0;
}

Output:-