EXPERIMENT-1

AIM: WAP to reverse an array by swapping without using additional memory.

CODE:

#include <iostream>

using namespace std;

void reverseArray(int arr[], int size) {

int start = 0;

int end = size - 1;

while (start < end) {

swap(arr[start], arr[end]);

start++;

end--;

void printArray(int arr[], int size) {

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

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

cout << endl;

int main() {

int arr[] = {1, 2, 3, 4, 5};

int size = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";

printArray(arr, size);

reverseArray(arr, size);

cout << "Reversed array: ";

printArray(arr, size);

return 0;

}
OUTPUT:

EXPERIMENT-2

AIM: WAP to find the number of Non Repeated elements in an Array

CODE:

#include <iostream>

#include <unordered_map>

using namespace std;

int countNonRepeated(int arr[], int size) {

unordered_map<int, int> frequency;

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

frequency[arr[i]]++;

int nonRepeatedCount = 0;

for (auto& pair : frequency) {

if (pair.second == 1) {

nonRepeatedCount++;

return nonRepeatedCount;

int main() {

int arr[] = {1, 2, 3, 2, 1, 4, 5, 6, 5};

int size = sizeof(arr) / sizeof(arr[0]);

int nonRepeatedCount = countNonRepeated(arr, size);

cout << "Number of non-repeated elements: " << nonRepeatedCount << endl;
return 0;

OUTPUT:

EXPERIMENT-3

AIM: WAP with function to swap two numbers using call by reference.

CODE:

#include <iostream>

using namespace std;

void swap(int& a, int& b) {

int temp = a;

a = b;

b = temp;

int main() {

int x = 5;

int y = 10;

cout << "Before swapping: x = " << x << ", y = " << y << endl;

swap(x, y);

cout << "After swapping: x = " << x << ", y = " << y << endl;

return 0;

OUTPUT:
EXPERIMENT-4

AIM: WAP to identify the missing numbers in a given Array within the range [1...N].

CODE:

#include <iostream>

#include <vector>

using namespace std;

void findMissingNumbers(int arr[], int size, int N) {

vector<bool> present(N + 1, false);

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

if (arr[i] >= 1 && arr[i] <= N) {

present[arr[i]] = true;

cout << "Missing numbers: ";

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

if (!present[i]) {

cout << i << " ";

cout << endl;

int main() {
int arr[] = {3, 7, 1, 2, 8, 4, 5};

int size = sizeof(arr) / sizeof(arr[0]);

int N = 8; // The range is from 1 to N

findMissingNumbers(arr, size, N);

return 0;

OUTPUT:

EXPERIMENT-5

AIM: Write a function that accepts as input a string and determines the frequency of
occurences of each of the distinct characters in string. Test your function using suitable data.

CODE:

#include <iostream>

#include <unordered_map>

using namespace std;

void characterFrequency(const string& str) {

unordered_map<char, int> frequency;

for (char ch : str) {

frequency[ch]++;

cout << "Character frequencies:\n";

for (const auto& pair : frequency) {

cout << "'" << pair.first << "' : " << pair.second << endl;

int main() {
string input = "hello world";

characterFrequency(input);

return 0;

OUTPUT:

EXPERIMENT-6

AIM: WAP to find the Median of the elements after merging the two sorted Arrays of same size.

CODE:

#include <iostream>

#include <vector>

using namespace std;

double findMedianSortedArrays(int arr1[], int arr2[], int size) {

vector<int> merged(2 * size);

int i = 0, j = 0, k = 0;

while (i < size && j < size) {

if (arr1[i] < arr2[j]) {

merged[k++] = arr1[i++];

} else {

merged[k++] = arr2[j++];

}
while (i < size) {

merged[k++] = arr1[i++];

while (j < size) {

merged[k++] = arr2[j++];

double median;

if (merged.size() % 2 == 0) {

median = (merged[size - 1] + merged[size]) / 2.0;

} else {

median = merged[merged.size() / 2];

return median;

int main() {

int arr1[] = {1, 3, 8};

int arr2[] = {7, 9, 10};

int size = sizeof(arr1) / sizeof(arr1[0]);

double median = findMedianSortedArrays(arr1, arr2, size);

cout << "Median of the merged arrays: " << median << endl;

return 0;

OUTPUT:

EXPERIMENT-7
AIM: WAP to Create a new file, Open an existing file, read the file to search a given word, write
into the file and close the file.

CODE:

#include <iostream>

#include <fstream>

#include <string>

using namespace std;

void createFile(const string& filename) {

ofstream outFile(filename);

if (outFile.is_open()) {

outFile << "This is a sample file.\n";

outFile << "It contains some sample text for testing.\n";

outFile << "Feel free to add more text.\n";

outFile.close();

void searchWordInFile(const string& filename, const string& word) {

ifstream inFile(filename);

string line;

bool found = false;

if (inFile.is_open()) {

while (getline(inFile, line)) {

if (line.find(word) != string::npos) {

cout << "Word '" << word << "' found in line: " << line << endl;

found = true;

inFile.close();
if (!found) {

cout << "Word '" << word << "' not found in the file.\n";

void writeToFile(const string& filename, const string& text) {

ofstream outFile(filename, ios::app);

if (outFile.is_open()) {

outFile << text << endl;

outFile.close();

int main() {

string filename = "sample.txt";

createFile(filename);

string wordToSearch = "sample";

searchWordInFile(filename, wordToSearch);

string textToWrite = "This is additional text added to the file.";

writeToFile(filename, textToWrite);

searchWordInFile(filename, "additional");

return 0;

OUTPUT:

EXPERIMENT-8
AIM: WAP to implement Dequeue using Arrays with all the basic operations.

CODE:

#include <iostream>

using namespace std;

class Dequeue {

int* arr;

int front;

int rear;

int capacity;

public:

Dequeue(int size) {

arr = new int[size];

capacity = size;

front = -1;

rear = 0;

~Dequeue() {

delete[] arr;

void insertFront(int key) {

if (isFull()) {

cout << "Overflow: Dequeue is full\n";

return;

front = (front + 1) % capacity;

arr[front] = key;

if (rear == 0) rear = front;

}

void insertRear(int key) {

if (isFull()) {

cout << "Overflow: Dequeue is full\n";

return;

rear = (rear - 1 + capacity) % capacity;

arr[rear] = key;

if (front == -1) front = rear;

void deleteFront() {

if (isEmpty()) {

cout << "Underflow: Dequeue is empty\n";

return;

front = (front - 1 + capacity) % capacity;

if (front == rear) {

front = -1;

rear = 0;

void deleteRear() {

if (isEmpty()) {

cout << "Underflow: Dequeue is empty\n";

return;

rear = (rear + 1) % capacity;

if (front == rear) {
front = -1;

rear = 0;

int getFront() {

if (isEmpty()) {

cout << "Dequeue is empty\n";

return -1;

return arr[front];

int getRear() {

if (isEmpty() || rear == 0) {

cout << "Dequeue is empty\n";

return -1;

return arr[(rear - 1 + capacity) % capacity];

bool isFull() {

return ((front + 1) % capacity == rear);

bool isEmpty() {

return front == -1;

void display() {

if (isEmpty()) {
cout << "Dequeue is empty\n";

return;

cout << "Dequeue elements: ";

for (int i = rear; i != front; i = (i + 1) % capacity) {

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

cout << arr[front] << endl;

};

int main() {

Dequeue dq(5);

dq.insertRear(10);

dq.insertRear(20);

dq.insertFront(30);

dq.insertFront(40);

dq.display();

cout << "Front element: " << dq.getFront() << endl;

cout << "Rear element: " << dq.getRear() << endl;

dq.deleteRear();

dq.display();

dq.deleteFront();

dq.display();

return 0;

OUTPUT:
EXPERIMENT-9

AIM: WAP to implement Merge Sort on 1D array of Student structures (contains student_name,
student_roll_no, total_marks) with key as student_roll_no.

CODE:

#include <iostream>

#include <string>

using namespace std;

struct Student {

string student_name;

int student_roll_no;

float total_marks;

};

void merge(Student arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

Student* L = new Student[n1];

Student* R = new Student[n2];

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

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i].student_roll_no <= R[j].student_roll_no) {

arr[k++] = L[i++];

} else {

arr[k++] = R[j++];

while (i < n1)

arr[k++] = L[i++];

while (j < n2)

arr[k++] = R[j++];

delete[] L;

delete[] R;

void mergeSort(Student arr[], int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

void printStudents(Student arr[], int size) {

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

cout << "Name: " << arr[i].student_name

<< ", Roll No: " << arr[i].student_roll_no

<< ", Total Marks: " << arr[i].total_marks << endl;

}

int main() {

Student students[] = {

{"Alice", 3, 85.5},

{"Bob", 1, 90.0},

{"Charlie", 2, 75.0},

{"David", 5, 95.5},

{"Eve", 4, 80.0}

};

int size = sizeof(students) / sizeof(students[0]);

cout << "Students before sorting:\n";

printStudents(students, size);

mergeSort(students, 0, size - 1);

cout << "\nStudents after sorting by roll number:\n";

printStudents(students, size);

return 0;

OUTPUT:

EXPERIMENT - 10

AIM: WAP to implement Linear search and Binary search on 1D array of Integers.
CODE :

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int linearSearch(const vector<int>& arr, int target) {

for (int i = 0; i < arr.size(); i++) {

if (arr[i] == target) {

return i; // Return the index of the found element

return -1; // Return -1 if the element is not found

int binarySearch(const vector<int>& arr, int target) {

int low = 0;

int high = arr.size() - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == target) {

return mid; // Return the index of the found element

else if (arr[mid] < target) {

low = mid + 1;

else {

high = mid - 1;

}
return -1; // Return -1 if the element is not found

int main() {

vector<int> arr = {3, 6, 8, 12, 14, 17, 20, 25, 28, 30};

int target = 17;

int resultLinear = linearSearch(arr, target);

if (resultLinear != -1)

cout << "Linear Search: Element " << target << " found at index " << resultLinear << endl;

else

cout << "Linear Search: Element not found" << endl;

int resultBinary = binarySearch(arr, target);

if (resultBinary != -1)

cout << "Binary Search: Element " << target << " found at index " << resultBinary << endl;

else

cout << "Binary Search: Element not found" << endl;

return 0;

OUTPUT :

EXPERIMENT – 11

AIM: WAP to implement Insertion and Selection sort on 1D array of strings.

CODE :

#include <vector>

#include <string>

using namespace std;

// Insertion Sort function

void insertionSort(vector<string>& arr) {

int n = arr.size();

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

string key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j--;

arr[j + 1] = key;

void selectionSort(vector<string>& arr) {

int n = arr.size();

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

int minIndex = i;

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

if (arr[j] < arr[minIndex]) {

minIndex = j;

swap(arr[i], arr[minIndex]);
}

void printArray(const vector<string>& arr) {

for (const string& s : arr) {

cout << s << " ";

cout << endl;

int main() {

vector<string> arr = {"banana", "apple", "cherry", "mango", "orange"};

cout << "c:\\saksham dsa lab\\" << endl;

vector<string> arr1 = arr; // Copy of the original array

insertionSort(arr1);

cout << "Insertion Sort: ";

printArray(arr1);

vector<string> arr2 = arr; // Another copy of the original array

selectionSort(arr2);

cout << "Selection Sort: ";

printArray(arr2);

return 0;

OUTPUT :

EXPERIMENT-12

AIM: WAP to implement Quick sort on 1D array of characters.

CODE:
#include <iostream>

#include <vector>

using namespace std;

int partition(vector<char>& arr, int low, int high) {

char pivot = arr[high];

int i = low - 1;

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;

void quickSort(vector<char>& arr, int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1); // Sort elements before partition

quickSort(arr, pi + 1, high); // Sort elements after partition

void printArray(const vector<char>& arr) {

for (char c : arr) {

cout << c << " ";

cout << endl;

int main() {

vector<char> arr = {'d', 'a', 'c', 'b', 'e'};

cout << "c:\\saksham dsa lab\\" << endl;

quickSort(arr, 0, arr.size() - 1);

cout << "Sorted array: ";

printArray(arr);

return 0;

OUTPUT:

EXPERIMENT-13

AIM: WAP to store and display a Lower-Right triangular matrix in RMO and CMO fashion.

CODE:

#include <iostream>

using namespace std;

void displayRMO(int* arr, int n) {

cout << "Row-Major Order:" << endl;

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

for (int j = 0; j < n; ++j) {

if (j >= i)

cout << arr[(i * (2 * n - i + 1)) / 2 + j - i] << " ";

else

cout << "0 ";

cout << endl;

}
void displayCMO(int* arr, int n) {

cout << "Column-Major Order:" << endl;

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

for (int j = 0; j < n; ++j) {

if (j >= i)

cout << arr[(j * (j + 1)) / 2 + i] << " ";

else

cout << "0 ";

cout << endl;

int main() {

int n;

cout << "Enter the size of matrix: ";

cin >> n;

int size = (n * (n + 1)) / 2;

int* arr = new int[size];

cout << "Enter the elements for the lower-right triangular matrix:" << endl;

for (int i = 0; i < size; ++i)

cin >> arr[i];

cout << endl;

displayRMO(arr, n);

cout << endl;

displayCMO(arr, n);

delete[] arr;

return 0;

OUTPUT :
EXPERIMENT – 14

AIM: WAP to store and display a Lower-Left triangular matrix in RMO and CMO fashion.

CODE:

#include <iostream>

using namespace std;

void displayRMO(int* arr, int n) {

cout << "Row-Major Order:" << endl;

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

for (int j = 0; j < n; ++j) {

if (j <= i)

cout << arr[(i * (i + 1)) / 2 + j] << " ";

else

cout << "0 ";

cout << endl;

}

void displayCMO(int* arr, int n) {

cout << "Column-Major Order:" << endl;

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

for (int j = 0; j < n; ++j) {

if (j <= i)

cout << arr[(j * (2 * n - j + 1)) / 2 - (n - i)] << " ";

else

cout << "0 ";

cout << endl;

int main() {

int n;

cout << "Enter the size of matrix: ";

cin >> n;

int size = (n * (n + 1)) / 2;

int* arr = new int[size];

cout << "Enter the elements for the upper-left triangular matrix:" << endl;

for (int i = 0; i < size; ++i)

cin >> arr[i];

cout << endl;

displayRMO(arr, n);

cout << endl;

displayCMO(arr, n);

delete[] arr;

return 0;
}

OUTPUT :

EXPERIMENT-15

AIM : WAP to store and display an Upper-Left triangular matrix in RMO and CMO fashion

CODE:

#include <iostream>

using namespace std;

void displayRMO(int* arr, int n) {

cout << "Row-Major Order:" << endl;

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

for (int j = 0; j < n; ++j) {

if (j <= i)

cout << arr[(i * (i + 1)) / 2 + j] << " ";

else

cout << "0 ";

}

cout << endl;

void displayCMO(int* arr, int n) {

cout << "Column-Major Order:" << endl;

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

for (int j = 0; j < n; ++j) {

if (j <= i)

cout << arr[(j * (2 * n - j - 1)) / 2 + i - j] << " ";

else

cout << "0 ";

cout << endl;

int main() {

int n;

cout << "Enter the size of matrix: ";

cin >> n;

int size = (n * (n + 1)) / 2;

int* arr = new int[size];

cout << "Enter the elements for the upper-left triangular matrix:" << endl;

for (int i = 0; i < size; ++i)

cin >> arr[i];

cout << endl;

displayRMO(arr, n);

cout << endl;

displayCMO(arr, n);
delete[] arr;

return 0;

OUTPUT :

EXPERIMENT-16

AIM: WAP to store and display a Z matrix in RMO and CMO fashion. (Z matrix contains non-zero
elements in first row, last row and right diagonal only.)

CODE:

#include <iostream>

using namespace std;

void displayRMO(int* arr, int n) {

cout << "Row-Major Order:" << endl;

int index = 0;

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

for (int j = 0; j < n; ++j) {

if (i == 0 || i == n - 1 || j == n - 1 - i)

cout << arr[index++] << " ";

else

cout << "0 ";

cout << endl;

void displayCMO(int* arr, int n) {

cout << "Column-Major Order:" << endl;

int index = 0;

for (int j = 0; j < n; ++j) {

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

if (i == 0 || i == n - 1 || j == n - 1 - i)

cout << arr[index++] << " ";

else

cout << "0 ";

cout << endl;

int main() {

int n;

cout << "Enter the size of matrix: ";

cin >> n;

int size = 2 * n - 1;

int* arr = new int[size];

cout << "Enter the elements for the

Z matrix:" << endl;

for (int i = 0; i < size; ++i)

cin >> arr[i];

cout << endl;

displayRMO(arr, n);

cout << endl;

displayCMO(arr, n);

delete[] arr;

return 0;

OUTPUT:

EXPERIMENT-17

AIM: WAP to evaluate a given postfix expression using stack ADT.

CODE:

cpp

Copy code

#include <iostream>

#include <stack>
#include <cctype>

using namespace std;

int evaluatePostfix(const string& expression) {

stack<int> s;

for (char ch : expression) {

if (isdigit(ch))

s.push(ch - '0');

else {

int operand2 = s.top(); s.pop();

int operand1 = s.top(); s.pop();

switch (ch) {

case '+': s.push(operand1 + operand2); break;

case '-': s.push(operand1 - operand2); break;

case '*': s.push(operand1 * operand2); break;

case '/': s.push(operand1 / operand2); break;

return s.top();

int main() {

string expression;

cout << "Enter the postfix expression: ";

cin >> expression;

cout << "Result: " << evaluatePostfix(expression) << endl;

return 0;

OUTPUT:
EXPERIMENT- 18

AIM: WAP to check the given string is palindrome using stack.

CODE:

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int main() {

string str;

cout << "Enter a string: ";

getline(cin, str);

stack<char> s;

// Push all characters of the string onto the stack

for (char c : str) {

if (isalnum(c)) { // Check if the character is alphanumeric

s.push(tolower(c)); // Convert to lowercase and push onto stack

string reversed;

// Pop characters from the stack to form the reversed string

while (!s.empty()) {

reversed += s.top();

s.pop();

// Compare the original string with the reversed string

if (reversed == str) {

cout << "The string is a palindrome." << endl;

} else {

cout << "The string is not a palindrome." << endl;

return 0;

OUTPUT:

EXPERIMENT-19

AIM: WAP to transform infix expression into equivalent postfix expression using stack. Also use
the user defined operators, $,#, etc, with appropiate priorities. Eg. A+(B*C D/E$F)*G)*H, {*,/} > $
> {+,-}

CODE:

#include <iostream>

#include <stack>

#include <string>

#include <cctype>

#include <map>

using namespace std;

int precedence(char op) {

if (op == '$' || op == '#') return 3;

if (op == '*' || op == '/') return 2;

if (op == '+' || op == '-') return 1;

return 0;

bool isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '$' || c == '#';

string infixToPostfix(const string &infix) {

stack<char> s;

string postfix;

for (char c : infix) {

if (isalnum(c)) {

postfix += c;

} else if (c == '(') {

s.push(c);

} else if (c == ')') {

while (!s.empty() && s.top() != '(') {

postfix += s.top();

s.pop();

s.pop();

} else if (isOperator(c)) {

while (!s.empty() && precedence(s.top()) >= precedence(c)) {

postfix += s.top();

s.pop();

s.push(c);
}

while (!s.empty()) {

postfix += s.top();

s.pop();

return postfix;

int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

string infix;

cout << "Enter an infix expression: ";

getline(cin, infix);

string postfix = infixToPostfix(infix);

cout << "Postfix expression: " << postfix << endl;

return 0;

OUTPUT :

EXPERIMENT-20

AIM: WAP wihch gives the solution to the Tower of Hanoi problem for n disks. Test the program
using: a) N=3, b) N=4.

CODE:
#include <iostream>

using namespace std;

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {

if (n == 1) {

cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;

return;

towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;

towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);

int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

int N;

cout << "Enter the number of disks (e.g., N=3 or N=4): ";

cin >> N;

cout << "Solution for Tower of Hanoi with " << N << " disks:\n";

towerOfHanoi(N, 'A', 'C', 'B');

return 0;

OUTPUT:
EXPERIMENT-21

AIM: WAP to solve Maze problem of size mxn.

CODE: #include <iostream>

using namespace std;

#define N 10

bool isSafe(int maze[N][N], int x, int y, int m, int n) {

return (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 1);

bool solveMazeUtil(int maze[N][N], int x, int y, int m, int n, int sol[N][N]) {

if (x == m - 1 && y == n - 1 && maze[x][y] == 1) {

sol[x][y] = 1;

return true;

if (isSafe(maze, x, y, m, n)) {

sol[x][y] = 1;

if (solveMazeUtil(maze, x + 1, y, m, n, sol)) return true;

if (solveMazeUtil(maze, x, y + 1, m, n, sol)) return true;

sol[x][y] = 0;

return false;
}

void printSolution(int sol[N][N], int m, int n) {

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

for (int j = 0; j < n; j++) {

cout << sol[i][j] << " ";

cout << endl;

bool solveMaze(int maze[N][N], int m, int n) {

int sol[N][N] = {0};

if (!solveMazeUtil(maze, 0, 0, m, n, sol)) {

cout << "No solution found." << endl;

return false;

printSolution(sol, m, n);

return true;

int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

int maze[N][N] = {

{1, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{1, 1, 1, 1, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 1, 1, 1, 1, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 1, 1, 1, 0},

{0, 0, 0, 0, 0, 0, 1, 0, 1, 1},

{0, 1, 1, 1, 1, 1, 1, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 1, 1, 1, 1},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 1}
};

int m = 10, n = 10;

solveMaze(maze, m, n);

return 0;

OUTPUT:

EXPERIMENT-22

AIM: WAP to reverse a singly linked list using one auxillary pointer. And try without using any
auxillary pointer.

CODE:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtEnd(Node*& head, int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

return;

Node* temp = head;

while (temp->next) {

temp = temp->next;

temp->next = newNode;

void reverseWithoutAux(Node*& head) {

if (!head || !head->next) return;

Node* prev = nullptr;

while (head->next) {

Node* temp = head->next;

head->next = temp->next;

temp->next = prev ? prev : head;

prev = temp;

head = prev;

void printList(Node* head) {

while (head) {

cout << head->data << " ";

head = head->next;

cout << endl;

}
int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

Node* head = nullptr;

insertAtEnd(head, 1);

insertAtEnd(head, 2);

insertAtEnd(head, 3);

insertAtEnd(head, 4);

cout << "Original List: ";

printList(head);

reverseWithoutAux(head);

cout << "Reversed List (without auxiliary pointer): ";

printList(head);

return 0;

OUTPUT:

EXPERIMENT-23

AIM:

CODE:

#include <iostream>

using namespace std;

struct Node {
int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtEnd(Node*& head, int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

return;

Node* temp = head;

while (temp->next) {

temp = temp->next;

temp->next = newNode;

Node* findSecondLastNode(Node* head) {

if (!head || !head->next) {

cout << "The list is too short to have a second last node." << endl;

return nullptr;

Node* temp = head;

while (temp->next->next) {

temp = temp->next;

return temp;

}
void printList(Node* head) {

while (head) {

cout << head->data << " ";

head = head->next;

cout << endl;

int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

Node* head = nullptr;

insertAtEnd(head, 1);

insertAtEnd(head, 2);

insertAtEnd(head, 3);

insertAtEnd(head, 4);

cout << "Linked List: ";

printList(head);

Node* secondLast = findSecondLastNode(head);

if (secondLast) {

cout << "The second last node is: " << secondLast->data << endl;

return 0;

OUTPUT:

EXPERIMENT-24

AIM: WAP to print alternate nodes from the list.

CODE:

#include <iostream>
using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtEnd(Node*& head, int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

return;

Node* temp = head;

while (temp->next) temp = temp->next;

temp->next = newNode;

void printAlternateNodes(Node* head) {

bool print = true;

while (head) {

if (print) cout << head->data << " ";

print = !print;

head = head->next;

cout << endl;

int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

Node* head = nullptr;

insertAtEnd(head, 1);

insertAtEnd(head, 2);

insertAtEnd(head, 3);

insertAtEnd(head, 4);

insertAtEnd(head, 5);

insertAtEnd(head, 6);

cout << "Alternate nodes: ";

printAlternateNodes(head);

return 0;

OUTPUT:

EXXPERIMENT-25

AIM: WAP to sort singly linked list.

CODE:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtEnd(Node*& head, int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

return;

Node* temp = head;

while (temp->next) temp = temp->next;

temp->next = newNode;

Node* findMiddle(Node* head) {

Node *slow = head, *fast = head->next;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

return slow;

Node* merge(Node* left, Node* right) {

if (!left) return right;

if (!right) return left;

Node* result;

if (left->data <= right->data) {

result = left;

result->next = merge(left->next, right);

} else {

result = right;

result->next = merge(left, right->next);

return result;
}

Node* mergeSort(Node* head) {

if (!head || !head->next) return head;

Node* middle = findMiddle(head);

Node* nextToMiddle = middle->next;

middle->next = nullptr;

Node* left = mergeSort(head);

Node* right = mergeSort(nextToMiddle);

return merge(left, right);

void printList(Node* head) {

while (head) {

cout << head->data << " ";

head = head->next;

cout << endl;

int main() {

cout << "PS C:\\saksham dsa lab> cd \"c:\\saksham dsa lab\\\"\n";

Node* head = nullptr;

insertAtEnd(head, 4);

insertAtEnd(head, 2);

insertAtEnd(head, 1);

insertAtEnd(head, 3);

cout << "Original List: ";

printList(head);
head = mergeSort(head);

cout << "Sorted List: ";

printList(head);

return 0;

OUTPUT:

EXPERIMENT- 26

AIM : WAP to create a Circular Singly Linked List for (a) Inserting a node, before the node with
key givenkey

CODE:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtEnd(Node*& head, int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

newNode->next = head;

return;

Node* temp = head;

while (temp->next != head) temp = temp->next;

temp->next = newNode;

newNode->next = head;

void insertBefore(Node*& head, int key, int data) {

if (!head) return;

Node* newNode = new Node(data);

if (head->data == key) {

Node* temp = head;

while (temp->next != head) temp = temp->next;

temp->next = newNode;

newNode->next = head;

head = newNode;

return;

Node* current = head;

while (current->next != head && current->next->data != key) {

current = current->next;

if (current->next->data == key) {

newNode->next = current->next;

current->next = newNode;

void printList(Node* head) {

if (!head) return;

Node* temp = head;

do {

cout << temp->data << " ";

temp = temp->next;

} while (temp != head);

cout << endl;

int main() {

Node* head = nullptr;

insertAtEnd(head, 1);

insertAtEnd(head, 2);

insertAtEnd(head, 3);

insertAtEnd(head, 4);

cout << "Original Circular List: ";

printList(head);

insertBefore(head, 3, 5);

cout << "List after inserting 5 before 3: ";

printList(head);

return 0;

OUTPUT:

EXPERIMENT-27

AIM: WAP to create a Circular Singly Linked List for Inserting a node, after the node with key
givenkey,

CODE:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

void insertAtEnd(Node*& head, int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

newNode->next = head;

return;

Node* temp = head;

while (temp->next != head) temp = temp->next;

temp->next = newNode;

newNode->next = head;

void insertAfter(Node*& head, int key, int data) {

if (!head) return;

Node* current = head;

do {

if (current->data == key) {

Node* newNode = new Node(data);

newNode->next = current->next;

current->next = newNode;

return;

current = current->next;

} while (current != head);

}

void printList(Node* head) {

if (!head) return;

Node* temp = head;

do {

cout << temp->data << " ";

temp = temp->next;

} while (temp != head);

cout << endl;

int main() {

Node* head = nullptr;

insertAtEnd(head, 1);

insertAtEnd(head, 2);

insertAtEnd(head, 3);

insertAtEnd(head, 4);

cout << "Original Circular List: ";

printList(head);

insertAfter(head, 2, 5);

cout << "List after inserting 5 after 2: ";

printList(head);

return 0;

OUTPUT:
EXPERIMENT-28

AIM: WAP to transform given tree into a binary tree.

CODE:

#include <iostream>

#include <vector>

using namespace std;

struct NaryNode {

int data;

vector<NaryNode*> children;

NaryNode(int val) : data(val) {}

};

struct BinaryTreeNode {

int data;

BinaryTreeNode* left;

BinaryTreeNode* right;

BinaryTreeNode(int val) : data(val), left(nullptr), right(nullptr) {}

};

// Function to convert N-ary Tree to Binary Tree

BinaryTreeNode* convertToBinaryTree(NaryNode* root) {

if (!root) return nullptr;

BinaryTreeNode* newRoot = new BinaryTreeNode(root->data);

if (root->children.empty()) return newRoot;

newRoot->left = convertToBinaryTree(root->children[0]);

BinaryTreeNode* current = newRoot->left;

for (size_t i = 1; i < root->children.size(); i++) {

current->right = convertToBinaryTree(root->children[i]);

current = current->right;
}

return newRoot;

void printBinaryTree(BinaryTreeNode* root) {

if (!root) return;

printBinaryTree(root->left);

cout << root->data << " ";

printBinaryTree(root->right);

int main() {

NaryNode* root = new NaryNode(1);

root->children.push_back(new NaryNode(2));

root->children.push_back(new NaryNode(3));

root->children.push_back(new NaryNode(4));

root->children[0]->children.push_back(new NaryNode(5));

root->children[0]->children.push_back(new NaryNode(6));

BinaryTreeNode* binaryTreeRoot = convertToBinaryTree(root);

cout << "Binary Tree In-Order Traversal: ";

printBinaryTree(binaryTreeRoot);

cout << endl;

return 0;

OUTPUT:

EXPERIMENT-29
AIM: WAP to represent an arithematic expression in binary tree format.

CODE:

#include <iostream>

#include <stack>

#include <string>

using namespace std;

struct TreeNode {

string data;

TreeNode* left;

TreeNode* right;

TreeNode(string val) : data(val), left(nullptr), right(nullptr) {}

};

TreeNode* constructTree(const string& expression) {

stack<TreeNode*> nodes;

for (char ch : expression) {

if (isalnum(ch)) {

nodes.push(new TreeNode(string(1, ch)));

} else {

TreeNode* right = nodes.top(); nodes.pop();

TreeNode* left = nodes.top(); nodes.pop();

TreeNode* operatorNode = new TreeNode(string(1, ch));

operatorNode->left = left;

operatorNode->right = right;

nodes.push(operatorNode);

return nodes.top();

}
void inorderTraversal(TreeNode* root) {

if (!root) return;

inorderTraversal(root->left);

cout << root->data << " ";

inorderTraversal(root->right);

int main() {

string expression = "ab+c*";

TreeNode* root = constructTree(expression);

cout << "In-Order Traversal of the Expression Tree: ";

inorderTraversal(root);

cout << endl;

return 0;

OUTPUT:

EXPERIMENT-30

AIM: WAP to find cut-set of the given graph.

CODE:

#include <iostream>

#include <vector>

using namespace std;

class Graph {

int V;

vector<vector<int>> adj;

void DFS(int u, int parent[], int low[], int disc[], vector<pair<int, int>>& cutEdges);

public:
Graph(int V);

void addEdge(int u, int v);

void findCutEdges();

};

Graph::Graph(int V) {

this->V = V;

adj.resize(V);

void Graph::addEdge(int u, int v) {

adj[u].push_back(v);

adj[v].push_back(u);

void Graph::DFS(int u, int parent[], int low[], int disc[], vector<pair<int, int>>& cutEdges) {

static int time = 0;

disc[u] = low[u] = ++time;

for (int v : adj[u]) {

if (disc[v] == -1) {

parent[v] = u;

DFS(v, parent, low, disc, cutEdges);

low[u] = min(low[u], low[v]);

if (low[v] > disc[u]) {

cutEdges.push_back({u, v});

} else if (v != parent[u]) {

low[u] = min(low[u], disc[v]);

}
}

void Graph::findCutEdges() {

vector<pair<int, int>> cutEdges;

int *disc = new int[V];

int *low = new int[V];

int *parent = new int[V];

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

disc[i] = -1;

low[i] = -1;

parent[i] = -1;

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

if (disc[i] == -1) {

DFS(i, parent, low, disc, cutEdges);

cout << "Cut edges in the graph:\n";

for (auto& edge : cutEdges) {

cout << edge.first << " -- " << edge.second << endl;

delete[] disc;

delete[] low;

delete[] parent;

int main() {

Graph g(5);

g.addEdge(0, 1);

g.addEdge(1, 2);
g.addEdge(1, 3);

g.addEdge(3, 4);

g.addEdge(2, 4);

g.findCutEdges();

return 0;

OUTPUT:

EXPERIMENT-31

AIM: WAP to implement doubly linked list for Inserting a node, before the node with givenkey.

CODE:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* prev;

Node* next;

Node(int val) : data(val), prev(nullptr), next(nullptr) {}

};

class DoublyLinkedList {

private:
Node* head;

public:

DoublyLinkedList() : head(nullptr) {}

void insertAtEnd(int data) {

Node* newNode = new Node(data);

if (!head) {

head = newNode;

return;

Node* temp = head;

while (temp->next) {

temp = temp->next;

temp->next = newNode;

newNode->prev = temp;

void insertBefore(int key, int data) {

if (!head) return;

Node* newNode = new Node(data);

if (head->data == key) {

newNode->next = head;

head->prev = newNode;

head = newNode;

return;

Node* current = head;

while (current && current->data != key) {

current = current->next;
}

if (current) {

newNode->next = current;

newNode->prev = current->prev;

if (current->prev) {

current->prev->next = newNode;

current->prev = newNode;

void printList() {

Node* temp = head;

while (temp) {

cout << temp->data << " ";

temp = temp->next;

cout << endl;

};

int main() {

DoublyLinkedList dll;

dll.insertAtEnd(1);

dll.insertAtEnd(2);

dll.insertAtEnd(3);

dll.insertAtEnd(4);

cout << "Original Doubly Linked List: ";

dll.printList();

dll.insertBefore(3, 5);

cout << "List after inserting 5 before 3: ";

dll.printList();

return 0;

OUTPUT:

EXPERIMENT-32

AIM: WAP to implement doubly linked list of Removing a node with particular key value

CODE:

#include <iostream>

using namespace std;

struct Node {

int data;

Node* prev;

Node* next;

Node(int val) : data(val), prev(nullptr), next(nullptr) {}

};

class DoublyLinkedList {

private:

Node* head;

public:

DoublyLinkedList() : head(nullptr) {}

void insertAtEnd(int data) {

Node* newNode = new Node(data);

if (!head) {
head = newNode;

return;

Node* temp = head;

while (temp->next) {

temp = temp->next;

temp->next = newNode;

newNode->prev = temp;

void removeNode(int key) {

if (!head) return;

Node* current = head;

while (current) {

if (current->data == key) {

if (current->prev) {

current->prev->next = current->next;

} else {

head = current->next;

if (current->next) {

current->next->prev = current->prev;

delete current;

return;

current = current->next;

}
void printList() {

Node* temp = head;

while (temp) {

cout << temp->data << " ";

temp = temp->next;

cout << endl;

};

int main() {

DoublyLinkedList dll;

dll.insertAtEnd(1);

dll.insertAtEnd(2);

dll.insertAtEnd(3);

dll.insertAtEnd(4);

cout << "Original Doubly Linked List: ";

dll.printList();

dll.removeNode(3);

cout << "List after removing node with value 3: ";

dll.printList();

return 0;

OUTPUT: