3.

1 a) Recursive Binary Search in C:

int binarySearch(int arr[], int low, int high, int key) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
return binarySearch(arr, mid + 1, high, key);
}
return -1;
}
b) Deleting a Node by Value in Singly Linked List:
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head, *prev;
if (temp != NULL && temp->data == key) { // Delete head node
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
free(temp);
}
c) push() and pop() for Static Stack:
struct Stack {
int top;
int arr[MAX_SIZE];
};

void push(struct Stack* stack, int item) {

if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack->arr[++stack->top] = item;
printf("%d pushed to stack\n", item);
}

int pop(struct Stack* stack) {

if (stack->top == -1) {
printf("Stack Underflow\n");
return -1;
}
return stack->arr[stack->top--];
}
3.2 write a c function for deleting element from singly linked list
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head, *prev;
// If head node itself holds the key to be deleted
if (temp != NULL && temp->data == key) {
*head = temp->next; // Changed head
free(temp); // free old head
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL)
return;
// Unlink the node from linked list
prev->next = temp->next;
// Free memory
free(temp);
}
// Function to push a new node at the beginning
void push(struct Node** head_ref, int new_data) {
/* 1 Allocate Node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* 2 Put in the data */
new_node->data = new_data;
/* 3 Make next of new Node as head */
new_node->next = (*head_ref);
/* 4 Move the head to point to new Node */
(*head_ref) = new_node;
}
// A utility function to print a linked list
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
printf("Created Linked List: ");
printList(head);
deleteNode(&head, 1);

printf("\nLinked List after Deletion of 1: ");

printList(head);
return 0;
}
3.3 write a c function to reverse singly linked list
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void reverseList(struct Node** head_ref) {
struct Node* prev = NULL, *current = *head_ref, *next;

while (current != NULL) {

// Store next
next = current->next;

// Reverse current node's pointer

current->next = prev;

// Move pointers one position ahead

prev = current;
current = next;
}
*head_ref = prev;
}
// Function to push a new node at the beginning
void push(struct Node** head_ref, int new_data) {
/* 1 Allocate Node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

/* 2 Put in the data */

new_node->data = new_data;

/* 3 Make next of new Node as head */

new_node->next = (*head_ref);

/* 4 Move the head to point to new Node */

(*head_ref) = new_node;
}

// Function to print linked list

void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverseList(&head);
printf("\nReversed linked list \n");
printList(head);
return 0;
}
3.4 write a program to search an element using linear search algorithm
#include <stdio.h>
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i; // Element found at index i
}
}
return -1; // Element not found
}
int main() {
int arr[] = {23, 45, 12, 90, 56, 78, 34, 21};
int n = sizeof(arr) / sizeof(arr[0]);
int x;
printf("Enter the element to search: ");
scanf("%d", &x);
int result = linearSearch(arr, n, x);
if (result == -1) {
printf("Element not found in the array.\n");
} else {
printf("Element found at index %d\n", result);
}
return 0;
}
write a c function to reverse a string using stack
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
struct Stack {
int top;
char items[MAX_SIZE];
};
void push(struct Stack* stack, char item) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack->items[++stack->top] = item;
}
char pop(struct Stack* stack) {
if (stack->top == -1) {
printf("Stack Underflow\n");
return '\0';
}
return stack->items[stack->top--];
}
void reverseString(char* str) {
int len = strlen(str);
struct Stack stack;
[Link] = -1;
// Push characters onto the stack
for (int i = 0; i < len; i++) {
push(&stack, str[i]);
}
// Pop characters from the stack and assign them back to the string
for (int i = 0; i < len; i++) {
str[i] = pop(&stack);
}
}

int main() {
char str[MAX_SIZE];
3.5
printf("Enter a string: ");
fgets(str, MAX_SIZE, stdin);

reverseString(str);

printf("Reversed string: %s", str);

return 0;
}
write a c function to delete a node from singly circular linked list at any position
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void deleteNode(struct Node** head, int position) {
if (*head == NULL) {
return; // Empty list
}
struct Node* temp = *head;
struct Node* prev = NULL;

if (position == 0) { // Delete the first node

*head = temp->next;
temp->next = NULL;
free(temp);
return;
}
for (int i = 0; i < position - 1; i++) {
prev = temp;
temp = temp->next;
}
struct Node* nextNode = temp->next;
prev->next = nextNode;
temp->next = NULL;
free(temp);
}
// Function to create a new node
struct Node* newNode(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = new_node; // Circular link
return new_node;
}
// Function to print the linked list
void printList(struct Node* head) {
if (head == NULL) {
return;
}

struct Node* temp = head;

do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);

printf("\n");
}
int main() {
struct Node* head = newNode(12);
head->next = newNode(15);
head->next->next = newNode(10);
 3.6
Head->next->next->next = head; // Create a circular link
printf("Original Circular Linked List: ");
printList(head);
int position = 2; // Delete the node at position 2 (0-based indexing)
deleteNode(&head, position);
printf("Circular Linked List after deletion: ");
printList(head);
return 0;
}
Define data structure and explain types of data structure
A data structure is a systematic way of organizing and storing data in a computer's memory so that it can be accessed and modified
efficiently. It provides a blueprint for how data can be arranged and manipulated.
Types of Data Structures
Primitive Data Structures:
Basic building blocks of data structures.
Examples: Integer, Float, Character, Boolean.
Non-Primitive Data Structures:
Derived from primitive data structures.
Categorized into:
Linear Data Structures:
Elements are arranged sequentially.
Examples: Array, Linked List, Stack, Queue.
Non-Linear Data Structures:
Elements are not arranged sequentially.
Examples: Tree, Graph.
Choice of Data Structure:
The choice of data structure depends on the specific requirements of the application, such as:
Access Patterns: How often data needs to be accessed and in what order.
Memory Usage: The amount of memory required to store the data.
Time Complexity: The efficiency of operations like insertion, deletion, and search.
By understanding these data structures and their properties, we can design efficient and effective algorithms and software systems.
withe a c function to create doubly linked list
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
struct Node* prev;
};

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = newNode->prev = NULL;
return newNode;
}

void insertAtBeginning(struct Node** head_ref, int data) {

struct Node* newNode = createNode(data);
if (*head_ref == NULL) {
*head_ref = newNode;
newNode->next = newNode;
newNode->prev = newNode;
} else {
newNode->next = *head_ref;
newNode->prev = (*head_ref)->prev;
(*head_ref)->prev->next = newNode;
(*head_ref)->prev = newNode;
*head_ref = newNode;
}
}
3.7
void insertAtEnd(struct Node** head_ref, int data) {
struct Node* newNode = createNode(data);
if (*head_ref == NULL) {
*head_ref = newNode;
newNode->next = newNode;
newNode->prev = newNode;
} else {
newNode->next = *head_ref;
newNode->prev = (*head_ref)->prev;
(*head_ref)->prev->next = newNode;
(*head_ref)->prev = newNode;
}
}

void printList(struct Node* head) {

if (head == NULL) {
return;
}

struct Node* temp = head;

do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}

int main() {
struct Node* head = NULL;

insertAtBeginning(&head, 10);
insertAtEnd(&head, 20);
insertAtBeginning(&head, 5);
insertAtEnd(&head, 30);

printList(head);

return 0;
}
Explain with example generalized linked list in 150 words
Generalized Linked List
A generalized linked list, also known as a heterogeneous linked list, is a flexible data structure where nodes can have different types
of data. Unlike traditional linked lists, which have nodes of a fixed structure, generalized linked lists allow for nodes with varying
numbers and types of data fields.
Example:
Consider a university database where each node represents a person. The node structure might include:
Name (string)
Age (integer)
Department (string)
Courses Enrolled (array of strings)
Next (pointer to the next node)
In this case, the Courses Enrolled field is an array, making it a variable-length data structure within the node. This allows for
flexibility in representing different types of people (students, faculty, staff) with varying information.
Advantages:
Flexibility: Can accommodate diverse data structures within a single linked list.
Efficiency: Can be optimized for specific data access patterns.
Dynamic Memory Allocation: Can efficiently allocate memory for nodes of different sizes.

Disadvantages:
Complexity: More complex to implement and manage compared to traditional linked lists.
Memory Overhead: May require additional memory for storing information about node structures. 3. Generalized linked lists are
powerful tools for representing complex data relationships, especially when dealing with heterogeneous data. By carefully designing
the node structure, you can create efficient and versatile data structures tailored to specific application needs.
3.8
write a shortnote on priority queue
Priority Queue
A priority queue is a data structure that stores elements along with their associated priorities. Elements with higher priority are
served before elements with lower priority. It's a common data structure used in various algorithms and applications.
Key Operations:
Insert: Adds an element with a specific priority.
Extract-Max (or Extract-Min): Removes and returns the element with the highest (or lowest) priority.
Peek: Returns the element with the highest (or lowest) priority without removing it.
Implementation:
Priority queues can be implemented using various data structures:
Array-Based Implementation:
Elements are stored in an array.
Insertion and deletion operations can be inefficient, especially for large priority queues.
Heap-Based Implementation:
A heap (usually a binary heap) is used to efficiently maintain the priority order.
Insertion and deletion operations have a time complexity of O(log n).
This is the most common and efficient implementation.
Applications:
Scheduling algorithms: Prioritizing tasks based on their importance.
Event-driven simulations: Handling events in the order of their occurrence time.
Graph algorithms: Implementing algorithms like Dijkstra's shortest path algorithm.
Operating systems: Managing processes and threads based on their priorities.
By understanding the concepts of priority queues, you can effectively design and implement algorithms that require efficient
handling of prioritized data.
Define the following time complexity, omega notation and doubly ended queue
Time complexity is a measure of how long an algorithm takes to run as a function of the input size. It's a crucial factor in evaluating
the efficiency of a data structure and the algorithms that operate on it.
Why is it important?
Performance Prediction: It helps predict how an algorithm's performance will scale with increasing input size.
Algorithm Selection: It aids in choosing the most efficient algorithm for a given task.
Optimization: It guides optimization efforts to improve the performance of algorithms and data structures.
Omega Notation (Ω)
Omega notation is used to describe the lower bound of an algorithm's running time. It represents the best-case complexity of an
algorithm. In simpler terms, it tells us the minimum amount of time an algorithm will take to complete a given task.
Mathematical Representation:
Ω(g(n)) = {f(n): there exist positive constants c0 and c1, such that 0 ≤ c0g(n) ≤ f(n) for all n ≥ c1}
Interpretation:
f(n): The actual running time of the algorithm.
g(n): A function that represents the lower bound.
c0 and c1: Positive constants.
If a function f(n) is Ω(g(n)), it means that for sufficiently large values of n, f(n) will always be greater than or equal to c0 * g(n).
Doubly Ended Queue (Deque)
A deque, short for double-ended queue, is a linear data structure that allows insertion and deletion of elements from both ends: 1
the front and the rear. This flexibility makes it useful for various applications.
Deques can be implemented using arrays or linked lists.
Array-Based Implementation:
Fixed Size: The array has a fixed size, limiting the number of elements that can be stored.
Efficient for Fixed-Size Deques: Operations like push and pop can be performed in constant time, O(1).
Linked List-Based Implementation:
Dynamic Size: The size of the deque can grow or shrink as needed.
Efficient for Dynamic-Size Deques: Operations like push and pop can be performed in constant time, O(1).
Key Operations:
Push Front: Adds an element to the front of the deque.
Pop Front: Removes an element from the front of the deque.
Push Back: Adds an element to the rear of the deque.
Pop Back: Removes an element from the rear of the deque.
There are two main types of deques based on the restrictions on insertion and deletion operations:
1. Input-Restricted Deque:
Insertion: Elements can be inserted only from one end (either front or rear).
Deletion: Elements can be deleted from both ends.
2. Output-Restricted Deque: Insertion: Elements can be inserted from both ends.
Deletion: Elements can be deleted from only one end (either front or rear).
These restrictions can be useful in specific scenarios where certain operations are more frequent or necessary than others.
3.9 List advantages and disadvantages of circular queue
Advantages of Circular Queue:
Efficient Utilization of Space: Unlike linear queues, circular queues can utilize all the available space in the array. This is because
the rear can wrap around to the beginning of the array once it reaches the end.
Simple Implementation: The implementation of a circular queue is relatively straightforward, involving a few simple operations
like enqueue, dequeue, and checking for empty and full conditions.
Efficient Operations: Basic operations like enqueue and dequeue can be performed in constant time, O(1), making it efficient for
many applications.

Disadvantages of Circular Queue:

Complexity in Implementation: While the concept is simple, the implementation can be slightly more complex than a linear queue
due to the circular nature and the need to handle boundary conditions.
Fixed Size: The size of a circular queue is fixed at the time of array allocation. If the queue needs to accommodate more elements
than the initial size, it may require resizing, which can be inefficient.
Potential for Overwriting: If not implemented carefully, there's a risk of overwriting existing elements in the queue, especially
when the queue is nearly full.
what is linear queue? How to implement it? explain in 150 words
Linear Queue
A linear queue is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. 1 This means the first element
added to the queue is the first one to be removed. 2
1. Creating a Queue in C | DigitalOcean
Source icon
[Link]
2. What Is a First-in-first-out (FIFO) Queue?
Source icon
[Link]
Implementation:
A linear queue can be implemented using an array or a linked list. Here's a basic implementation using an array:
#include <stdio.h>
#define MAX 100
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int x) {
if (rear == MAX - 1) {
printf("Queue Overflow\n");
return;
}
if (front == -1) {
front = rear = 0;
} else {
rear = rear + 1;
}
queue[rear] = x;
printf("%d enqueued to queue\n", x);
}
int dequeue() {
if (front == -1) {
printf("Queue Underflow\n");
return -1;
}
int x = queue[front];
if (front == rear) {
front = rear = -1;
} else {
front = front + 1;
}
return x;
}
Explanation:
Front and Rear Pointers: Two pointers, front and rear, are used to keep track of the front and rear ends of the queue, respectively.
Enqueue Operation:
Checks for overflow.
If the queue is empty, both front and rear are initialized to 0.
3.10
 Otherwise, the rear pointer is incremented, and the new element is added to the rear position.
Dequeue Operation:
Checks for underflow.
Removes the element at the front position.
If the queue becomes empty after the removal, both front and rear are reset to -1.
Otherwise, the front pointer is incremented.

This implementation provides a basic understanding of how a linear queue works. However, it's important to consider the
limitations of fixed-size arrays and explore more advanced implementations like circular queues and linked list-based queues to
overcome these limitations.
List the various sequential search. Explain any one with example
Sequential Search
Sequential search, also known as linear search, is a simple search algorithm that iterates through a list of elements one by one until
the desired element is found or the end of the list is reached.
Example:
#include <stdio.h>

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

for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i; // Element found at index i
}
}
return -1; // Element not found
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);

int result = linearSearch(arr, n, x);

(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Explanation:
Iterate through the array: The for loop iterates through each element of the array, starting from the first index (0).
Compare with the target: In each iteration, the current element is compared with the target value x.
Return index or -1: If a match is found, the index of the element is returned. If the entire array is searched without finding a
match, -1 is returned to indicate that the element is not present.

Time Complexity:
The time complexity of sequential search is O(n) in the worst case, where n is the number of elements in the array. This means that
1 in the worst-case scenario, the algorithm will have to examine every element in the array to find the target element or determine
that it's not present.