Divyanshu dsa file1

NOIDA INSTITUTE OF ENGINEERING AND TECHNOLOGY
GREATER NOIDA
Department of CSE(IoT)
School of Computer Sciences in Emerging Technologies
Lab File
of
DATA STRUCTURE & ALGORITHMS-1

(BCSE-0351)
(3rd Semester)
Session (2024 – 2025)
Affiliated to Dr. A.P.J Abdul Kalam Technical University, Uttar Pradesh, Lucknow
Submitted By: Submitted To:
Divyanshu Ms. Neha Bhati

Sharma
Mr. Sachin Chawla
ROLL NO:
2301331550037
[BCSE0301] DATA STRUCTURES & ALGORITHMS-1 2024
Index
B. TECH. SECOND YEAR (CSE(IoT)) 3rd Sem
Course Code BCSE0301 LTP Credit
Course Title Data Structure & Algorithm -1 0 0 4 2
Lab Experiments
Course Objective: Learn to implement linear data structures.
Course Outcomes (CO)
Course outcome: After completion of this course Bloom’s Knowledge

students will be able to: Level(KL)
Implementing Single and Multi-dimensional array with

CO 1 their applications like searching K3
and Sorting techniques.
CO2 Implement Link list, Stack and Queues with their K3
applications.
CO3 Implementation and analysis of various Divide and K4
Conquer, Greedy Algorithms.
List of Practical’s
CO Date Signature
Sr No Program Title
Mapping
Construct a program to compare the time complexities of CO1
1 selection, bubble and insertion
sort by plotting the graph
Construct a program to compare the time complexities of CO1
2 various algorithms by varying
size “n”.
3 Construct a Code to find the maximum element in an array. CO1
4 Construct a Code to calculate the sum of all elements in an CO1
array.
5 Construct a Code to reverse the elements of an array. CO1
6 Construct a Code to check if an array is sorted in ascending CO1
order.
Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET
7 Construct a Code to count the occurrence of a specific CO1

element in an array.
8 Construct a Code creation and traversal of 2D Array in row CO1
major and column major order.
9 Construct a code to print the transpose of a given matrix using CO1
function
10 Program to find if a given matrix is Sparse or Not and print CO1
Sparse Matrix
11 Construct a code to represent a sparse matrix in triplet CO1
form.
12 Construct a code to Implement Linear Search CO1
13 Construct a code to implement Binary Search CO1
14 Construct a program to Implement Selection Sort CO1
15 Construct a program to Implement Bubble Sort CO1
16 Construct a program to Implement Insertion Sort CO1
17 Construct a program to Implement Shell Sort CO1
18 Construct a program to Implement Counting Sort CO1
19 Create a single linked list and perform basic CO2
operations (insertion, deletion, traversal).
20 Create a double linked list and perform basic CO2
operations (insertion, deletion, traversal).
21 Create a circular linked list and perform basic CO2
operations (insertion, deletion,
traversal).
22 Create a circular double linked list and perform basic CO2
operations (insertion, deletion,
traversal).
23 Reverse a single linked list. CO2
24 Check if a linked list is palindrome. CO2
25 Reverse a double linked list. CO2
26 Find the middle element of a single linked list. CO2
27 Find the middle element of a double linked list. CO2
28 Merge two sorted single linked lists. CO2
29 Detect and remove a loop in a circular linked list. CO2
30 Construct a code to add two polynomials using linked CO2
list
31 Construct a program to Implement stack using array CO2
32 Construct a program to Implement stack using a CO2
linked list
33 Construct a code to Infix to postfix conversion using a CO2
stack

34 Construct a code for Balanced parentheses checker CO2
using a stack
35 Implement Reverse a string using a stack. CO2
36 Implement Binary Search using Recursion. CO2
37 Construct a python program to print Fibonacci Series CO2

using Recursion.
38 Construct a code to implement Tower of Hanoi. CO2
39 Construct a program to Implement queue using array. CO2
40 Construct a code for Implementing a circular queue. CO2
41 Construct a program to Implement queue using stack CO2
42 Construct a program to Implement priority queue CO2
43 Construct a program to Implement double ended CO2
queue
44 Construct a program to Implement Merge Sort with CO3
recursion
45 Construct a program to Implement Quick Sort with CO3
recursion
46 Construct a program to Implement Merge Sort using CO3
iteration
47 Construct a program to Implement Quick Sort using CO3
iteration
48 Construct a program to Implement fractional knapsack CO3
49 Construct a program to Implement Activity selection CO3
problem
50 Construct a program to Implement Job scheduling CO3
problem

Experiment- 1
AIM- Construct a program to compare the time complexities of selection, bubble
and insertion sort by plotting the graph
Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx, temp;
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;
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
void bubbleSort(int arr[], int n) {

int i, j, temp;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
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() {
int n = 1000, arr[1000], i;
clock_t start, end;
double time_used;
for (i = 0; i < n; i++)
arr[i] = rand() % 1000;
start = clock();
selectionSort(arr, n);
end = clock();
time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Selection Sort: %f seconds\n", time_used);
for (i = 0; i < n; i++)
arr[i] = rand() % 1000;
start = clock();
bubbleSort(arr, n);
end = clock();
printf("Bubble Sort: %f seconds\n", time_used);

for (i = 0; i < n; i++)
arr[i] = rand() % 1000;
start = clock();
insertionSort(arr, n);
end = clock();
printf("Insertion Sort: %f seconds\n", time_used);
return 0;
OUTPUT:

Experiment-2
AIM- Construct a program to compare the time complexities of various
algorithms by varying size “n”.
Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) return;
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]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;

void binarySearch(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) return;
if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
int main() {
int sizes[] = {1000, 5000, 10000, 50000, 100000};
int numSizes = sizeof(sizes) / sizeof(sizes[0]);
srand(time(NULL));
for (int i = 0; i < numSizes; i++) {
int n = sizes[i];
int *arr = (int *)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) arr[j] = rand() % 10000;

clock_t start, end;
start = clock();
linearSearch(arr, n, -1);
end = clock();
printf("Linear Search for n=%d: %lf seconds\n", n, (double)(end - start) /

CLOCKS_PER_SEC);
start = clock();
bubbleSort(arr, n);
end = clock();
printf("Bubble Sort for n=%d: %lf seconds\n", n, (double)(end - start) /

CLOCKS_PER_SEC);
start = clock();
binarySearch(arr, n, -1);
end = clock();
printf("Binary Search for n=%d: %lf seconds\n", n, (double)(end - start) /

CLOCKS_PER_SEC);
free(arr);
return 0;

OUTPUT:

Experiment- 3
AIM- Construct a Code to find the maximum element in an array.
Program:
#include <stdio.h>
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
return max;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Maximum element is: %d\n", findMax(arr, n));
return 0;

OUTPUT:

Experiment- 4
AIM- Construct a Code to calculate the sum of all elements in an array.
Program:
#include <stdio.h>
int calculateSum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
return sum;
int main() {
int arr[] = {1, 2, 3, 4, 5};
printf("Sum of elements is: %d\n", calculateSum(arr, n));
return 0;
OUTPUT:

Experiment- 5
AIM- Construct a Code to reverse the elements of an array.
Program:
#include <stdio.h>
void reverseArray(int arr[], int n) {
int temp;
for (int i = 0; i < n/2; i++) {
temp = arr[i];
arr[i] = arr[n-i-1];
arr[n-i-1] = temp;
int main() {
int arr[] = {1, 2, 3, 4, 5};
reverseArray(arr, n);
printf("Reversed array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);

printf("\n");
return 0;
OUTPUT:

Experiment- 6
AIM- Construct a Code to check if an array is sorted in ascending order.
Program:
#include <stdio.h>
int isSorted(int arr[], int n) {
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
return 0;
return 1;
int main() {
int arr[] = {1, 2, 3, 4, 5};
if (isSorted(arr, n)) {
printf("The array is sorted in ascending order.\n");
} else {
printf("The array is not sorted in ascending order.\n");

return 0;
OUTPUT:

Experiment- 7
AIM- Construct a Code to count the occurrence of a specific element in an
array.
Program:
#include <stdio.h>
int countOccurrences(int arr[], int n, int x) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x)
count++;
return count;
int main() {
int arr[] = {1, 2, 3, 2, 4, 2};
int x = 2;
printf("Element %d occurs %d times\n", x, countOccurrences(arr, n, x));
return 0;
}OUTPUT:

Experiment- 8
AIM- Construct a Code creation and traversal of 2D Array in row major and
column major order.
Program:
#include <stdio.h>
void create2DArray(int rows, int cols, int arr[rows][cols]) {
int value = 1;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
arr[i][j] = value++;
void traverseRowMajor(int rows, int cols, int arr[rows][cols]) {
printf("Row-major order:\n");
printf("%d ", arr[i][j]);
printf("\n");

void traverseColumnMajor(int rows, int cols, int arr[rows][cols]) {
printf("Column-major order:\n");
printf("%d ", arr[i][j]);
printf("\n");
int main() {
int rows = 3, cols = 4;
int arr[rows][cols];
create2DArray(rows, cols, arr);
traverseRowMajor(rows, cols, arr);
traverseColumnMajor(rows, cols, arr);
return 0;

OUTPUT:

Experiment- 9
AIM- Construct a code to print the transpose of a given matrix using function
Program:
#include <stdio.h>
void transpose(int rows, int cols, int matrix[rows][cols]) {
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
printf("%d ", matrix[j][i]);
printf("\n");
int main() {
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
transpose(3, 3, matrix);
return 0;
OUTPUT:

Experiment- 10
AIM- Program to find if a given matrix is Sparse or Not and print Sparse Matrix.
Program:
#include <stdio.h>
int isSparse(int rows, int cols, int matrix[rows][cols]) {
int zeroCount = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (matrix[i][j] == 0)
zeroCount++;
return zeroCount > (rows * cols) / 2;
int main() {
int matrix[3][3] = {{0, 0, 3}, {0, 5, 0}, {0, 0, 9}};
if (isSparse(3, 3, matrix))
printf("Matrix is sparse\n");
else
printf("Matrix is not sparse\n");
return 0;

OUTPUT:

Experiment- 11
AIM- Construct a code to represent a sparse matrix in triplet form.
Program:
#include <stdio.h>
void toTripletForm(int rows, int cols, int matrix[rows][cols]) {
int triplet[rows * cols][3];
int k = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (matrix[i][j] != 0) {
triplet[k][0] = i;
triplet[k][1] = j;
triplet[k][2] = matrix[i][j];
k++;
printf("Row Column Value\n");
for (int i = 0; i < k; i++)
printf("%d %d %d\n", triplet[i][0], triplet[i][1], triplet[i][2]);
int main() {

int matrix[3][3] = {{0, 0, 3}, {0, 5, 0}, {0, 0, 9}};
toTripletForm(3, 3, matrix);
return 0;
OUTPUT:

Experiment- 12
AIM- Construct a code to Implement Linear Search.
Program:
#include <stdio.h>
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;
return -1;
int main() {
int arr[] = {1, 3, 5, 7, 9};
int target = 7;
int result = linearSearch(arr, 5, target);
if (result == -1) {
printf("Element not found.\n");
} else {

printf("Element found at index %d.\n", result);
return 0;
OUTPUT:

Experiment- 13
AIM- Construct a code to implement Binary Search.
Program:
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
return -1;
int main() {
int arr[] = {1, 3, 5, 7, 9};

int target = 5;
int result = binarySearch(arr, 5, target);
if (result == -1) {
printf("Element not found.\n");
} else {
printf("Element found at index %d.\n", result);
return 0;
OUTPUT:

Experiment- 14
AIM- Construct a program to Implement Selection Sort
Program:
#include <stdio.h>
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = 5;

selectionSort(arr, size);
printf("Sorted array: ");
return 0;
OUTPUT:

Experiment- 15
AIM- Construct a program to Implement Bubble Sort
Program:
#include <stdio.h>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = 7;
bubbleSort(arr, size);
Ritik Roll no 2301331550079 Department of CSE(IoT), SoCSET, NIET

return 0;
OUTPUT

Experiment- 16
AIM- Construct a program to Implement Insertion Sort
Program:
#include <stdio.h>
void insertionSort(int arr[], int size) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = key;
int main() {
int arr[] = {12, 11, 13, 5, 6};
int size = 5;
insertionSort(arr, size);

return 0;
OUTPUT

Experiment- 17
AIM- Construct a program to Implement Shell Sort
Program:
#include <stdio.h>
void shellSort(int arr[], int size) {
for (int gap = size / 2; gap > 0; gap /= 2) {
for (int i = gap; i < size; 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;
int main() {
int arr[] = {12, 34, 54, 2, 3};
int size = 5;
shellSort(arr, size);

return 0;
OUTPUT

Experiment- 18
AIM- Construct a program to Implement Counting Sort
Program:
#include <stdio.h>
#include <string.h>
void countingSort(int arr[], int size) {
int output[size];
int max = arr[0];
if (arr[i] > max)
max = arr[i];
int count[max + 1];
memset(count, 0, sizeof(count));
count[arr[i]]++;

for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
for (int i = size - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
arr[i] = output[i];
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int size = 7;
countingSort(arr, size);

return 0;
OUTPUT

Experiment- 19
AIM- Create a single linked list and perform basic operations (insertion,
deletion, traversal)
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* insert(struct Node* head, int data) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = head;
return temp;
struct Node* delete(struct Node* head, int key) {
struct Node *temp = head, *prev = NULL;
if (temp != NULL && temp->data == key) {
head = temp->next;

free(temp);
return head;
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
if (temp == NULL) return head;
prev->next = temp->next;
free(temp);
return head;
void traverse(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
printf("\n");
int main() {
struct Node* head = NULL;

head = insert(head, 10);
traverse(head);
head = delete(head, 20);
traverse(head);
return 0;
OUTPUT

Experiment- 20
AIM- Create a double linked list and perform basic operations (insertion,
deletion, traversal).
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *prev, *next;
};
temp->data = data;
temp->next = head;
temp->prev = NULL;
if (head != NULL) head->prev = temp;
return temp;
struct Node* temp = head;

while (temp && temp->data != key) temp = temp->next;
if (!temp) return head;
if (temp->prev) temp->prev->next = temp->next;
if (temp->next) temp->next->prev = temp->prev;
if (temp == head) head = temp->next;
free(temp);
return head;
while (head) {
head = head->next;
printf("\n");
int main() {
traverse(head);

traverse(head);
return 0;
OUTPUT

Experiment- 21
AIM- Create a circular linked list and perform basic operations (insertion,
deletion, traversal).
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
temp->data = data;
if (!head) {
head = temp;
temp->next = head;
return head;
struct Node* curr = head;
while (curr->next != head) curr = curr->next;
curr->next = temp;

temp->next = head;
return head;
if (!head) return NULL;
while (temp->data != key) {
if (temp->next == head) return head;
prev = temp;
temp = temp->next;
if (temp == head && temp->next == head) {
free(temp);
return NULL;
if (temp == head) {
prev = head;
while (prev->next != head) prev = prev->next;
head = temp->next;
prev->next = head;
free(temp);
} else if (temp->next == head) {

prev->next = head;
free(temp);
} else {
prev->next = temp->next;
free(temp);
return head;
if (!head) return;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
int main() {

traverse(head);
traverse(head);
return 0;
OUTPUT

Experiment- 22
AIM- Create a circular Double linked list and perform basic operations
(insertion, deletion, traversal).
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *prev, *next;
};
temp->data = data;
if (!head) {
temp->next = temp;
temp->prev = temp;
return temp;
struct Node* last = head->prev;
temp->next = head;
head->prev = temp;

temp->prev = last;
last->next = temp;
return head;
if (!head) return NULL;
while (temp->data != key) {
if (temp->next == head) return head;
prev = temp;
temp = temp->next;
if (temp->next == head && temp->prev == head) {
free(temp);
return NULL;
if (temp == head) {
prev = head->prev;
head = temp->next;
prev->next = head;
head->prev = prev;
free(temp);

} else if (temp->next == head) {
temp->prev->next = head;
head->prev = temp->prev;
free(temp);
} else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
return head;
if (!head) return;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
int main() {

traverse(head);
traverse(head);
return 0;
OUTPUT

Experiment- 23
AIM- Reverse a single linked list
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* reverse(struct Node* head) {
struct Node *prev = NULL, *curr = head, *next = NULL;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
return prev;

temp->data = data;
temp->next = head;
return temp;
while (head) {
head = head->next;
printf("\n");
int main() {
traverse(head);
head = reverse(head);
traverse(head);

return 0;
OUTPUT

Experiment- 24
AIM- Check if a linked list is palindrome.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int isPalindrome(struct Node* head) {
struct Node *slow = head, *fast = head, *prev, *second_half;
int result = 1;
if (!head || !head->next) return 1;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
prev->next = NULL;
struct Node* reverse(struct Node* head);

second_half = reverse(slow);
struct Node* temp1 = head, *temp2 = second_half;
while (temp2) {
if (temp1->data != temp2->data) {
result = 0;
break;
temp1 = temp1->next;
temp2 = temp2->next;
second_half = reverse(second_half);
prev->next = second_half;
return result;
temp->data = data;
temp->next = head;
return temp;

struct Node *prev = NULL, *curr = head, *next = NULL;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
return prev;
while (head) {
head = head->next;
printf("\n");
int main() {

traverse(head);
printf(isPalindrome(head) ? "Palindrome\n" : "Not Palindrome\n");
return 0;
OUTPUT

Experiment- 25
AIM- Reverse a double linked list.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next, *prev;
};
struct Node *temp = NULL, *curr = head;
while (curr) {
temp = curr->prev;
curr->prev = curr->next;
curr->next = temp;
curr = curr->prev;
return temp ? temp->prev : head;

temp->data = data;
temp->next = head;
temp->prev = NULL;
if (head) head->prev = temp;
return temp;
while (head) {
head = head->next;
printf("\n");
int main() {
traverse(head);

head = reverse(head);
traverse(head);
return 0;
OUTPUT

Experiment- 26
AIM- Find the middle element of a single linked list
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
temp->data = data;
temp->next = head;
return temp;
int findMiddle(struct Node* head) {
struct Node *slow = head, *fast = head;
slow = slow->next;

return slow->data;
int main() {
printf("Middle Element: %d\n", findMiddle(head));
return 0;
OUTPUT

Experiment- 27
AIM- Find the middle element of a double linked list.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
temp->data = data;
temp->next = head;
temp->prev = NULL;
if (head) head->prev = temp;
return temp;
int findMiddle(struct Node* head) {

slow = slow->next;
return slow->data;
int main() {
printf("Middle Element: %d\n", findMiddle(head));
return 0;
OUTPUT

Experiment- 28
AIM- Merge two sorted single linked lists.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
temp->data = data;
temp->next = head;
return temp;
struct Node* merge(struct Node* l1, struct Node* l2) {
struct Node* result = NULL;
if (!l1) return l2;
if (!l2) return l1;

if (l1->data <= l2->data) {
result = l1;
result->next = merge(l1->next, l2);
} else {
result = l2;
result->next = merge(l1, l2->next);
return result;
while (head) {
head = head->next;
printf("\n");
int main() {
struct Node *l1 = NULL, *l2 = NULL;
l1 = insert(l1, 30);

l2 = insert(l2, 5);
struct Node* mergedList = merge(l1, l2);
traverse(mergedList);
return 0;
OUTPUT

Experiment- 29
AIM- Detect and remove a loop in a circular linked list.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void detectAndRemoveLoop(struct Node* head) {
slow = slow->next;
if (slow == fast) {
slow = head;
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;

fast->next = NULL;
return;
temp->data = data;
temp->next = head;
return temp;
while (head) {
head = head->next;
printf("\n");
int main() {

head->next->next->next = head; // Creating a loop for demonstration
detectAndRemoveLoop(head);
traverse(head);
return 0;
OUTPUT

Experiment- 30
AIM- Construct a code to add two polynomials using linked list
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int coeff, pow;
struct Node* next;
};
struct Node* insert(struct Node* head, int coeff, int pow) {
temp->coeff = coeff;
temp->pow = pow;
temp->next = head;
return temp;
struct Node* addPolynomials(struct Node* p1, struct Node* p2) {
struct Node* result = NULL;
while (p1 || p2) {

if (!p1 || (p2 && p1->pow < p2->pow)) {
result = insert(result, p2->coeff, p2->pow);
p2 = p2->next;
} else if (!p2 || (p1 && p1->pow > p2->pow)) {
result = insert(result, p1->coeff, p1->pow);
p1 = p1->next;
} else {
result = insert(result, p1->coeff + p2->coeff, p1->pow);
p1 = p1->next;
p2 = p2->next;
return result;
void printPolynomial(struct Node* head) {
while (head) {
printf("%dx^%d ", head->coeff, head->pow);
head = head->next;
printf("\n");

int main() {
struct Node *p1 = NULL, *p2 = NULL;
p1 = insert(p1, 5, 2);
p1 = insert(p1, 4, 1);
p2 = insert(p2, 3, 1);
p2 = insert(p2, 2, 0);
struct Node* result = addPolynomials(p1, p2);
printPolynomial(result);
return 0;
OUTPUT

Experiment- 31
AIM- Construct a program to Implement stack using array
Program:
#include <stdio.h>
#define SIZE 100
int stack[SIZE], top = -1;
void push(int val) {
if (top < SIZE - 1)
stack[++top] = val;
int pop() {
return top >= 0 ? stack[top--] : -1;
int peek() {
return top >= 0 ? stack[top] : -1;
int isEmpty() {

return top == -1;
int main() {
push(10);
push(20);
printf("%d", pop()); // Output: 20
OUTPUT

Experiment- 32
AIM- Construct a program to Implement stack using a linked list
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;
void push(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = top;
top = newNode;
int pop() {

if (top == NULL) return -1;
struct Node* temp = top;
int poppedValue = top->data;
top = top->next;
free(temp);
return poppedValue;
int peek() {
return top ? top->data : -1;
int isEmpty() {
return top == NULL;
int main() {
push(10);
push(20);
printf("%d", pop()); // Output: 20
OUTPUT

Experiment- 33
AIM- Construct a code to Infix to postfix conversion using a stack
Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
if (top < MAX - 1)
stack[++top] = c;
char pop() {
if (top == -1) return -1;
return stack[top--];

int precedence(char c) {
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
return 0;
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
void infixToPostfix(char* infix, char* postfix) {
int i = 0, k = 0;
while (infix[i]) {
if (isalnum(infix[i]))
postfix[k++] = infix[i];
else if (infix[i] == '(')
push(infix[i]);
else if (infix[i] == ')') {
while (top != -1 && stack[top] != '(')
postfix[k++] = pop();
top--; // Pop '('
} else if (isOperator(infix[i])) {

while (top != -1 && precedence(stack[top]) >= precedence(infix[i]))
push(infix[i]);
i++;
while (top != -1)
postfix[k] = '\0';
int main() {
char infix[MAX], postfix[MAX];
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("%s", postfix);
OUTPUT

Experiment- 34
AIM- Construct a code for Balanced parentheses checker using a stack
Program:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
if (top < MAX - 1) stack[++top] = c;
char pop() {
int isBalanced(char* expr) {
for (int i = 0; expr[i]; i++) {

if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[') {
push(expr[i]);
} else if (expr[i] == ')' || expr[i] == '}' || expr[i] == ']') {
char topChar = pop();
if ((expr[i] == ')' && topChar != '(') ||
(expr[i] == '}' && topChar != '{') ||
(expr[i] == ']' && topChar != '[')) {
return 0;
return top == -1;
int main() {
char expr[MAX];
scanf("%s", expr);
if (isBalanced(expr)) printf("Balanced");
else printf("Not Balanced");
OUTPUT

Experiment- 35
AIM- Implement Reverse a string using a stack.
Program:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
if (top < MAX - 1) stack[++top] = c;
char pop() {
void reverseString(char* str) {

for (int i = 0; str[i]; i++) {
push(str[i]);
for (int i = 0; str[i]; i++) {
str[i] = pop();
int main() {
char str[MAX];
scanf("%s", str);
reverseString(str);
printf("%s", str);
OUTPUT

Experiment- 36
AIM- Implement Binary Search using Recursion.
Program:
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
if (low > high) return -1;
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] > key) return binarySearch(arr, low, mid - 1, key);
else return binarySearch(arr, mid + 1, high, key);
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int key = 4;
printf("%d", binarySearch(arr, 0, n - 1, key)); // Output: 3
OUTPUT

Experiment- 37
AIM- Construct a python program to print Fibonacci Series using Recursion.
Program:
def fibonacci(n):
if n <= 0:
return []
elif n == 1:
return [0]
elif n == 2:
return [0, 1]
else:
fib_series = fibonacci(n - 1)
fib_series.append(fib_series[-1] + fib_series[-2])
return fib_series
n = int(input("Enter the number of terms: "))
print(fibonacci(n))
OUTPUT

Experiment- 38
AIM- Construct a code to implement Tower of Hanoi.
Program:
#include <stdio.h>
void towerOfHanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
towerOfHanoi(n - 1, from, aux, to);
printf("Move disk %d from %c to %c\n", n, from, to);
towerOfHanoi(n - 1, aux, to, from);
int main() {
int n = 3;
towerOfHanoi(n, 'A', 'C', 'B');
OUTPUT -

Experiment- 39
AIM- Construct a program to Implement queue using array
Program:
#include <stdio.h>
#define SIZE 5
int queue[SIZE], front = -1, rear = -1;
void enqueue(int val) {
if (rear == SIZE - 1) printf("Queue Full\n");
else if (front == -1) front = rear = 0;
else queue[++rear] = val;
int dequeue() {
if (front == -1) return -1;
int val = queue[front];
if (front == rear) front = rear = -1;
else front++;
return val;

int main() {
enqueue(10);
enqueue(20);
printf("%d", dequeue()); // Output: 10
OUTPUT

Experiment- 40
AIM- Construct a code for Implementing a circular queue.
Program:
#include <stdio.h>
#define SIZE 5
int queue[SIZE], front = -1, rear = -1;
void enqueue(int val) {
if ((rear + 1) % SIZE == front) {
printf("Queue Full\n");
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = val;
int dequeue() {
if (front == -1) {
printf("Queue Empty\n");
return -1;

} else {
int val = queue[front];
if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % SIZE;
return val;
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printf("%d\n", dequeue()); // Output: 10
enqueue(40);
enqueue(50);
enqueue(60); // Queue Full
printf("%d\n", dequeue()); // Output: 20
OUTPUT

Experiment- 41
AIM- Construct a program to Implement queue using stack
Program:
#include <stdio.h>
#define MAX 100
int stack1[MAX], stack2[MAX], top1 = -1, top2 = -1;
void push1(int value) {
stack1[++top1] = value;
int pop1() {
if (top1 == -1)
return -1;
return stack1[top1--];
void push2(int value) {
stack2[++top2] = value;
int pop2() {

if (top2 == -1) {
while (top1 != -1) {
push2(pop1());
if (top2 == -1)
return -1;
return stack2[top2--];
int main() {
push1(10);
push1(20);
printf("Queue: %d\n", pop2());
push1(30);
return 0;
OUTPUT

Experiment- 42
AIM- Construct a program to Implement priority queue
Program:
#include <stdio.h>
#define MAX 10
int pq[MAX], size = 0;
void insert(int value) {
int i = size++;
while (i && pq[(i - 1) / 2] < value) {
pq[i] = pq[(i - 1) / 2];
i = (i - 1) / 2;
pq[i] = value;
int delete() {
if (size == 0)
return -1;
int root = pq[0];
pq[0] = pq[--size];
int i = 0, left, right, max;

while (i * 2 + 1 < size) {
left = 2 * i + 1;
right = 2 * i + 2;
max = i;
if (left < size && pq[left] > pq[max])
max = left;
if (right < size && pq[right] > pq[max])
max = right;
if (max == i)
break;
int temp = pq[i];
pq[i] = pq[max];
pq[max] = temp;
i = max;
return root;
int main() {
insert(10);
insert(20);
insert(15);
printf("Priority Queue: %d\n", delete());

printf("Priority Queue: %d\n", delete());
return 0;
OUTPUT

Experiment- 43
AIM- Construct a program to Implement double ended queue
Program:
#include <stdio.h>
#define MAX 10
int dq[MAX], front = -1, rear = -1;
void insertFront(int value) {
if (front == 0)
else {
if (front == -1)
front = rear = 0;
else
dq[--front] = value;
void insertRear(int value) {
if (rear == MAX - 1)
else {

if (rear == -1)
front = rear = 0;
else
dq[++rear] = value;
int deleteFront() {
if (front == -1)
return -1;
int val = dq[front];
if (front == rear)
front = rear = -1;
else
front++;
return val;
int deleteRear() {
if (rear == -1)
return -1;
int val = dq[rear];
if (front == rear)

front = rear = -1;
else
rear--;
return val;
int main() {
insertRear(10);
insertRear(20);
insertFront(30);
printf("Deque: %d\n", deleteFront());
printf("Deque: %d\n", deleteRear());
return 0;
OUTPUT

Experiment- 44
AIM- Construct a program to Implement Merge Sort with recursion
Program:
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[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] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
while (i < n1)
arr[k++] = L[i++];

while (j < n2)
arr[k++] = R[j++];
void mergeSort(int arr[], int left, int right) {
if (left < right) {
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, 5);
for (int i = 0; i < 6; i++)
return 0;
OUTPUT

Experiment- 45
AIM- Construct a program to Implement Quick Sort with recursion
Program:
#include <stdio.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
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 arr[] = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, 5);
for (int i = 0; i < 6; i++)
return 0;
OUTPUT

Experiment- 46
AIM- Construct a program to Implement Merge Sort using iteration
Program:
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[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] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
while (i < n1)
arr[k++] = L[i++];
while (j < n2)

arr[k++] = R[j++];
void mergeSort(int arr[], int n) {
for (int curr_size = 1; curr_size < n; curr_size *= 2) {
for (int left = 0; left < n - 1; left += 2 * curr_size) {
int mid = left + curr_size - 1;
int right = ((left + 2 * curr_size - 1) < (n - 1)) ? (left + 2 * curr_size - 1) : (n

- 1);
if (mid < right)
merge(arr, left, mid, right);
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 6);
for (int i = 0; i < 6; i++)
return 0;
OUTPUT

Experiment- 47
AIM- Construct a program to Implement Quick Sort using iteration
Program:
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
int partition(int arr[], int low, int high) {
int 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(int arr[], int low, int high) {
int stack[high - low + 1];
int top = -1;
stack[++top] = low;
stack[++top] = high;
while (top >= 0) {
high = stack[top--];
low = stack[top--];
int p = partition(arr, low, high);
if (p - 1 > low) {
stack[++top] = low;
stack[++top] = p - 1;
if (p + 1 < high) {
stack[++top] = p + 1;
stack[++top] = high;

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
return 0;
OUTPUT

Experiment- 48
AIM- Construct a program to Implement fractional knapsack
Program:
#include <stdio.h>
struct Item {
int value;
int weight;
float ratio;
};
void swap(struct Item* a, struct Item* b) {
struct Item temp = *a;
*a = *b;
*b = temp;
void sort(struct Item arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i].ratio < arr[j].ratio)

float knapsack(struct Item arr[], int n, int W) {
sort(arr, n);
int currentWeight = 0;
float finalValue = 0.0;
for (int i = 0; i < n; i++) {
if (currentWeight + arr[i].weight <= W) {
currentWeight += arr[i].weight;
finalValue += arr[i].value;
} else {
int remain = W - currentWeight;
finalValue += arr[i].value * ((float)remain / arr[i].weight);
break;
return finalValue;
int main() {

struct Item arr[] = {{60, 10, 6.0}, {100, 20, 5.0}, {120, 30, 4.0}};
int W = 50;
printf("Maximum value we can obtain = %.2f", knapsack(arr, n, W));
return 0;
OUTPUT

Experiment- 49
AIM- Construct a program to Implement Activity selection problem
Program:
#include <stdio.h>
struct Activity {
int start;
int finish;
};
void sort(struct Activity arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i].finish > arr[j].finish) {
struct Activity temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

void activitySelection(struct Activity arr[], int n) {
sort(arr, n);
int i = 0;
printf("Selected Activities: \n");
printf("Activity %d: (%d, %d)\n", i + 1, arr[i].start, arr[i].finish);
for (int j = 1; j < n; j++) {
if (arr[j].start >= arr[i].finish) {
printf("Activity %d: (%d, %d)\n", j + 1, arr[j].start, arr[j].finish);
i = j;
int main() {
struct Activity arr[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
activitySelection(arr, n);
return 0;
OUTPUT

Experiment- 50
AIM- Construct a program to Implement Job scheduling problem
Program:
#include <stdio.h>
struct Job {
int id;
int deadline;
int profit;
};
void swap(struct Job* a, struct Job* b) {
struct Job temp = *a;
*a = *b;
*b = temp;
void sort(struct Job arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i].profit < arr[j].profit)

void jobScheduling(struct Job arr[], int n) {
sort(arr, n);
int result[n];
int slot[n];
for (int i = 0; i < n; i++)
slot[i] = -1;
for (int i = 0; i < n; i++) {
for (int j = arr[i].deadline - 1; j >= 0; j--) {
if (slot[j] == -1) {
slot[j] = i;
result[i] = 1;
break;
printf("Scheduled Jobs: \n");

for (int i = 0; i < n; i++) {
if (result[i] == 1)
printf("Job %d with profit %d\n", arr[i].id, arr[i].profit);
int main() {
struct Job arr[] = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
jobScheduling(arr, n);
return 0;
OUTPUT

Divyanshu dsa file1

Uploaded by

Copyright:

Available Formats

Divyanshu dsa file1

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

Divyanshu dsa file1

Uploaded by

Copyright:

Available Formats

NOIDA INSTITUTE OF ENGINEERING AND TECHNOLOGY

DATA STRUCTURE & ALGORITHMS-1

Submitted By: Submitted To:

Divyanshu Ms. Neha Bhati

Course Code BCSE0301 LTP Credit

Course Title Data Structure & Algorithm -1 0 0 4 2

Course Objective: Learn to implement linear data structures.

Course Outcomes (CO)

Course outcome: After completion of this course Bloom’s Knowledge

Implementing Single and Multi-dimensional array with

7 Construct a Code to count the occurrence of a specific CO1

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

37 Construct a python program to print Fibonacci Series CO2

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

void selectionSort(int arr[], int n) {

int i, j, min_idx, temp;

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

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

if (arr[j] < arr[min_idx])

void bubbleSort(int arr[], int n) {

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

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

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

if (arr[j] > arr[j+1]) {

void insertionSort(int arr[], int n) {

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

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

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

int n = 1000, arr[1000], i;

clock_t start, end;

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

arr[i] = rand() % 1000;

time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Selection Sort: %f seconds\n", time_used);

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

arr[i] = rand() % 1000;

time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Bubble Sort: %f seconds\n", time_used);

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

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

arr[i] = rand() % 1000;

time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Insertion Sort: %f seconds\n", time_used);

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

void linearSearch(int arr[], int n, int x) {

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

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]) {

int temp = arr[j];

Ritik Roll no 2301331550079 Department of CSE(IoT), BCSE0301, NIET

void binarySearch(int arr[], int n, int x) {

int left = 0, right = n - 1;

while (left <= right) {

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

if (arr[mid] < x) left = mid + 1;

else right = mid - 1;

int sizes[] = {1000, 5000, 10000, 50000, 100000};

int numSizes = sizeof(sizes) / sizeof(sizes[0]);

int arr = (int )malloc(n * sizeof(int));