Index

NO Name of Problems Page Date Remarks

no

01 Write a program that Implement of Binary 01 22-06-22

Search Algorithm.

02 Write a program for finding maximum and 03 22-06-22

minimum using divided and conquer method.

03 Write a program to compare the performance of 04 22-06-22

quick sort and bubble sort.

04 Write a program that implements Knapsack 06 22-06-22

problem in the Greedy method

05 Write a program that implements minimum 07 22-06-22

spanning tree by using Prims algorithm.

06 Write a program that implements all pair 08 22-06-22

shortest path algorithm (Warshall Algorithm).

07 Write a program that implements N-Queens 10 22-06-22

problem.

08 Write a program that implements Sum of 13 22-06-22

subsets problem.

09 Write a program that implements Graph 15 22-06-22

coloring problem.
Problem No: 01
Problem Name: Write a program that Implement of Binary Search Algorithm.
Algorithm:
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the right side
return binarySearch(arr, x, low, mid - 1)

Source Code:
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000

int main()
{
int i, j, temp, n, key, a[MAX];
cout<<"How many numbers: ";
cin>>n;
cout<<"Enter numbers: "<<endl;
for(i=0; i<n; i++)
cin>>a[i];

sort(a, a+n);
cout<<"Sorted numbers are: ";

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

cout<<a[i]<<" ";
}

do
{
int begin=0,end=n-1, mid=(begin+end)/2;
cout<<"\nEnter the number to be searched: ";
cin>>key;

while(begin<=end && key!=a[mid])

{
if(key<a[mid]) end=mid-1;
Page No: 1
 else begin=mid+1;
mid=(begin+end)/2;
}

if(key==a[mid]){
cout<<key<<" is found at the location "<<mid+1<<endl;
}
else{
cout<<key<<" is not found! try another one..."<<endl;
}
}
while(key!=0);
}

Result (Sample Input/Output):

How many numbers:6
Enter numbers:
436917
Sorted numbers are:1 3 4 6 7 9
Enter the number to be searched:7
7 is found at the location 5
Enter the number to be searched:_

Page No: 2
Problem No: 02
Problem Name: Write a program for finding maximum and minimum using divided
and conquer method.
Algorithm:
max := numbers[1]
min := numbers[1]
for i = 2 to n do
if numbers[i] > max then
max := numbers[i]
if numbers[i] < min then
min := numbers[i]
return (max, min)
Source Code:
#include <bits/stdc++.h>
using namespace std;
void findMinAndMax(vector<int> const &nums, int low, int high, int &min, int &max) {
if (low == high) {
if (max < nums[low]) {
max = nums[low]; }
if (min > nums[high]) {
min = nums[high]; }
return; }
if (high - low == 1) { if (nums[low] < nums[high]) {
if (min > nums[low]) {
min = nums[low]; }
if (max < nums[high]) {
max = nums[high]; } }
else { if (min > nums[high]) {min = nums[high]; }
if (max < nums[low]) {
max = nums[low]; } } return; }
int mid = (low + high) / 2;
findMinAndMax(nums, low, mid, min, max);
findMinAndMax(nums, mid + 1, high, min, max); }
int main() {vector<int> nums = { 7, 2, 9, 3, 1, 6, 7, 8, 4 };
int max = INT_MIN, min = INT_MAX;
int n = nums.size();
findMinAndMax(nums, 0, n - 1, min, max);
cout << "The minimum array element is " << min << endl;
cout << "The maximum array element is " << max << endl;
return 0;
}
Result (Sample Input/Output):
The minimum array element is 1
The maximum array element is 9
Page No: 3
Problem No: 03
Problem Name: Write a program to compare the performance of quick sort and
bubble sort.
Source code:
#include<bits/stdc++.h>
#define Max 15000
void BubbleSort(long a[],long n)
{
int i,j;
for(i=n-1;i>0;i--) {
for(j=0;j<i;j++) {
if(a[j]>a[j+1]) {
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp; } } } }
void quick(long a[], long beg, long end) {
long left,right,loc,temp;
left=beg;
right=end;
loc=beg;
while(left<right) {
while(a[loc]<=a[right] && loc!=right)
right--;
if (a[loc]>a[right]) {
temp=a[loc];
a[loc]=a[right];
a[right]=temp;
loc=right; }
while(a[left]<=a[loc] && loc!=left)
left++;
if (a[left]>a[loc]) {
temp=a[left];
a[left]=a[loc];
a[loc]=temp;
loc=left; } }
if (loc-beg>1)
quick(a, beg, loc-1);
if (end-loc>1)
quick(a, loc+1, end); }
int main() {

Page No: 4
long i,j,n,a[Max],b[Max],c[Max],d[Max],e[Max],temp;
clock_t start,end;
cout<<"How many numbers: ";
cin>>n;
for (i=0; i<n; i++) {
a[i]=1+rand()/1000;
b[i]=a[i]; }
start=clock();
BubbleSort(a,n-1);
end=clock();
cout<<"\nBubble sort time: "<<(end-start)/CLK_TCK<<endl;
start=clock();
quick(b, 0, n-1);
end=clock();
cout<<"\nQuick sort time: "<<(end-start)/CLK_TCK<<endl;
getch();
return 0;
}

Result (Sample Input/Output):

Time complexity of Bubble sort: O(n2)
Time complexity of Quick sort: O(n*log n)

Page No: 5
Problem No: 04
Problem Name: Write a program that implements Knapsack problem in the Greedy
method.
Algorithm:
while(i.weight){
if(i.weight<=curr_cap) {
curr_cap -= i.weight;
res += i.value; }
else {
res += (i.value * (curr_cap/i.weight));
return res; } }
Source code:
#include<bits/stdc++.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];
for (i = 0; i <= n; i++){
for (w = 0; w <= W; w++){
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w]; } }
return K[n][W]; }
int main() {
int i, n, val[20], wt[20], W;
printf("Enter number of items:");
scanf("%d", &n);
printf("Enter value and weight of items:\n");
for(i = 0;i < n; ++i){
scanf("%d%d", &val[i], &wt[i]); }
printf("Enter size of knapsack:");
scanf("%d", &W);
printf("%d", knapSack(W, wt, val, n));
return 0; }
Result (Sample Input/Output):
Enter number of items:3
Enter value and weight of items:
100 20
50 10
150 30
Enter size of knapsack: 50
250
Page No: 6
Problem No: 05
Problem Name: Write a program that implements minimum spanning tree by using
Prims algorithm.

Algorithm:
T = ∅;
U = { 1 };
while (U ≠ V)
let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U;
T = T ∪ {(u, v)}
U = U ∪ {v}
Source code:
#include <bits/stdc++.h>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX; int min_index;
for (int i = 0; i < V; i++)
if (mstSet[i] == false && key[i] < min) {min = key[i];min_index = i; }
return min_index; }
int printMST(int parent[], int graph[V][V]) {
cout<<"Edge Weight\n"; for (int i = 1; i < V; i++)
cout<<parent[i]<<" --> "<<i<<" "<<graph[i][parent[i]]<<endl; }
void primMST(int graph[V][V]) {
int parent[V]; int key[V]; bool mstSet[V];
for (int i = 0; i < V; i++) {
key[i] = INT_MAX; mstSet[i] = false; }
key[0] = 0; parent[0] = -1; for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true; for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v]; } }
printMST(parent, graph); }
int main() {int graph[V][V] =
{{ 0, 2, 0, 6, 0 },{ 2, 0, 3, 8, 5 },{ 0, 3, 0, 0, 7 },{ 6, 8, 0, 0, 9 },{ 0, 5, 7, 9, 0 } };
primMST(graph);
return 0;
}
Result (Sample Input/Output):
Edge Weight
0 --> 1 2
1 --> 2 3
0 --> 3 6
1 --> 4 5

Page No: 7
Problem No: 06
Problem Name: Write a program that implements all pair shortest path algorithm
(Warshall Algorithm).

Algorithm:
let dist be V × V matrix of minimum distances initialized to INFINITY
for each vertex v
dist[v][v] = 0
for each edge (u, v)
dist[u][v] = weight(u, v)
for k from 0 to |V| – 1
for i from 0 to |V| – 1
for j from 0 to |V| – 1
if (dist[i][k] + dist[k][j]) is less than dist[i][j] then
dist[i][j] = dist[i][k] + dist[k][j]
Source code:
#include <bits/stdc+++.h>
using namespace std;
#define INF 2000000
int D[10][10]={0};
void warshall(int n)
{
int i,j,k;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (D[i][j]>D[i][k]+D[k][j])
D[i][j]=D[i][k]+D[k][j];
}
}
int main()
{
int i,j,v;
char w[20];
printf("Enter the number of vertices:");
scanf("%d",&v);
printf("\nEnter the Adjacency matrix of cost of edges (i=infinity): \n");
for (i=1;i<=v;i++)
for (j=1;j<=v;j++)
{
scanf("%s",&w);
Page No: 8
if(w[0]=='i')
D[i][j]=INF;
else
D[i][j]=atoi(w);
}
warshall(v);
printf("\nAdjacency matrix of lowest cost between the vertices, D%d: \n",v);
for (i=1;i<=v;i++)
{
for (j=1;j<=v;j++)
printf("%d\t",D[i][j]);
printf("\n");
}
return 0;
}

Result (Sample Input/Output):

Enter the number of vertices:3

Enter the Adjacency matrix of cost of edges (i=infinity):
321457890145
Adjacency matrix of lowest cost between the vertices, D3:
1 2 1
4 5 5
0 1 1

Page No: 9
Problem No: 07
Problem Name: Write a program that implements N-Queens problem.

Algorithm:
IS-ATTACK(i, j, board, N)
// checking in the column j
for k in 1 to i-1
if board[k][j]==1
return TRUE
// checking upper right diagonal
k = i-1
l = j+1
while k>=1 and l<=N
if board[k][l] == 1
return TRUE
k=k+1
l=l+1
// checking upper left diagonal
k = i-1
l = j-1
while k>=1 and l>=1
if board[k][l] == 1
return TRUE
k=k-1
l=l-1
return FALSE
N-QUEEN(row, n, N, board)
if n==0
return TRUE
for j in 1 to N
if !IS-ATTACK(row, j, board, N)
board[row][j] = 1
if N-QUEEN(row+1, n-1, N, board)
return TRUE
board[row][j] = 0 //backtracking, changing current decision
return FALSE
Source code:
#include<bits/stdc++.h>
Using namespace std;
int board[20],count;
int main()
{
int n,i,j;
void queen(int row,int n);
printf(" - N Queens Problem Using Backtracking -");
Page No: 10
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
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;
}
void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)

Page No: 11
{
if(place(row,column))
{
board[row]=column;
if(row==n)
print(n);
else
queen(row+1,n);
}
}
}

Result (Sample Input/Output):

Enter number of Queens:4

Solution 1:
1 2 3 4
1 - Q - -
2 - - - Q
3 Q - - -
4 - - Q -

Solution 2:
1 2 3 4
1 - - Q -
2 Q - - -
3 - - - Q
4 - Q - -

Page No: 12
Problem No: 08
Problem Name: Write a program that implements Sum of subsets problem.

Algorithm:
void subset_sum(int list[], int sum, int starting_index, int target_sum)
{
if( target_sum == sum )
{
subset_count++;
if(starting_index < list.length)
subset_sum(list, sum - list[starting_index-1], starting_index, target_sum);
}
else
{
for( int i = starting_index; i < list.length; i++ )
{
subset_sum(list, sum + list[i], i + 1, target_sum);
}
}
}
Source code:
#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printValues(int A[], int size){
for (int i = 0; i < size; i++) {
printf("%*d", 5, A[i]); }
printf("\n"); }
void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const
target_sum){
total_nodes++;
if (target_sum == sum) {
printValues(t, t_size);
subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
return;}
else {
for (int i = ite; i < s_size; i++) {
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}}}

void generateSubsets(int s[], int size, int target_sum){

int* tuplet_vector = (int*)malloc(size * sizeof(int));
Page No: 13
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);}
int main(){
int set[] = { 5, 6, 12 , 54, 2 , 20 , 15 };
int size = sizeof(set) / sizeof(set[0]);
printf("The set is ");
printValues(set , size);
generateSubsets(set, size, 25);
printf("Total Nodes generated %d\n", total_nodes);
return 0;
}

Result (Sample Input/Output):

The set is 5 6 12 54 2 20 15
5 6 12 2
5 20
Total Nodes generated 127

Page No: 14
Problem No: 09
Problem Name: Write a program that implements Graph coloring problem.
Algorithm:
BFS algorithm is used to traverse all the vertices.
Take a vertex and colour it yellow.
Colour all its neighbour vertices as blue.
Colour the next level vertices as yellow and so,
until all vertices are coloured.
Source code:
#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<int> > g; vector<int> color;
bool v[11101];
void c(int node,int n)
{
queue<int> q;
if(v[node])
return;
color[node]=n;
v[node]=1;
for(i=0;i<n;i++)
{
if(!v[g[node][i]])
{
q.push(g[node][i]);
}
}
while(!q.empty())
{
c(q.front(),(n+1)%2);
q.pop();
}
return;
}
int main()
{
int a,b;
cout<<"Enter number of vertices and edges respectively:"; cin>>n>>e;
cout<<"'Y' is for Yellow Colour and 'B' is for Blue Colour."; cout<<"\n";
g.resize(n);
Page No: 15
color.resize(n); memset(v,0,sizeof(v)); for(i=0;i<e;i++)
{
cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
cin>>a>>b;
a--;
b--;
g[a].push_back(b); g[b].push_back(a);
}
c(0,1);
for(i=0;i<n;i++)
{
if(color[i]) cout<<i+1<<" "<<'Y'<<"\n";
else cout<<i+1<<" "<<'B'<<"\n";
}
}

Result (Sample Input/Output):

Enter number of vertices and edges respectively: 1 2

'Y' is for Yellow Colour and 'B' is for Blue Colour.
Enter edge vertices of edge 1 : 1 2

Page No: 16