Scribd
Upload
42 views32 pages

Daa Practial

The document contains 5 programs: 1) C++ code to implement merge sort and calculate time complexity. 2) C++ code using dynamic programming to solve the 0/1 knapsack problem. 3) C++ code using Prim's algorithm to find the minimum spanning tree of an undirected graph. 4) C++ code using backtracking to solve the N queens problem. 5) C++ code to perform BFS traversal on a graph and check if a graph is connected using DFS.

Uploaded by

Purva Sukhwal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
42 views32 pages

Daa Practial

The document contains 5 programs: 1) C++ code to implement merge sort and calculate time complexity. 2) C++ code using dynamic programming to solve the 0/1 knapsack problem. 3) C++ code using Prim's algorithm to find the minimum spanning tree of an undirected graph. 4) C++ code using backtracking to solve the N queens problem. 5) C++ code to perform BFS traversal on a graph and check if a graph is connected using DFS.

Uploaded by

Purva Sukhwal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 32

List of Programs :

1) C++ code for implementing Merge Sort algorithm to sort a given


set of elements and determine the time required to sort the
elements

2) C++ code to implement the 0/1 Knapsack problem using


Dynamic Programming

3) Find the Minimum Cost Spanning Tree of a given undirected


graph using Prim’s algorithm.

4) Implement N Queen's problem using Back Tracking.

5) C++ code for:


A) Printing all the nodes reachable from a given starting node in
a digraph using BFS method
B) Checking whether a given graph is connected or not using
DFS method
Program 1
C++ code for implementing Merge Sort algorithm to sort a given set of
elements and determine the time required to sort the elements.
Algorithm:
 start
 declare array and left, right, mid variable
 perform merge function.
If left > right
return
mid= (left+right)/2
merge sort(array, left, mid)
merge sort(array, mid+1, right)
merge(array, left, mid, right)
 Stop

Code:
#include <iostream>
using namespace std;
void merge(int array[], int const left, int const mid,
int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne
= 0, // Initial index of first sub-array
indexOfSubArrayTwo
= 0; // Initial index of second sub-array
int indexOfMergedArray
= left; // Initial index of merged array
while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
<= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;
auto mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
void printArray(int A[], int size)
{
for (auto i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
auto arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}

Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
Program 2
C++ code to implement the 0/1 Knapsack problem using Dynamic
Programming.
Algorithm:
 Begin
 Input set of items each with a weight and a value
 Set knapsack capacity
 Create a function that returns maximum of two integers.
 Create a function which returns the maximum value that can be put in a
knapsack of capacity W
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
for i = 0 to n
for wt = 0 to W
if (i == 0 or wt == 0) Do K[i][wt] = 0
else if (w[i - 1] <= wt)
Compute: K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i -1][wt])
Else K[i][wt] = K[i - 1][wt]
return K[n][W]
 Call the function and print.
 End of function of 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)
{
int i, w;
vector<vector<int> > K(n + 1, vector<int>(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];
}

// Driver Code
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);

cout << knapSack(W, weight, profit, n);

return 0;
}

Output:
220
Program 3
Find the Minimum Cost Spanning Tree of a given undirected graph using
Prim’s algorithm.
Algorithm
 Determine an arbitrary vertex as the starting vertex of the MST.
 Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
 Find edges connecting any tree vertex with the fringe vertices.
 Find the minimum among these edges.
 Add the chosen edge to the MST if it does not form any cycle.
 Return the MST and exit

Code :
#include <bits/stdc++.h>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(int parent[], int graph[V][V])
{
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
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);
}
// Driver's code
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 } };
// Print the solution
primMST(graph);
return 0;
}

Output :
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
Program 4
C++ code to implement N Queen's problem using Back Tracking.
Algorithm:
while there are untried configurations
{ generate the next configuration
if queens don't attack in this configuration then
{ print this configuration; }
}

Code:

#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++)
if(board[i][j])
cout << "Q ";
else cout<<". ";
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)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
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()
{
solveNQ();
return 0;
}

Output:
..Q.
Q...
...Q
..Q.
Program 5
C++ code to print BFS traversal.
Algorithm:
 Choose a starting vertex, mark it as visited, and add it to a queue.
 While the queue is not empty:
 Dequeue a vertex from the queue and process it (e.g., print its value).
 Enqueue all its adjacent vertices that have not been visited and mark them
as visited.
 Repeat step 2 until the queue is empty.

Code:
#include <bits/stdc++.h>
using namespace std;
class Graph {
int V;
vector<list<int> > adj;
public:
Graph(int V);
void addEdge(int v, int w);
void BFS(int s);
};
Graph: :Graph(int V)
{
this->V = V;
adj.resize(V);
}
void Graph: :addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::BFS(int s)
{
vector<bool> visited;
visited.resize(V, false);
list<int> queue;
visited[s] = true;
queue.push_back(s);
while (!queue.empty()) {
s = queue.front();
cout << s << " ";
queue.pop_front();
for (auto adjacent : adj[s]) {
if (!visited[adjacent]) {
visited[adjacent] = true;
queue.push_back(adjacent);
}
}
}
}
// Driver code
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) \n";
g.BFS(2);
return 0;
}

Output:

Following is Breadth First Traversal (starting from vertex 2)


2031
List of Programs :
1) C++ code for implementing Merge Sort algorithm to sort a given
set of elements and determine the time required to sort the
elements

2) C++ code to implement the 0/1 Knapsack problem using


Dynamic Programming

3) Find the Minimum Cost Spanning Tree of a given undirected


graph using Prim’s algorithm.

4) Implement N Queen's problem using Back Tracking.

5) C++ code for:


A) Printing all the nodes reachable from a given starting node in
a digraph using BFS method
B) Checking whether a given graph is connected or not using
DFS method
Program 1
C++ code for implementing Merge Sort algorithm to sort a given set of
elements and determine the time required to sort the elements.
Algorithm:
 start
 declare array and left, right, mid variable
 perform merge function.
If left > right
return
mid= (left+right)/2
merge sort(array, left, mid)
merge sort(array, mid+1, right)
merge(array, left, mid, right)
 Stop

Code:
#include <iostream>
using namespace std;
void merge(int array[], int const left, int const mid,
int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne
= 0, // Initial index of first sub-array
indexOfSubArrayTwo
= 0; // Initial index of second sub-array
int indexOfMergedArray
= left; // Initial index of merged array
while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
<= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;
auto mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
void printArray(int A[], int size)
{
for (auto i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
auto arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}

Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
Program 2
C++ code to implement the 0/1 Knapsack problem using Dynamic
Programming.
Algorithm:
 Begin
 Input set of items each with a weight and a value
 Set knapsack capacity
 Create a function that returns maximum of two integers.
 Create a function which returns the maximum value that can be put in a
knapsack of capacity W
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
for i = 0 to n
for wt = 0 to W
if (i == 0 or wt == 0) Do K[i][wt] = 0
else if (w[i - 1] <= wt)
Compute: K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i -1][wt])
Else K[i][wt] = K[i - 1][wt]
return K[n][W]
 Call the function and print.
 End of function of 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)
{
int i, w;
vector<vector<int> > K(n + 1, vector<int>(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];
}

// Driver Code
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);

cout << knapSack(W, weight, profit, n);

return 0;
}

Output:
220
Program 3
Find the Minimum Cost Spanning Tree of a given undirected graph using
Prim’s algorithm.
Algorithm
 Determine an arbitrary vertex as the starting vertex of the MST.
 Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
 Find edges connecting any tree vertex with the fringe vertices.
 Find the minimum among these edges.
 Add the chosen edge to the MST if it does not form any cycle.
 Return the MST and exit

Code :
#include <bits/stdc++.h>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(int parent[], int graph[V][V])
{
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
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);
}
// Driver's code
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 } };
// Print the solution
primMST(graph);
return 0;
}

Output :
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
Program 4
C++ code to implement N Queen's problem using Back Tracking.
Algorithm:
while there are untried configurations
{ generate the next configuration
if queens don't attack in this configuration then
{ print this configuration; }
}

Code:

#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++)
if(board[i][j])
cout << "Q ";
else cout<<". ";
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)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
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()
{
solveNQ();
return 0;
}

Output:
..Q.
Q...
...Q
..Q.
Program 5
C++ code to print BFS traversal.
Algorithm:
 Choose a starting vertex, mark it as visited, and add it to a queue.
 While the queue is not empty:
 Dequeue a vertex from the queue and process it (e.g., print its value).
 Enqueue all its adjacent vertices that have not been visited and mark them
as visited.
 Repeat step 2 until the queue is empty.

Code:
#include <bits/stdc++.h>
using namespace std;
class Graph {
int V;
vector<list<int> > adj;
public:
Graph(int V);
void addEdge(int v, int w);
void BFS(int s);
};
Graph: :Graph(int V)
{
this->V = V;
adj.resize(V);
}
void Graph: :addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::BFS(int s)
{
vector<bool> visited;
visited.resize(V, false);
list<int> queue;
visited[s] = true;
queue.push_back(s);
while (!queue.empty()) {
s = queue.front();
cout << s << " ";
queue.pop_front();
for (auto adjacent : adj[s]) {
if (!visited[adjacent]) {
visited[adjacent] = true;
queue.push_back(adjacent);
}
}
}
}
// Driver code
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) \n";
g.BFS(2);
return 0;
}

Output:

Following is Breadth First Traversal (starting from vertex 2)


2031

You might also like