Experiment Title
1: Implementation of Quick Sort Algorithm
#include <iostream>
using namespace std;
// Function to swap two elements
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // choosing last element as pivot
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
swap(arr[i + 1], arr[high]);
return (i + 1);
1
// QuickSort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // partition index
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
// Function to print array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
// Main function
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
quickSort(arr, 0, n - 1);
2
cout << "Sorted array: ";
printArray(arr, n);
return 0;
🔹 Output
Original array: 10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10
2: Implementation of Merge Sort Algorithm
#include <iostream>
3
using namespace std;
// Function to merge two halves
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // size of left subarray
int n2 = right - mid; // size of right subarray
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temp arrays back into arr[left..right]
int i = 0; // Initial index of left subarray
int j = 0; // Initial index of right subarray
int k = left; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
4
j++;
k++;
// Copy the remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
// Copy the remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
// MergeSort function
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort both halves
mergeSort(arr, left, mid);
5
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
// Function to print array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
// Main function
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
mergeSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
6
return 0;
🔹 Output
Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
3: Implementation of DFS and BFS Algorithms for a Graph
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
7
int V; // Number of vertices
list<int>* adj; // Adjacency list
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
void BFS(int start); // Breadth First Search
void DFS(int start); // Depth First Search
private:
void DFSUtil(int v, bool visited[]); // Recursive helper for DFS
};
// Constructor
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
// Add an edge to the graph
void Graph::addEdge(int v, int w) {
adj[v].push_back(w); // Directed graph
adj[w].push_back(v); // For undirected, add reverse edge
// BFS Implementation
void Graph::BFS(int start) {
8
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
queue<int> q;
visited[start] = true;
[Link](start);
cout << "BFS Traversal starting from vertex " << start << ": ";
while (![Link]()) {
int v = [Link]();
cout << v << " ";
[Link]();
for (auto i : adj[v]) {
if (!visited[i]) {
visited[i] = true;
[Link](i);
cout << endl;
// DFS helper function (recursive)
9
void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (auto i : adj[v]) {
if (!visited[i])
DFSUtil(i, visited);
// DFS Implementation
void Graph::DFS(int start) {
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
cout << "DFS Traversal starting from vertex " << start << ": ";
DFSUtil(start, visited);
cout << endl;
// Main function
int main() {
Graph g(5);
// Adding edges
[Link](0, 1);
10
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 4);
[Link](0); // Perform BFS
[Link](0); // Perform DFS
return 0;
🔹 Output
BFS Traversal starting from vertex 0: 0 1 2 3 4
DFS Traversal starting from vertex 0: 0 1 3 4 2
4: Implementation of N-Queens Problem using Backtracking
#include <iostream>
using namespace std;
#define N 8 // You can change this value to any N
// Function to print the chessboard
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
11
for (int j = 0; j < N; j++)
cout << (board[i][j] ? "Q " : ". ");
cout << endl;
// Function to check if a queen can be placed at board[row][col]
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check this column on the upper side
for (i = 0; i < row; i++)
if (board[i][col])
return false;
// Check upper left diagonal
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
// Check upper right diagonal
for (i = row, j = col; i >= 0 && j < N; i--, j++)
if (board[i][j])
return false;
return true;
12
// Recursive utility function to solve N-Queens
bool solveNQueensUtil(int board[N][N], int row) {
// Base case: If all queens are placed
if (row >= N)
return true;
// Try placing this queen in all columns
for (int col = 0; col < N; col++) {
if (isSafe(board, row, col)) {
board[row][col] = 1; // Place queen
// Recurse to place the rest
if (solveNQueensUtil(board, row + 1))
return true;
// Backtrack if placing queen leads to no solution
board[row][col] = 0;
return false; // If no place is safe
// Function to solve N-Queens problem
bool solveNQueens() {
int board[N][N] = {0};
13
if (!solveNQueensUtil(board, 0)) {
cout << "No solution exists" << endl;
return false;
printSolution(board);
return true;
// Main function
int main() {
solveNQueens();
return 0;
🔹 Output Example (for N = 8)
.Q......
...Q....
.....Q..
Q.......
..Q.....
....Q...
......Q.
..Q.....
14
5: Implementation of Sum of Subsets Problem using Backtracking
6 Implementation of Hamiltonian Circuit using Backtracking
7: Implementation of Job Sequencing with Deadlines using Greedy
Algorithm
8: Implementation of Dijkstra’s Algorithm (Single Source Shortest
Path)
9: Implementation of Prim’s Algorithm (Minimum Cost Spanning
Tree)
10: Implementation of Kruskal’s Algorithm (Minimum Cost Spanning
Tree)
11: Implementation of 0/1 Knapsack Problem using Dynamic
Programming
12: Implementation of Binary Search using Divide and Conquer
13: Implementation of Fractional Knapsack Problem using Greedy
Approach
15
14: Implementation of Traveling Salesman Problem (TSP) using
Dynamic Programming
15: Implementation of Subset Sum Problem using Dynamic
Programming
16