Design And Analysis Of Algorithm

(ITL-502)

Lab File

Submitted To Submitted By
Mr. Sandeep Singh Sikarwar Sagar Bhan
Assistant professor Branch- IT
Roll No.-12012053

1
S.no Name of Program Page no
1 Quick Sort 3
2 Finding min-max 6
3 Merge sort 9
4 Min Heap and Max Heap with 12
heap sort
5 Knapsack problem 18
6 Job sequencing 21
7 Huffman coding 24
8 Kruskal algorithm 28
9 Prim’s algorithm 32
10 Matrix chain multiplication 35
11 Longest common sequence 37
12 0/1 knapsack 38
13 Bellman ford 39
14 Floyd-Warshall algorithm 43
15 Queen problem 45
16 Vertex cover graph coloring 49
17 Hamiltonian cycles 52
18 0/1 knapsack with backtracking 56
INDEX

2
 ASSIGNMENT-1
Q) Quick Sort in C++

Code:

#include <iostream>
using namespace std;

int partition(int A[],

int l, int h)

int pivot = A[l]; //

initializing pivot int i
= l, j = h, t;

while (i < j)

{do

i++; // increamenting i

} while (A[i] <= pivot);

do

j--; // increamenting j

} while (A[j] > pivot);

if (i < j) // swapping
A[i] and A[j] if i<j

3
t = A[i]; A[i] = A[j];
A[j] = t;

// swapping A[i] and

A[j] if i>j 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+

4
+)

cout << arr[i] << " ";

int main()

int a[] = {4, 32, 64,

23, 78, 13, 1000}; //
in this case 1000
acting as infinity

cout << "Array before

Sorting: "; display(a,
6);

quickSort(0, 6, a);
cout << endl;

cout << "Array after

Sorting: "; display(a,
6);

return 0;

Output

5
 ASSIGNMENT-2
Q Min, max of numbers in C++
CODE:
#include <iostream>
#include <vector>
using namespace std;
struct pr {
int min;
int max;
};
struct pr getMinMax(vector<int> arr, int l, int r, int &count){
struct pr minMax, ml, mr;
int mid;
if(l==r){
minMax.min = arr[l];
minMax.max = arr[r];
return minMax;
}
if(r==l+1){
if(arr[l]>arr[r]){

minMax.min = arr[r];
minMax.max = arr[l];
}else{
minMax.min = arr[l];
minMax.max = arr[r];
}
count++;
return minMax;
}

6
else{
mid = (l+r)/2;
ml = getMinMax(arr, l, mid, count);
mr = getMinMax(arr, mid+1, r, count);
if(ml.min > mr.min){
minMax.min = mr.min;
}else{
minMax.min = ml.min;
}
if(ml.max > mr.max){
minMax.max = ml.max;
}else{
minMax.max = mr.max;
}
count+=2;
return minMax;
}
}
int main(){
system("cls");

vector<int> v;
int x, count = 0;
cout << "Enter the array (enter 0 to terminate): ";
do {
cin >> x;
v.push_back (x);
} while (x);
struct pr minMax = getMinMax(v, 0, v.size()-2, count);
cout << "Minimum element is " << minMax.min << endl;
cout << "Maximum element is " << minMax.max << endl;
7
cout << "Total number of comparisions is: " << count;
return 0;

OUTPUT:

8
 ASSIGNMENT-3
Q) merge sort in C++

CODE
#include <iostream>
using namespace std;
// A function to merge the two halves into sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}
9
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// A function to split the array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);

1
0
MergeSort(a, mid+1, high);
// Merge them to get sorted output.
Merge(a, low, high, mid);
}
}
int main()
{
system("cls");
int n, i;
cout<<"\nEnter the number of the 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);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}

OUTPUT

11
1
 ASSIGNMENT-4

MAX_heap in C++
Code:
#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,
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];
11
2
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 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";
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}

11
3
cout << endl;
int x = n;
for (int i = 1; i <= n; i++)
{
maxDelete(a, x--);
}
cout << "Sorted numbers" << endl;
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}

Output: Max heap program output

11
4
Min heap program:

Code:
#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];
11
5
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] << " ";
}

11
6
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;
}

Output: Min heap program output

11
7
 ASSIGNMENT-5
Knapsack problem
Code:
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
bool compare(pair<float, int> p1, pair<float, int> p2)
{
return p1.first > p2.first;
}
int fractionalKnapsack(vector<int> weights, vector<int> profits, int
capacity)
{
int len = weights.size();
int total_profit = 0;

// vector to store the items based on their profit/weight ratios

vector<pair<float, int>> ratio(len, make_pair(0.0, 0));
for (int i = 0; i < len; i++)
{
ratio[i] = make_pair(profits[i] / weights[i], i);
}
sort(ratio.begin(), ratio.end(), compare); // arrange them in
decreasing order according to profit/weight.
for (int i = 0; i < len; i++)
{
if (capacity == 0)
break;

21
8
 int index = ratio[i].second;
if (weights[index] < capacity)
{
capacity = capacity - weights[index];
total_profit += profits[index];
}
else
{
int fracValue = profits[index] * (float(capacity) /
float(weights[index]));
total_profit += fracValue;
capacity = 0;
}
}
return total_profit;
}

int main()
{
cout << "Enter the weights of the objects press -1 to stop:" << endl;
vector<int> weights;
int i = 1;
while (1)
{
int weight;
cout << "Enter weight for object" << i << ": ";
cin >> weight;
if (weight == -1)
break;
weights.push_back(weight);
21
9
i++;
}
cout<<endl<<"Enter the weights of the objects press -1 to
stop:"<<endl;
vector<int> profits;
i = 1;
while (1)
{
int profit;
cout << "Enter Profit for object" << i << ": ";
cin >> profit;
if (profit == -1)
break;
profits.push_back(profit);
i++;
}
int capacity;
cout << "Enter capacity of the Knapsack: ";
cin >> capacity;
cout << "Maximum profit: " << fractionalKnapsack(weights, profits,
capacity);
return 0;
}

Output:

22
0
Q) Job Sequencing in C++
Code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
bool compare(pair<int, int> p1, pair<int, int> p2)
{
return p1.second > p2.second;
}
void jobseq(vector<int> profits, vector<int> deadlines)
{
int l = profits.size();
vector<pair<int, int>> jobs_profit(l, make_pair(0, 0));
for (int i = 0; i < l; i++)
{
jobs_profit[i] = make_pair(i + 1, profits[i]);
}
sort(jobs_profit.begin(), jobs_profit.end(), compare);
// sorting deadlines in decreasing order of their profits
vector<pair<int, int>> deadlines_profit(l, make_pair(0, 0));
for (int i = 0; i < l; i++)
{
deadlines_profit[i] = make_pair(deadlines[i], profits[i]);
}
sort(deadlines_profit.begin(), deadlines_profit.end(), compare);
int max_deadline = *max_element(deadlines.begin(), deadlines.end());
vector<bool> slot(max_deadline, false);

22
1
vector<int> result(max_deadline, 0);
for (int i = 0; i < l; i++)
{
for (int k = min(l, deadlines_profit[i].first - 1); k >= 0; k--)
{
if (slot[k] == false)
{
result[k] = jobs_profit[i].first;
slot[k] = true;
break;
}
} }
cout << "results: ";
for (int i = 0; i < max_deadline; i++)
{
cout << result[i] << " ";
}
}
int main()
{
cout << "Enter jobs profit and press -1 to stop \n";
vector<int> profits;
int i = 1;
while (1)
{
int profit;
cout << "Enter profit for job " << i << ": ";
cin >> profit;
if (profit == -1)
break;

22
2
profits.push_back(profit);
i++;
}
cout << endl;
cout << "Enter jobs deadlines and press -1 to stop";
cout << endl;
vector<int> deadlines;
i = 1;
while (1)
{
int profit;
cout << "Enter deadlines for job " << i <<": ";
cin >> profit;
if (profit == -1)
break;
deadlines.push_back(profit);
i++;
}
jobseq(profits, deadlines);
return 0;
}
Output:

22
3
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)
{
22
4
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;

22
5
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()
{
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";

22
6
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:

22
7
Q) Kruskal algorithm in C++
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)

22
8
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;
}

22
9
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;
}

30
};
int main()
{
int n, e;
cout << "Enter number of vertices : ";
cin >> n;
cout << "Enter no. of edges : ";
cin >> e;
graph g(n, e);
edge *mst = g.unionfind();
}

Output:

31
Prim's algorithm
Code:
#include <iostream>
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
int main()
{
int V;
int cost = 0;
cout << "Enter no. of vertices: ";
cin >> V;
int G[V][V];
cout << "Enter graph in 2d array: " << endl;
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cin >> G[i][j];
}
}
int edge;
int visit[V];
for (int i = 0; i < V; i++)
{
visit[i] = false;
}
edge = 0;
visit[0] = true;

32
int x;
int y;
cout << "Edge"
<< " : "
<< "Weight";
cout << endl;
while (edge < V - 1)
{
int min = INT_MAX;
x = 0;
y = 0;
for (int i = 0; i < V; i++)
{
if (visit[i])
{
for (int j = 0; j < V; j++)
{
if (!visit[j] && G[i][j])
{
if (min > G[i][j])
{
min = G[i][j];
x = i;
y = j;
}
}
}
}
}

33
cout << x << " ---> " << y << " : " << G[x][y];
cost = cost + G[x][y];
cout << endl;
visit[y] = true;
edge++;
}
cout << "Minimum Cost: " << cost;
return 0;
}

Output:

34
 ASSIGNMENT-6
 Implement the dynamic programming algorithm:
Q) Matrix chain multiplication algo
Code:
#include <bits/stdc++.h>
using namespace std;
// Matrix Formation
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
//when row and coloum are equal
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 minimum count
return mini;
}
// Driver Code
int main()
{
int arr[] = {3,4,7,5,2,8};
int N = sizeof(arr) / sizeof(arr[0]);
35
// Calling the function
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, N - 1);
return 0;
}

OUTPUT:-

46
Q) Longest common sequene
Code:
#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[] = "AABCDCCBBE";
char Y[] = "SSABCDBBEYYLUS";

int m = strlen(X);
int n = strlen(Y);
cout << "Length of LCS is " << lcs(X, Y, m, n);
return 0;
}

OUTPUT :-

47
Q) 0/1 KNAPSACK ALGORITHM
Code:
#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 :-

48
Q) BELLMAN FORD ALGO in C++
Code:
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
int src, dest, weight;
};
struct Graph
{
int V, E;
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;
}
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)
{
49
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;

41
0
}
// Driver's code
int main()
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph *graph = createGraph(V, E);
// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;

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

graph->edge[0].weight = -6;
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 3;
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 5;
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 3;
// add edge 1-4 (or B-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 8;
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 2;
graph->edge[5].dest = 2;
41
1
graph->edge[5].weight = 3;
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}

OUTPUT :-

41
2
 Q) FLOYD- WARSHALL ALGO in C++

Code:
#include <stdio.h>
#define V 4
#define INF 99999
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("%s", "INF");
else
printf("%d", dist[i][j]);
}
printf("\n");
}
}
void floydWarshall(int graph[][V])
{
int dist[V][V], i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)

41
3
{
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);
}
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:-

41
4
 Assignment-7

 Implement the Backtracking algorithm:

N-Queen Problem in C++

Code:
#include <bits/stdc++.h>

#define N 4

using namespace std;

/* A utility function to print solution */

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;

/* Check this row on left side */

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

if (board[row][i])

return false;

41
5
 /* Check upper diagonal on left side */

for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])

return false;

/* Check lower diagonal on left side */

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)

/* base case: If all queens are placed

then return true */

if (col >= N)

return true;

/* Consider this column and try placing

this queen in all rows one by one */

for (int i = 0; i < N; i++) {

/* Check if the queen can be placed on

board[i][col] */

if (isSafe(board, i, col)) {

/* Place this queen in board[i][col] */

board[i][col] = 1;

/* recur to place rest of the queens */

41
6
 if (solveNQUtil(board, col + 1))

return true;

/* If placing queen in board[i][col]

doesn't lead to a solution, then

remove queen from board[i][col] */

board[i][col] = 0; // BACKTRACK

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;

// driver program to test above function

int main()

41
7
{

solveNQ();

return 0;

OUTPUT:

50
 vertex cover graph coloring in C++
code:
#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the graph

#define V 4

void printSolution(int color[]);

bool isSafe(int v, bool graph[V][V], int color[], int c)

{
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;

return true;
}

bool graphColoringUtil(bool graph[V][V], int m, int color[],

int v)
{

/* base case: If all vertices are assigned a color then return true
*/ if (v == V)
return true;

/* Consider this vertex v and

try different colors */
for (int c = 1; c <= m; c++) {

/* Check if assignment of color

c to v is fine*/
if (isSafe(v, graph, color, c)) {
color[v] = c;

/* recur to assign colors to

rest of the vertices */
if (graphColoringUtil(graph, m, color, v + 1)
== true)
return true;

/* If assigning color c doesn't

lead to a solution then remove it */
color[v] = 0;
50
 }
}

return false;
}

bool graphColoring(bool graph[V][V], int m)

{

int color[V];
for (int i = 0; i < V; i++)
color[i] = 0;

// Call graphColoringUtil() for vertex 0

if (graphColoringUtil(graph, m, color, 0) == false) {
cout << "Solution does not exist";
return false;
}

// Print the solution

printSolution(color);
return true;
}

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, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};

// Number of colors
int m = 3;

// Function call
graphColoring(graph, m);
50
 return 0;
}

OUTPUT :

50
Hamiltonian Graph in C++

Code:

#include <bits/stdc++.h>

using namespace std;

// Number of vertices in the graph

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

52
2
 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;

/* recur to construct rest of the path */

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

52
3
 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;

// Driver Code

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

// Print the solution

hamCycle(graph1);

52
4
 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}};

// Print the solution

hamCycle(graph2);

return 0;

OUTPUT :

52
5
0/1 Knapsack in c++

Code:

#include <bits/stdc++.h>
using namespace std;
int knapSack(int W, int wt[], int val[], int n)
{
// making and initializing dp array
int dp[W + 1];
memset(dp, 0, sizeof(dp));

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

for (int w = W; w >= 0; w--) {

if (wt[i - 1] <= w)
// finding the maximum value
dp[w] = max(dp[w],
dp[w - wt[i - 1]] + val[i -
1]);
}
}
return dp[W]; // returning the maximum value of knapsack
}
int main()
{int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]); cout << knapSack(W, wt, val, n);
return 0; }

52
6
OUTPUT:

62
7
62
8