Dsa Assignment Final Ojas Nagta 102184009

1
A
Laboratory File
Submitted For
DATA STRUCTURE AND ALGORITHMS

(UCS540)
Submitted By:
Ojas Nagta
102184009
3EE4
Submitted To:
Dr. Ashish Kumar Gupta
Electrical and Instrumentation Engineering Department

Thapar Institute of Engineering and Technology (TIET)
A DEEMED TO BE UNIVERSITY)
PATIALA, PUNJAB-147004
Ojas Nagta 102184009

2
INDEX
Sr.No List of Experiments Page No.
1. 3-13
Assignment 1
2. 14-28
Assignment 2
3. 29-33
Assignment 3
4. 34-40
Assignment 4
5. 41-53
Assignment 5
6. Assignment 6 54-57
7 Assignment 7 58-64

3
Que :1) Write a program in C to convert miles into kilometers

(Km). Hint: 1 Mile=1.609 Km. [Use macros, relevant name
and types for variables].
Code:
#include <stdio.h>
#define MILES_TO_KM 1.609
void convert_miles_to_km() {
float miles, km;
printf("Enter distance in miles: ");
scanf("%f", &miles);
km = miles * MILES_TO_KM;
printf("%.2f miles = %.2f kilometers\n", miles, km);
}
int main() {
convert_miles_to_km();
return 0; }
Output:

4
Que :2) Write a program to find the number of positive, negative and
zeros in a sequence of inputs (numbers) entered as data
Code:
#include <stdio.h>
void count_positive_negative_zero() {
int num, positive = 0, negative = 0, zero = 0;
printf("Enter a sequence of numbers (-999 to end):\n");
do {
scanf("%d", &num);
if (num == -999) {
break; // stop loop when -999 is entered
} else if (num > 0) {
positive++;
} else if (num < 0) {
negative++;
} else {
zero++; }
} while (1);
printf("Positive numbers: %d\n", positive);
printf("Negative numbers: %d\n", negative);
printf("Zeros: %d\n", zero);
int main() { count_positive_negative_zero();
return 0;}

5
Que: 4) Write an interactive program (menu driven) in ‘C’ (using

functions) to compute the area of a selected geometrical figure from a
list of such figures (square, rectangle, and circle).
Code:
#include <stdio.h>
#define PI 3.14159265358979323846
void calculate_area_of_square();
void calculate_area_of_rectangle();
void calculate_area_of_circle();
int main() {

6
int choice;
do { printf("\nArea Calculator Menu\n");
printf("1. Square\n");
printf("2. Rectangle\n");
printf("3. Circle\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
calculate_area_of_square();
break;
case 2:
calculate_area_of_rectangle();
break;
case 3:
calculate_area_of_circle();
break;
case 4:
printf("Exiting...\n");
break;
default:
printf("Invalid choice. Try again.\n");
break; }
} while (choice!= 4);
return 0;
}
void calculate_area_of_square() {
float side, area;
printf("Enter the length of a side of the square: ");
scanf("%f", &side);
area = side * side;

7
printf("Area of the square = %.2f square units\n", area);

} void calculate_area_of_rectangle() {
float length, width, area;
printf("Enter the length of the rectangle: ");
scanf("%f", &length);
printf("Enter the width of the rectangle: ");
scanf("%f", &width);
area = length * width;
printf("Area of the rectangle = %.2f square units\n", area);
} void calculate_area_of_circle() {
float radius, area;
printf("Enter the radius of the circle: ");
scanf("%f", &radius);
area = PI * radius * radius;
printf("Area of the circle = %.2f square units\n", area);}

8
Que: 5) Write a program to display first n elements of Fibonacci

series.
Code:
#include <stdio.h>
int fibonacci(int n);
int main() {
int n, i;
printf("Enter the number of elements in the Fibonacci series: ");
scanf("%d", &n);
printf("The first %d elements of the Fibonacci series are: ", n);
for (i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
} printf("\n");
return 0;
}
int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2); }}
Output:

9
Que: 6) Write a program to print a table book from Table X to Table

Y. X and Y are user inputs.
Code:
#include <stdio.h>
int main() {
int x, y, i, j;
printf("Enter the starting table number: ");
scanf("%d", &x);
printf("Enter the ending table number: ");
scanf("%d", &y);
printf("\n");
for (i = 1; i <= 10; i++) {
for (j = x; j <= y; j++) {
printf("%4d x %2d = %3d ", j, i, i * j); }
printf("\n");
} return 0;}
Output:

10
Que: 7) Write a program to compute factorial of a number using

iterative approach.
Code:
#include <stdio.h>
unsigned long long factorial(int n);
int main() {
int n;
printf("Enter a positive integer: ");
scanf("%d", &n);
if (n < 0) {
printf("Error: Factorial of negative numbers is not defined.\n");
} else {
printf("The factorial of %d is %llu.\n", n, factorial(n));
} return 0;}
unsigned long long factorial(int n) {
int i;
unsigned long long fact = 1;
for (i = 1; i <= n; i++) {
fact *= i;
} return fact; }
Output:

11
Que: 8) Write a program to swap two numbers using functions.

Code:
#include <stdio.h>
void swap(int *a, int *b);
int main() {
int x, y;
printf("Enter two numbers: ");
scanf("%d %d", &x, &y);
printf("Before swapping: x = %d, y = %d\n", x, y);
swap(&x, &y);
printf("After swapping: x = %d, y = %d\n", x, y);
return 0;
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;}
Output:

12
Que: 9) Write a function that returns the first integer between n_min
and n_max entered as data to the calling function (main).
Code:
#include <stdio.h>
#include <stdlib.h>
int random_int(int min, int max)
{ return min + rand() % (max - min + 1);}
int first_int(int n_min, int n_max)
{
int num;
printf("Enter an integer between %d and %d: ", n_min, n_max);
scanf("%d", &num);
while (num < n_min || num > n_max)
{
printf("Invalid input. Try again: ");
scanf("%d", &num); }
return num;}
int main(){
int n_min = 10;
int n_max = 20;
int result = first_int(n_min, n_max);
printf("The first integer between %d and %d is %d\n", n_min, n_max, result);
return 0;}
Output:

13
Que: 10) Write nests of loops that cause the following output to be
displayed.
Code:

14
Program: 01 Write a program to check whether a given

number is present in array or not (Linear search).
#include<bits/stdc++.h>
using namespace std;
void len_ser(int a[],int n)
{
int x;
cout<<"input target element:"<<endl;
cin>>x;
for(int i=0;i<n;i++)
{
if(a[i]==x)
{
cout<<"element is found at index:"<<i;
}
}
}
int main()
{
int i,n;
cout<<"Enter n"<<endl;
cin>>n;
int a[n];
cout<<"enter elemnts of array"<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"array"<<endl;
for(i=0;i<n;i++)
{
cout<<" "<<a[i];
}
cout<<endl;
len_ser(a,n);
return 0;

15
Program: 02 Write a program to get second maximum and second

minimum elements in an array.
void max_min(int a[],int n)

{
// sort(a,a+n);
// cout<<"Second max is:"<<a[n-2]<<endl;
// cout<<"Second min is:"<<a[1]<<endl;
//
int max1,min1;
int max2,min2;
min1=INT_MAX;
{
min1=min(min1,a[i]);
}
max1=INT_MIN;
{
max1=max(max1,a[i]);
}
min2=INT_MAX;
{
if(a[i]==min1) continue;
min2=min(min2,a[i]);

16
}
max2=INT_MIN;
{
if(a[i]==max1) continue;
max2=max(max2,a[i]);
}
cout<<"Second max is:"<<max2<<endl;
cout<<"Second min is:"<<min2<<endl;
}
int main()
{ int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
cout<<" "<<a[i];
}
cout<<endl;
max_min(a,n);
return 0;}

17
Program: 03 Write a program to perform insertion (any location),

deletion (any location) and traversal in an array.
void traverse(int [],int);
void insertion(int [],int);
void deletion(int [],int);
int main()
{
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
int fun;
cout<<endl;
cout<<"write operation to perform:"<<endl;
cin>>fun;
switch(fun){
case 1:
traverse(a,n);
break;
case 2:
insertion(a,n);
break;
case 3:
deletion(a,n);
break;;
default:
cout<<"No operation selected:"<<endl;
}
}
void traverse(int a[],int n)

{
for(int i=0;i<n+1;i++)
{
cout<<" "<<a[i];
}
cout<<endl;

18
void insertion(int a[],int n)

{ int x,pos;
cout<<"enter element:";
cin>>x;
cout<<"enter location";
cin>>pos;
a[n]=a[n+1];
for(int i=n;i>=pos;i--)
{
a[i+1]=a[i];
}
a[pos]=x;
traverse(a,n);
}
void deletion(int a[],int n)
{
int x;
cout<<"Enter loction:"<<endl;
cin>>x;
for (int i = x - 1; i < n- 1; i++)
{
a[i] = a[i+1];
}
n--;
traverse(a,n);}

19
Program: 04 Write a menu driven program to perform addition,

multiplication and subtraction of 2 arrays.
const int MAX_SIZE = 100;
void input_array(int arr[], int size) {

for (int i = 0; i < size; i++) {
cout << "Enter element " << i << ": ";
cin >> arr[i];
}
}
void display_array(int arr[], int size) {

cout << arr[i] << " ";
}
cout << endl;
}
void add_arrays(int arr1[], int arr2[], int size, int result[]) {

result[i] = arr1[i] + arr2[i];
}
}
void multiply_arrays(int arr1[], int arr2[], int size, int result[]) {

20

result[i] = arr1[i] * arr2[i];
}
}
void subtract_arrays(int arr1[], int arr2[], int size, int result[]) {

result[i] = arr1[i] - arr2[i];
}
}
int main() {
int size, choice;
int arr1[MAX_SIZE], arr2[MAX_SIZE], result[MAX_SIZE];
cout << "Enter the size of the arrays: ";

cin >> size;
cout << "Enter elements of array 1: " << endl;

input_array(arr1, size);
cout << "Enter elements of array 2: " << endl;

input_array(arr2, size);
while (true) {
cout << "Menu" << endl;
cout << "1. Add arrays" << endl;
cout << "2. Multiply arrays" << endl;
cout << "3. Subtract arrays" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
add_arrays(arr1, arr2, size, result);
cout << "Result of addition: ";
display_array(result, size);
break;
case 2:
multiply_arrays(arr1, arr2, size, result);
cout << "Result of multiplication: ";
break;
case 3:
subtract_arrays(arr1, arr2, size, result);
cout << "Result of subtraction: ";

21
break;
case 4:
exit(0);
default:
cout << "Invalid choice. Try again." << endl;
}
}
return 0;
}
Program :5 Write a program to perform sorting while merging

(Merge two sorted arrays into one sorted array).

22
#include <bits/stdc++.h>
void merge(int arr1[], int n1, int arr2[], int n2, int result[]) {
int i = 0;
int j = 0;
int k = 0;
while (i < n1 && j < n2) {

if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
i++;
} else {
result[k] = arr2[j];
j++;
}
k++;
}
while (i < n1) {

result[k] = arr1[i];
i++;
k++;
}
while (j < n2) {

result[k] = arr2[j];
j++;
k++;
}
}
int main() {
int arr1[5];
int arr2[5];
cout << "Enter the elements of the first array: ";

for (int i = 0; i < 5; i++) {
cin >> arr1[i];
}
cout << "Enter the elements of the second array: ";

for (int i = 0; i < 5; i++) {
cin >> arr2[i];
}
int n1 = 5;
int n2 = 5;
int result[n1 + n2];

23
merge(arr1, n1, arr2, n2, result);
cout << "Merged and sorted array: ";

for (int i = 0; i < n1 + n2; i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
Program :6 Write the above programs (1,2, and 3) using functions

and call by address only.
Ques 1:
// Function to search for target element in array

void len_ser(int *a, int n, int x, int &idx) {
for (int i = 0; i < n; i++) {
if (a[i] == x) {
idx = i;
return;
}
}
idx = -1;
}
int main() {
int n;
cout << "Enter n: " << endl;

24
cin >> n;
int a[n];
cout << "Enter elements of array: " << endl;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << "Array: ";

for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
int x, idx;
cout << "Input target element: " << endl;
cin >> x;
len_ser(a, n, x, idx);
if (idx == -1) {
cout << "Element not found in array" << endl;
} else {
cout << "Element found at index " << idx << endl;
}
return 0;}

25
Que 2:
void max_min(int a[],int n)

{
int max1, min1, max2, min2;
min1 = INT_MAX;
{
min1 = min(min1, a[i]);
}
max1 = INT_MIN;
{
max1 = max(max1, a[i]);
}
min2 = INT_MAX;
{
if(a[i] == min1) continue;
min2 = min(min2, a[i]);
}
max2 = INT_MIN;
{
if(a[i] == max1) continue;
max2 = max(max2, a[i]);
}
cout<<"Second max is:"<<max2<<endl;
cout<<"Second min is:"<<min2<<endl;
}
int main()
{
int n;
cin>>n;
int a[n];
cout<<"enter elements of array"<<endl;
for(int i=0; i<n; i++)
{
cin>>a[i];
}
cout<<"Array"<<endl;
for(int i=0; i<n; i++)
{
cout<<" "<<a[i];
}

26
cout<<endl;
max_min(a,n);
return 0;
}
Que 3:
void traverse(int *, int);
void insertion(int *, int&);
void deletion(int *, int&);
int main()
{
int n;
cout << "Enter n: " << endl;
cin >> n;
int a[n];
cout << "Enter elements of array: " << endl;
{
cin >> a[i];
}
int fun;
cout << endl << "Write operation to perform: " << endl;
cin >> fun;
switch(fun)
{ case 1:
traverse(a,n);
break;
case 2:
insertion(a,n);
break;
case 3:

27
deletion(a,n);
break;
default:
cout << "No operation selected." << endl;
}}
void traverse(int *a, int n)
{
cout << "Array: " << endl;
{
cout << " " << *(a+i);
}
cout << endl;
}
void insertion(int *a, int &n)
{ int x, pos;
cout << "Enter element: ";
cin >> x;
cout << "Enter location: ";
cin >> pos;
for(int i=n-1; i>=pos; i--)
{
*(a+i+1) = *(a+i);
}
*(a+pos) = x;
n++;
traverse(a, n);
}
void deletion(int *a, int &n)
{ int x;
cout << "Enter location: " << endl;
cin >> x;
for(int i=x-1; i<n-1; i++)
{
*(a+i) = *(a+i+1);
}
n--;
traverse(a,n); }

28

29
Assignment – 3
Que 1: Write a program to implement strlen() function
Code:
#include <iostream>
int strlen(char* str) {
int length = 0;
while (*str != '\0') {
length++;
str++;
}
return length;
}
int main() {
char str[] = "Hello, world!";
int length = strlen(str);
cout << "The length of the string is: " << length << endl;
return 0;
}
Output:
Que 2: Write a program to implement strcpy() function

Code:
#include <iostream>
#include <cstring>

char* strcpy(char* dest, const char* src) {
char* ptr = dest;
while (*src != '\0') {

30
*dest = *src;
dest++;
src++;
}
*dest = '\0';
return ptr;
}
int main() {
// Test the strcpy() function
char str1[20] = "Hello";
char str2[20];
strcpy(str2, str1);
cout << "Copied string is: " << str2 << endl;
return 0;
}
Output:
Que 3: Write a program to implement strcat() function.

Code:
#include <iostream>
#include <cstring>
char* my_strcat(char* str1, char* str2) {
int len1 = strlen(str1);
for (int i = 0; str2[i] != '\0'; i++) {
str1[len1 + i] = str2[i];
}
str1[len1 + strlen(str2)] = '\0';
return str1;
}
int main() {
char str1[100], str2[100];
cout << "Enter the first string: ";
cin.getline(str1, 100);
cout << "Enter the second string: ";
cin.getline(str2, 100);

31
char* result = my_strcat(str1, str2);

cout << "Concatenated string: " << result << endl;
return 0;
}
Output:
Que 4: Write a program to implement strcmp() function.

Code:
#include <iostream>
#include <cstring>
int strcmp(const char* str1, const char* str2) {
int i = 0;
while (str1[i] != '\0' && str2[i] != '\0') {
if (str1[i] != str2[i]) {
return str1[i] - str2[i];
}
i++;
}
return str1[i] - str2[i];
}
int main() {
char str1[] = "Hello";
char str2[] = "World";
int result = strcmp(str1, str2);
cout << "Result: " << result << endl;
return 0;
}
Output:

32
Que 5: WAP to demonstrate limitations of Two-Dimensional Array of

Characters.
Code:
#include <iostream>
#include <cstring>
int main() {
char arr[3][5];
strcpy(arr[0], "hello");
strcpy(arr[1], "world");
strcpy(arr[2], "!");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 5; j++) {
cout << arr[i][j];
}
cout << endl;
}
arr[1][2] = 'x';
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 5; j++) {
cout << arr[i][j];
}
cout << endl; }
strcpy(arr[3], "oops");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 5; j++) {
cout << arr[i][j];
}
cout << endl;
}
return 0; }
Output:

33
Que 6: WAP to demonstrate an array of Pointers to Strings.

Code:
#include <iostream>
int main() {
const char* strings[] = {"Hello", "World", "from", "Ojas"};
int length = sizeof(strings) / sizeof(strings[0]);
for (int i = 0; i < length; i++) {
cout << strings[i] << " ";
}
return 0;
}
Output:

34
Assignment – 4
Que 1: Write a program to implement KMP pattern matching algorithm.
[String processing]
Code:
#include <bits/stdc++.h>
void computeLPSArray(char* pat, int M, int* lps);

void KMPSearch(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d\n", i - j);
j = lps[j - 1];
}
else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(char* pat, int M, int* lps)
{
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;

35
i++;
}
else
{
if (len != 0) {
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
int main()
{
char txt[] = "ABABDABACDABABCABAB";
char pat[] = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
Output:
Que 2: Sum of n numbers using arrays a) Iterative approach b) Recursive

approach
Code:
#include<iostream>
int sumIterative(int arr[], int n){
int sum = 0;
for(int i=0; i<n; i++){
sum += arr[i];
}
return sum;

36
}
int sumRecursive(int arr[], int n){
if(n == 0){
return 0;
}
else{
return arr[n-1] + sumRecursive(arr, n-1);
}
}
int main(){
int n;
cout<<"Enter the number of elements: ";
cin>>n;
int arr[n];
cout<<"Enter the elements: ";
for(int i=0; i<n; i++){
cin>>arr[i];
}
cout<<"Sum using iterative approach: "<<sumIterative(arr, n)<<endl;
cout<<"Sum using recursive approach: "<<sumRecursive(arr, n)<<endl;
return 0;
}
Output:

37
Que 3: Write a program to implement binary search. a) Iterative approach b)

Recursive approach
Code:
#include <iostream>
#include <vector>
int binarySearchIterative(vector<int> arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
int binarySearchRecursive(vector<int> arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
}
else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9};
int target = 5;
int indexIterative = binarySearchIterative(arr, target);
if (indexIterative == -1) {
cout << "Target not found using iterative approach" << endl;

38
}
else {
cout << "Target found at index " << indexIterative << " using iterative approach" << endl;
}
int indexRecursive = binarySearchRecursive(arr, target, 0, arr.size() - 1);
if (indexRecursive == -1) {
cout << "Target not found using recursive approach" << endl;
}
else {
cout << "Target found at index " << indexRecursive << " using recursive approach" << endl;
}
return 0;
}
Result:
Que 4: Write a program to implement Tower of Hanoi problem.

Code:
#include <iostream>
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
if (n == 1) {
cout << "Move disk 1 from tower " << source << " to tower " << destination << endl;
return;
}
towerOfHanoi(n - 1, source, auxiliary, destination);
cout << "Move disk " << n << " from tower " << source << " to tower " << destination << endl;
towerOfHanoi(n - 1, auxiliary, destination, source);
}
int main() {
int n = 3;
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
}

39
Result:
Que 5: Write a program to implement finding min and max from an array. a)
Iterative approach b) Recursive approach.
Code:
#include <iostream>
#include <climits>
void findMinMaxIterative(int arr[], int n, int& min, int& max) {
min = arr[0];
max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
}
void findMinMaxRecursive(int arr[], int low, int high, int& min, int& max) {
if (low == high) {
min = arr[low];
max = arr[low];
return;
}
if (high == low + 1) {
if (arr[low] < arr[high]) {
min = arr[low];
max = arr[high];
} else {
min = arr[high];
max = arr[low];
}

40
return;
}
int mid = (low + high) / 2;
int min1, max1, min2, max2;
findMinMaxRecursive(arr, low, mid, min1, max1);
findMinMaxRecursive(arr, mid + 1, high, min2, max2);
min = (min1 < min2) ? min1 : min2;
max = (max1 > max2) ? max1 : max2;
}
int main() {
int arr[] = { 1, 4, 6, 2, 8, 3, 9, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int minIterative, maxIterative;
findMinMaxIterative(arr, n, minIterative, maxIterative);
cout << "Minimum element using iterative approach: " << minIterative << endl;
cout << "Maximum element using iterative approach: " << maxIterative << endl;
int minRecursive, maxRecursive;
findMinMaxRecursive(arr, 0, n - 1, minRecursive, maxRecursive);
cout << "Minimum element using recursive approach: " << minRecursive << endl;
cout << "Maximum element using recursive approach: " << maxRecursive << endl;
return 0;
}
Output:

41
Assignment – 5
Program: 01 Write a menu driven program with 4 options
(Push, Pop, Display, and Exit) to demonstrate the working of
stacks using arrays.
#include <iostream>
#define MAX_SIZE 10
int stack[MAX_SIZE], top = -1;
void push(int item) {

if (top == MAX_SIZE - 1) {
cout << "Stack Overflow!" << endl;
} else {
top++;
stack[top] = item;
cout << item << " pushed into stack." << endl;
}
}
int pop() {
if (top == -1) {
cout << "Stack Underflow!" << endl;
return -1;
} else {
int popped_item = stack[top];
top--;
cout << popped_item << " popped from stack." << endl;
return popped_item;
}
}
void display() {
if (top == -1) {
cout << "Stack is empty." << endl;
} else {
cout << "Elements in stack are: ";
for (int i = top; i >= 0; i--) {
cout << stack[i] << " ";
}

42
cout << endl;

}
}
int main() {
int choice, item;
while (true) {
cout << endl;
cout << "Stack Operations" << endl;
cout << "1. Push" << endl;
cout << "2. Pop" << endl;
cout << "3. Display" << endl;
cin >> choice;
switch (choice) {
case 1:
cout << "Enter item to push: ";
cin >> item;
push(item);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
cout << "Exiting program..." << endl;
exit(0);
default:
cout << "Invalid choice, please try again." << endl;
}
}
return 0;
}

43
Output:

44
Program: 02 Write a menu driven program with 4 options (Push,

Pop, Display, and Exit) to demonstrate the working of stacks using
linked-list
#include <iostream>
struct Node {
int data;
Node* next;
};
class Stack {
Node* top;
public:
Stack() {
top = NULL;
}
void push(int item) {

Node* new_node = new Node;
new_node->data = item;
new_node->next = top;
top = new_node;
cout << item << " pushed into stack." << endl;
}
int pop() {
if (top == NULL) {
cout << "Stack Underflow!" << endl;
return -1;
}
int popped_item = top->data;
Node* temp = top;
top = top->next;
delete temp;
cout << popped_item << " popped from stack." << endl;
return popped_item;
}
void display() {
if (top == NULL) {
cout << "Stack is empty." << endl;
return;
}
cout << "Elements in stack are: ";
Node* temp = top;

45
while (temp != NULL) {

cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
Stack stack;
int choice, item;
while (true) {
cout << "Stack Operations" << endl;
cout << "1. Push" << endl;
cout << "2. Pop" << endl;
cin >> choice;
switch (choice) {
case 1:
cout << "Enter item to push: ";
cin >> item;
stack.push(item);
break;
case 2:
stack.pop();
break;
case 3:
stack.display();
break;
case 4:
exit(0);
default:
}
}
return 0;
}

46
Output:

47
Program: 03 Write a menu driven program with 4 options (Insert, Delete,

Display, and Exit) to demonstrate the working of Queues using linked-list.
#include <iostream>
struct Node {
int data;
Node* next;
};
class Queue {
Node* front;
Node* rear;
public:
Queue() {
front = NULL;
rear = NULL;
}
void insert(int item) {
Node* new_node = new Node;
new_node->data = item;
new_node->next = NULL;
if (front == NULL) {
front = rear = new_node;
} else {
rear->next = new_node;
rear = new_node;
}
cout << item << " inserted into queue." << endl;
}
int delete_item() {
cout << "Queue is empty!" << endl;
return -1;
}
int deleted_item = front->data;
Node* temp = front;
front = front->next;
delete temp;
cout << deleted_item << " deleted from queue." << endl;
return deleted_item;
}
void display() {

48
return;
}
cout << "Elements in queue are: ";
Node* temp = front;
temp = temp->next;
}
cout << endl;
}};
int main() {
Queue queue;
int choice, item;
while (true) {
cout << "Queue Operations" << endl;
cout << "1. Insert" << endl;
cout << "2. Delete" << endl;
cin >> choice;
switch (choice) {
case 1:
cout << "Enter item to insert: ";
cin >> item;
queue.insert(item);
break;
case 2:
queue.delete_item();
break;
case 3:
queue.display();
break;
case 4:
exit(0);
default:
} }
return 0;
}

49
Output:

50
Program: 04 Write a menu driven program with 4 options (Insert, Delete,

Display, and Exit) to demonstrate the working of Circular Queues (arrays.)
#include <iostream>
class CircularQueue {
int* arr;
int front;
int rear;
int size;
public:
CircularQueue(int s) {
arr = new int[s];
front = -1;
rear = -1;
size = s;
}
int is_empty() {
return front == -1;
}
int is_full() {
return (front == 0 && rear == size - 1) || (rear == front - 1);
}
void insert(int item) {

if (is_full()) {
cout << "Queue is full!" << endl;
return;
}
if (front == -1) {
front = rear = 0;
} else if (rear == size - 1 && front != 0) {
rear = 0;
} else {
rear++;
}
arr[rear] = item;
cout << item << " inserted into queue." << endl;
}
int delete_item() {
if (is_empty()) {
return -1;

51
}
int deleted_item = arr[front];
if (front == rear) {
front = rear = -1;
} else if (front == size - 1) {
front = 0;
} else {
front++;
}
cout << deleted_item << " deleted from queue." << endl;
return deleted_item;
}
void display() {
if (is_empty()) {
return;
}
cout << "Elements in queue are: ";
if (rear >= front) {
for (int i = front; i <= rear; i++) {
cout << arr[i] << " ";
}
} else {
for (int i = front; i < size; i++) {
cout << arr[i] << " ";
}
for (int i = 0; i <= rear; i++) {
cout << arr[i] << " ";
}
}
cout << endl;
}
};
int main() {
int size, choice, item;
cout << "Enter size of circular queue: ";
cin >> size;
CircularQueue queue(size);
while (true) {
cout << "Circular Queue Operations" << endl;
cout << "1. Insert" << endl;
cout << "2. Delete" << endl;
cin >> choice;

52
switch (choice) {
case 1:
cout << "Enter item to insert: ";
cin >> item;
queue.insert(item);
break;
case 2:
queue.delete_item();
break;
case 3:
queue.display();
break;
case 4:
exit(0);
default:
}
}
return 0;
}

53
Output:

54
Assignment – 6
Que :1 Write a program to convert infix expression into postfix expression
using stack
Code:
#include <iostream>
#include <stack>
#include <string>
string infixToPostfix(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 {
while (!s.empty() && s.top() != '(' && ((c == '*' || c == '/') && (s.top() == '+' || s.top() == '-') || (c
== s.top() && (c == '+' || c == '-')))) {
postfix += s.top();
s.pop();
}
s.push(c);
}
}
while (!s.empty()) {
postfix += s.top();
s.pop();
}
return postfix;
}
int main() {
string infix = "a+b*c-d/e";
string postfix = infixToPostfix(infix);

55
cout << "Infix expression: " << infix << endl;

cout << "Postfix expression: " << postfix << endl;
return 0;
}
Result:
Que: 2 Write a program to evaluate a postfix expression using stack.

Code: #include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack {
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;

56
}
int peek(struct Stack* stack)
{
return stack->array[stack->top];
}
int pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, int op)
{
stack->array[++stack->top] = op;
}
int evaluatePostfix(char* exp)
{
struct Stack* stack = createStack(strlen(exp));
int i;
if (!stack)
return -1;
for (i = 0; exp[i]; ++i) {
if (exp[i] == ' ')
continue;
else if (isdigit(exp[i])) {
int num = 0;
while (isdigit(exp[i])) {
num = num * 10 + (int)(exp[i] - '0');
i++;
}
i--;
push(stack, num);
}
else {
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i]) {
case '+':
push(stack, val2 + val1);
break;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':

57
push(stack, val2 / val1);

break;
}
}
}
return pop(stack);
}
int main()
{
char exp[] = "100 200 + 2 / 5 * 7 +";
printf("%d", evaluatePostfix(exp));
return 0;
}
Output:

58
Assignment – 7
Que 1: Write a program to implement bubble sort for sorting n elements in an
array
Code:
#include <iostream>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int n;
cout << "Enter the size of the array: ";
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
{
cout << "Enter element " << i + 1 << ": ";
cin >> arr[i];
}
cout << "The array is: ";
for (int i = 0; i < n; i++)
{

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

}
cout << endl;
bubbleSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
Result:
Que 2: Write a program to implement Selection sort for sorting n elements in

an array
Code:
#include <iostream>
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;

60
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
selectionSort(arr, n);
cout << "Sorted array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:
Que: 3 Write a program to implement Insertion sort for sorting n elements in

an array
Code:
#include <iostream>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {

61
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
insertionSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:
Que 4: Write a program to implement Shell sort for sorting n elements in an

array.
Code:
#include <iostream>
void shellSort(int arr[], int n) {
for (int gap = n/2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}

62
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
shellSort(arr, n);

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Result:
Que 5: Write a program to implement Radix sort for sorting n elements in an

array.
Code:
63
#include <iostream>
int getMax(int arr[], int n) {
int mx = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > mx) {
mx = arr[i];
}
}
return mx;
}
void countSort(int arr[], int n, int exp) {
int output[n];
int i, count[10] = {0};
for (i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i++) {

arr[i] = output[i];
}
}
void radixSort(int arr[], int n) {
int m = getMax(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
radixSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";

64
}
return 0;
}
Result:

65
Assignment – 8
Que 1: Write a program to implement Merge sort.
Code:
#include <iostream>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
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++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

66
void mergeSort(int arr[], int l, int r) {

if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Result:
Que 2: Write a program to implement Quick sort

Code:
#include <iostream>
int partition(int arr[], int low, int high) {

67
int pivot = arr[high];

int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:

68
Assignment – 9
Que 1: Write a program to implement single Link List (with function insertion
at first node, insertion at last node, deletion at first node, deletion at last node,
insertion and deletion at middle node and traversing of link list).
Code:
#include <iostream>

struct Node {
int data;
Node* next;
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = NULL;
}
void insertAtFirst(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = head;
head = newNode;
}
void insertAtLast(int data) {
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteAtFirst() {

69
if (head == NULL) {
cout << "Linked list is empty" << endl;
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
void deleteAtLast() {
if (head == NULL) {
return;
}
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node* temp = head;
while (temp->next->next != NULL) {
temp = temp->next;
}
delete temp->next;
temp->next = NULL;
}
void insertAtMiddle(int data, int position) {
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
for (int i = 1; i < position-1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Position out of range" << endl;
return;
}
newNode->next = temp->next;
}
void deleteAtMiddle(int position) {
if (head == NULL) {
return;

70
}
Node* temp = head;
Node* prev = NULL;
for (int i = 1; i < position && temp != NULL; i++) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
cout << "Position out of range" << endl;
return;
}
if (prev == NULL) {
head = temp->next;
} else {
prev->next = temp->next;
}
delete temp;
}
void traverse() {
if (head == NULL) {
return;
}
Node* temp = head;
temp = temp->next;
}
cout << endl;
}
};
int main() {
LinkedList list;
list.insertAtFirst(10);
list.insertAtFirst(20);
list.insertAtLast(30);
list.insertAtLast(40);
list.insertAtMiddle(50, 3);
list.traverse();
list.deleteAtFirst();
list.deleteAtLast();
list.deleteAtMiddle(2);
list.traverse();
return 0;
}

71
Output:
Que :2 Write a program to implement Doubly Link List (with function

insertion at first node, insertion at last node, deletion at first node, deletion at
last node, insertion and deletion at middle node and traversing of link list).
Code:
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() {
head = NULL;
tail = NULL;
}
void insertAtFirst(int value) {
newNode->data = value;
newNode->prev = NULL;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
if (tail == NULL) {
tail = newNode;
}
}
void insertAtLast(int value) {

72
newNode->prev = tail;
if (tail != NULL) {
tail->next = newNode;
}
tail = newNode;
if (head == NULL) {
head = newNode;
}
}
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
Node* temp = head;
head = head->next;
if (head != NULL) {
head->prev = NULL;
}
delete temp;
}
if (tail == NULL) {
return;
}
Node* temp = tail;
tail = tail->prev;
if (tail != NULL) {
tail->next = NULL;
}
delete temp;
}
void insertAtMiddle(int value, int position) {
Node* temp = head;
temp = temp->next;
}
if (temp == NULL) {
cout << "Invalid position" << endl;
return;
}
newNode->prev = temp;
if (temp->next != NULL) {

73
temp->next->prev = newNode;
}
}
Node* temp = head;
temp = temp->next;
}
if (temp == NULL) {
return;
}
if (temp == head) {
head = temp->next;
}
if (temp == tail) {
tail = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
temp->next->prev = temp->prev;
}
delete temp;
}
void traverse() {
Node* temp = head;
temp = temp->next;
}
cout << endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtFirst(10);
dll.traverse();
dll.insertAtLast(40);
dll.traverse();

74
dll.deleteAtFirst();
dll.traverse();
dll.deleteAtLast();
dll.deleteAtLast();
dll.traverse();
dll.insertAtMiddle(30, 2);
dll.traverse();
dll.deleteAtMiddle(2);
dll.traverse();
return 0;
}
Result:
Que 3: Write a program to implement Circular Doubly Link List (with

function insertion at first node, insertion at last node, deletion at first node,

75
deletion at last node, insertion and deletion at middle node and traversing of link
list).
Code:
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() {
head = NULL;
tail = NULL;
}
void insertAtFirst(int value) {
newNode->prev = NULL;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
if (tail == NULL) {
tail = newNode;
}
}
void insertAtLast(int value) {
newNode->prev = tail;
if (tail != NULL) {
tail->next = newNode;
}
tail = newNode;
if (head == NULL) {
head = newNode;
}
}
if (head == NULL) {

76

return;
}
Node* temp = head;
head = head->next;
if (head != NULL) {
head->prev = NULL;
}
delete temp;
}
if (tail == NULL) {
return;
}
Node* temp = tail;
tail = tail->prev;
if (tail != NULL) {
tail->next = NULL;
}
delete temp;
}
void insertAtMiddle(int value, int position) {
Node* temp = head;
temp = temp->next;
}
if (temp == NULL) {
return;
}
newNode->prev = temp;
temp->next->prev = newNode;
}
}
Node* temp = head;
temp = temp->next;
}
if (temp == NULL) {
return;

77
}
if (temp == head) {
head = temp->next;
}
if (temp == tail) {
tail = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
temp->next->prev = temp->prev;
}
delete temp;
}
void traverse() {
Node* temp = head;
temp = temp->next;
}
cout << endl;
}
};
int main() {
DoublyLinkedList dll;
dll.traverse();
dll.traverse();
dll.traverse();
dll.deleteAtLast();
dll.deleteAtLast();
dll.traverse();
dll.traverse();

78
dll.traverse();
return 0;
}
Output:

Dsa Assignment Final Ojas Nagta 102184009

Uploaded by

Copyright:

Available Formats

Dsa Assignment Final Ojas Nagta 102184009

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dsa Assignment Final Ojas Nagta 102184009

Uploaded by

Copyright:

Available Formats

1

DATA STRUCTURE AND ALGORITHMS

Electrical and Instrumentation Engineering Department

Ojas Nagta 102184009

Sr.No List of Experiments Page No.

Ojas Nagta 102184009

Que :1) Write a program in C to convert miles into kilometers

Ojas Nagta 102184009

Ojas Nagta 102184009

Que: 4) Write an interactive program (menu driven) in ‘C’ (using

Ojas Nagta 102184009

Ojas Nagta 102184009

printf("Area of the square = %.2f square units\n", area);

Ojas Nagta 102184009

Que: 5) Write a program to display first n elements of Fibonacci

Ojas Nagta 102184009

Que: 6) Write a program to print a table book from Table X to Table

Ojas Nagta 102184009

Que: 7) Write a program to compute factorial of a number using

Ojas Nagta 102184009

Que: 8) Write a program to swap two numbers using functions.

Ojas Nagta 102184009

Ojas Nagta 102184009

Ojas Nagta 102184009

Program: 01 Write a program to check whether a given

Ojas Nagta 102184009

Program: 02 Write a program to get second maximum and second

void max_min(int a[],int n)

Ojas Nagta 102184009

Ojas Nagta 102184009

Program: 03 Write a program to perform insertion (any location),

void traverse(int a[],int n)

Ojas Nagta 102184009

void insertion(int a[],int n)

Ojas Nagta 102184009

Program: 04 Write a menu driven program to perform addition,

const int MAX_SIZE = 100;

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

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

void add_arrays(int arr1[], int arr2[], int size, int result[]) {

void multiply_arrays(int arr1[], int arr2[], int size, int result[]) {

Ojas Nagta 102184009

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

void subtract_arrays(int arr1[], int arr2[], int size, int result[]) {

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

cout << "Enter elements of array 1: " << endl;

cout << "Enter elements of array 2: " << endl;

Ojas Nagta 102184009

Program :5 Write a program to perform sorting while merging

Ojas Nagta 102184009

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

while (i < n1) {

while (j < n2) {

cout << "Enter the elements of the first array: ";

cout << "Enter the elements of the second array: ";

Ojas Nagta 102184009

merge(arr1, n1, arr2, n2, result);

cout << "Merged and sorted array: ";

Program :6 Write the above programs (1,2, and 3) using functions

// Function to search for target element in array