Design and analysis of
algorithms
Practical file
Submitted to : Dr. Manisha bansal
Submitted by : pooja soni
Roll no. 22/CS/48
Course : B.Sc.(H) computer science
Question 1) write a program to sort the elements of an
array using insertion sort(the program should report the
number of comparisons ).
#include <iostream>
void insertionSort(int arr[], int n, int& comparisons) {
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position
ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
++comparisons; // Increment the comparison count
arr[j + 1] = key;
int main() {
int n;
std::cout << "Enter the number of elements: ";
std::cin >> n;
int arr[n];
std::cout << "Enter the elements: ";
for (int i = 0; i < n; ++i)
std::cin >> arr[i];
int comparisons = 0; // Variable to count comparisons
insertionSort(arr, n, comparisons);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << "\nNumber of comparisons: " << comparisons << std::endl;
return 0;
Output :
Enter the number of elements: 5
Enter the elements: 12 11 13 5 6
Sorted array: 5 6 11 12 13
Number of comparisons: 7
Question 2) write a program to sort the elements of an
array using merge sort(the program should report the
number of comparisons ).
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int l, int m, int r, int&
comparisons) {
int n1 = m - l + 1;
int n2 = r - m;
std::vector<int> L(n1);
std::vector<int> R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
comparisons++; // Increment comparison count
k++;
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
// Merge sort function
void mergeSort(std::vector<int>& arr, int l, int r, int& comparisons)
{
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m, comparisons);
mergeSort(arr, m + 1, r, comparisons);
merge(arr, l, m, r, comparisons);
int main() {
int n;
std::cout << "Enter the number of elements: ";
std::cin >> n;
std::vector<int> arr(n);
std::cout << "Enter the elements: ";
for (int i = 0; i < n; ++i)
std::cin >> arr[i];
int comparisons = 0; // Variable to count comparisons
mergeSort(arr, 0, n - 1, comparisons);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << "\nNumber of comparisons: " << comparisons <<
std::endl;
return 0;
Output :
Enter the number of elements: 5
Enter the elements: 12 11 13 5 6
Sorted array: 5 6 11 12 13
Number of comparisons: 7
Question 3) write a program to sort the elements of an
array using heap sort(the program should report the
number of comparisons ).
#include <iostream>
#include <vector>
// Function to heapify a subtree rooted with node i
void heapify(std::vector<int>& arr, int n, int i, int& comparisons) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
// If largest is not root
if (largest != i) {
std::swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest, comparisons);
comparisons++; // Increment comparison count
// Function to perform heap sort
void heapSort(std::vector<int>& arr, int& comparisons) {
int n = arr.size();
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i, comparisons);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
std::swap(arr[0], arr[i]);
// Call max heapify on the reduced heap
heapify(arr, i, 0, comparisons);
}
int main() {
int n;
std::cout << "Enter the number of elements: ";
std::cin >> n;
std::vector<int> arr(n);
std::cout << "Enter the elements: ";
for (int i = 0; i < n; ++i)
std::cin >> arr[i];
int comparisons = 0; // Variable to count comparisons
heapSort(arr, comparisons);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << "\nNumber of comparisons: " << comparisons << std::endl;
return 0;
Output :
Enter the number of elements: 5
Enter the elements: 12 11 13 5 6
Sorted array: 5 6 11 12 13
Number of comparisons: 8
Question 4) write a program to sort the elements of an
array using quick sort(the program should report the
number of comparisons ).
#include <iostream>
#include <vector>
// Function to partition the array and return the pivot index
int partition(std::vector<int>& arr, int low, int high, int& comparisons) {
int pivot = arr[high]; // Pivot element
int i = low - 1; // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
std::swap(arr[i], arr[j]);
comparisons++; // Increment comparison count
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
// Function to perform quick sort
void quickSort(std::vector<int>& arr, int low, int high, int& comparisons) {
if (low < high) {
// Partitioning index
int pi = partition(arr, low, high, comparisons);
// Recursively sort elements before partition and after partition
quickSort(arr, low, pi - 1, comparisons);
quickSort(arr, pi + 1, high, comparisons);
int main() {
int n;
std::cout << "Enter the number of elements: ";
std::cin >> n;
std::vector<int> arr(n);
std::cout << "Enter the elements: ";
for (int i = 0; i < n; ++i)
std::cin >> arr[i];
int comparisons = 0; // Variable to count comparisons
quickSort(arr, 0, n - 1, comparisons);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << "\nNumber of comparisons: " << comparisons << std::endl;
return 0;
Output:
Enter the number of elements: 5
Enter the elements: 12 11 13 5 6
Sorted array: 5 6 11 12 13
Number of comparisons: 7
Question 5) write a program to multiply two matrices
using the stranssen’s algorithm for matrix multiplication.
#include <iostream>
#include <vector>
using namespace std;
// Function to add two matrices
vector<vector<int>> matrixAdd(const vector<vector<int>>& A, const
vector<vector<int>>& B) {
int n = A.size();
vector<vector<int>> C(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
C[i][j] = A[i][j] + B[i][j];
return C;
// Function to subtract two matrices
vector<vector<int>> matrixSubtract(const vector<vector<int>>& A, const
vector<vector<int>>& B) {
int n = A.size();
vector<vector<int>> C(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
C[i][j] = A[i][j] - B[i][j];
return C;
// Function to multiply two matrices using Strassen's algorithm
vector<vector<int>> strassenMultiply(const vector<vector<int>>& A,
const vector<vector<int>>& B) {
int n = A.size();
vector<vector<int>> C(n, vector<int>(n));
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
} else {
int newSize = n / 2;
vector<vector<int>> A11(newSize, vector<int>(newSize));
vector<vector<int>> A12(newSize, vector<int>(newSize));
vector<vector<int>> A21(newSize, vector<int>(newSize));
vector<vector<int>> A22(newSize, vector<int>(newSize));
vector<vector<int>> B11(newSize, vector<int>(newSize));
vector<vector<int>> B12(newSize, vector<int>(newSize));
vector<vector<int>> B21(newSize, vector<int>(newSize));
vector<vector<int>> B22(newSize, vector<int>(newSize));
// Divide matrices A and B into submatrices
for (int i = 0; i < newSize; ++i) {
for (int j = 0; j < newSize; ++j) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newSize];
A21[i][j] = A[i + newSize][j];
A22[i][j] = A[i + newSize][j + newSize];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newSize];
B21[i][j] = B[i + newSize][j];
B22[i][j] = B[i + newSize][j + newSize];
// Strassen's recursive calls
vector<vector<int>> M1 = strassenMultiply(matrixAdd(A11, A22),
matrixAdd(B11, B22));
vector<vector<int>> M2 = strassenMultiply(matrixAdd(A21, A22),
B11);
vector<vector<int>> M3 = strassenMultiply(A11, matrixSubtract(B12,
B22));
vector<vector<int>> M4 = strassenMultiply(A22, matrixSubtract(B21,
B11));
vector<vector<int>> M5 = strassenMultiply(matrixAdd(A11, A12),
B22);
vector<vector<int>> M6 = strassenMultiply(matrixSubtract(A21, A11),
matrixAdd(B11, B12));
vector<vector<int>> M7 = strassenMultiply(matrixSubtract(A12, A22),
matrixAdd(B21, B22));
// Calculate result matrices
vector<vector<int>> C11 = matrixAdd(matrixSubtract(matrixAdd(M1,
M4), M5), M7);
vector<vector<int>> C12 = matrixAdd(M3, M5);
vector<vector<int>> C21 = matrixAdd(M2, M4);
vector<vector<int>> C22 = matrixAdd(matrixAdd(matrixSubtract(M1,
M2), M3), M6);
// Combine result matrices into one
for (int i = 0; i < newSize; ++i) {
for (int j = 0; j < newSize; ++j) {
C[i][j] = C11[i][j];
C[i][j + newSize] = C12[i][j];
C[i + newSize][j] = C21[i][j];
C[i + newSize][j + newSize] = C22[i][j];
return C;
int main() {
int n;
cout << "Enter the size of matrices: ";
cin >> n;
vector<vector<int>> A(n, vector<int>(n));
cout << "Enter matrix A elements:\n";
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> A[i][j];
vector<vector<int>> B(n, vector<int>(n));
cout << "Enter matrix B elements:\n";
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> B[i][j];
vector<vector<int>> C = strassenMultiply(A, B);
cout << "Matrix A:\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cout << A[i][j] << " ";
cout << endl;
cout << "Matrix B:\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cout << B[i][j] << " ";
cout << endl;
cout << "Matrix C (Result of A * B):\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << C[i][j] << " ";
}
cout << endl;
return 0;
Output :
Enter the size of matrices: 2
Enter matrix A elements:
12
34
Enter matrix B elements:
56
78
Matrix A:
12
34
Matrix B:
56
78
Matrix C (Result of A * B):
19 22
43 50
Question 6) write a program to sort the elements of an
array using count sort.
#include <iostream>
#include <vector>
using namespace std;
void countSort(vector<int>& arr) {
int maxElement = *max_element(arr.begin(), arr.end());
// Create a count array to store count of individual elements
vector<int> count(maxElement + 1, 0);
// Store count of each element
for (int i = 0; i < arr.size(); ++i)
count[arr[i]]++;
// Modify the count array to store the sum of previous counts
for (int i = 1; i <= maxElement; ++i)
count[i] += count[i - 1];
// Output array
vector<int> output(arr.size());
// Build the output array
for (int i = arr.size() - 1; i >= 0; --i) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
// Copy the sorted elements into the original array
for (int i = 0; i < arr.size(); ++i)
arr[i] = output[i];
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements: ";
for (int i = 0; i < n; ++i)
cin >> arr[i];
countSort(arr);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;
return 0;
Output :
Enter the number of elements: 7
Enter the elements: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8
Question 7) display the data stored in a given graph using
breadth- first search algorithm.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// Function to perform breadth-first search on a graph
void BFS(const vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " "; // Output current vertex
// Traverse all adjacent vertices of current vertex
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
int main() {
int numVertices, numEdges;
cout << "Enter the number of vertices: ";
cin >> numVertices;
cout << "Enter the number of edges: ";
cin >> numEdges;
// Initialize adjacency list
vector<vector<int>> graph(numVertices);
// Input edges
cout << "Enter the edges (vertex pairs):\n";
for (int i = 0; i < numEdges; ++i) {
int u, v;
cin >> u >> v;
// Add edges to the adjacency list (assuming undirected graph)
graph[u].push_back(v);
graph[v].push_back(u);
int startVertex;
cout << "Enter the starting vertex for BFS: ";
cin >> startVertex;
cout << "BFS traversal starting from vertex " << startVertex << ": ";
BFS(graph, startVertex);
return 0;
Output :
Enter the number of vertices: 6
Enter the number of edges: 7
Enter the edges (vertex pairs):
01
02
13
14
24
35
45
Enter the starting vertex for BFS: 0
BFS traversal starting from vertex 0: 0 1 2 3 4 5
Question 8) display the data stored in a given graph using
depth- first search algorithm.
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
// Function to perform depth-first search on a graph
void DFS(const vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<bool> visited(n, false);
stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int current = stk.top();
stk.pop();
if (!visited[current]) {
cout << current << " ";
visited[current] = true;
// Push unvisited adjacent vertices onto the stack
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
stk.push(neighbor);
int main() {
// Example graph represented using an adjacency list
vector<vector<int>> graph = {
{1, 2}, // Vertex 0 is connected to vertices 1 and 2
{0, 3, 4}, // Vertex 1 is connected to vertices 0, 3, and 4
{0, 5}, // Vertex 2 is connected to vertices 0 and 5
{1}, // Vertex 3 is connected to vertex 1
{1}, // Vertex 4 is connected to vertex 1
{2} // Vertex 5 is connected to vertex 2
};
cout << "DFS traversal starting from vertex 0: ";
DFS(graph, 0); // Start DFS traversal from vertex 0
return 0;
Output :
DFS traversal starting from vertex 0: 0 2 5 1 4 3
Question 9) write a program to determine a minimum
spanning tree of a graph using the prim’s algorithm .
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to find the vertex with minimum key value, from the set of
vertices not yet included in MST
int minKey(const vector<int>& key, const vector<bool>& mstSet, int V) {
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;
// Function to print the constructed MST stored in parent array
void printMST(const vector<int>& parent, const vector<vector<int>>&
graph, int V) {
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
// Function to construct and print MST for a graph represented using
adjacency matrix representation
void primMST(const vector<vector<int>>& graph, int V) {
vector<int> parent(V); // Array to store constructed MST
vector<int> key(V); // Key values used to pick minimum weight edge in
cut
vector<bool> mstSet(V, false); // To represent set of vertices included in
MST
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
// Always include first vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet included
in MST
int u = minKey(key, mstSet, V);
// Add the picked vertex to the MST set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of the
picked vertex
// Consider only those vertices which are not yet included in MST
for (int v = 0; v < V; v++) {
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
// Print the constructed MST
printMST(parent, graph, V);
int main() {
// Example graph represented using adjacency matrix
vector<vector<int>> graph = {
{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, 5);
return 0;
Output :
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
Question 10) write a program to solve the 0-1 knapsack
problem .
#include <iostream>
#include <vector>
using namespace std;
// Function to solve the 0-1 knapsack problem
int knapsack(int W, const vector<int>& wt, const vector<int>& val, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] <= w) {
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
return dp[n][W];
int main() {
int n; // Number of items
cout << "Enter the number of items: ";
cin >> n;
vector<int> val(n); // Values of the items
vector<int> wt(n); // Weights of the items
cout << "Enter the values of the items:\n";
for (int i = 0; i < n; i++) {
cin >> val[i];
cout << "Enter the weights of the items:\n";
for (int i = 0; i < n; i++) {
cin >> wt[i];
}
int W; // Capacity of the knapsack
cout << "Enter the capacity of the knapsack: ";
cin >> W;
int maxValue = knapsack(W, wt, val, n);
cout << "Maximum value that can be obtained: " << maxValue << endl;
return 0;
Output :
Enter the number of items: 3
Enter the values of the items:
60 100 120
Enter the weights of the items:
10 20 30
Enter the capacity of the knapsack: 50
Maximum value that can be obtained: 220
