1. A bank queue is implemented to manage customer transaction amounts.

The program
calculates the total of all customer transactions in the queue to generate a daily report. Write a
C program to calculate the sum of the elements in a queue.
Expected Output:
Queue elements are: 1 2 3 4 5
Sum of the elements in the queue is: 15
#include <stdio.h>
#define MAX 100 // Maximum size of the queue

// Queue structure
typedef struct {
int data[MAX];
int front;
int rear;
} Queue;

// Initialize the queue

void initializeQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}

// Check if the queue is empty

int isEmpty(Queue *q) {
return (q->front == -1);
}

// Check if the queue is full

int isFull(Queue *q) {
return (q->rear == MAX - 1);
}

// Enqueue an element into the queue

void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full. Cannot add element.\n");
return;
}
if (q->front == -1) {
q->front = 0; // Set front to 0 if the queue was empty
}
q->data[++(q->rear)] = value;
}

// Display all elements in the queue

void displayQueue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements are: ");
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->data[i]);
}
printf("\n");
}

// Calculate the sum of elements in the queue

int calculateSum(Queue *q) {
if (isEmpty(q)) {
return 0; // Return 0 if the queue is empty
}
int sum = 0;
for (int i = q->front; i <= q->rear; i++) {
sum += q->data[i];
}
return sum;
}

// Main function
int main() {
Queue q;
initializeQueue(&q);

// Enqueue some elements

enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
enqueue(&q, 5);

// Display the queue

displayQueue(&q);

// Calculate and display the sum of elements

int sum = calculateSum(&q);
printf("Sum of the elements in the queue is: %d\n", sum);

return 0;
}
2. A playlist application uses a linked list to manage songs. The user requests to reverse the order
of songs in the playlist to play them in the opposite sequence. Implement a program to reverse
a linked list.
Original Linked List: 2 -> 7 -> 3 -> NULL
Reversed Linked List: 3 -> 7 -> 2 -> NULL
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int data;
struct Node *next;
} Node;

// Function to create a new node

Node* createNode(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to append a node to the linked list

void append(Node **head, int data) {
Node *newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node *temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

// Function to display the linked list

void display(Node *head) {
Node *temp = head;
while (temp != NULL) {
printf("%d", temp->data);
if (temp->next != NULL) {
printf(" -> ");
}
temp = temp->next;
}
printf(" -> NULL\n");
}

// Function to reverse the linked list

Node* reverse(Node *head) {
Node *prev = NULL;
Node *current = head;
Node *next = NULL;
while (current != NULL) {
next = current->next; // Store next node
current->next = prev; // Reverse current node's pointer
prev = current; // Move prev to current
current = next; // Move to next node
}
return prev; // New head of the reversed list
}

// Main function
int main() {
Node *head = NULL;

// Create the linked list: 2 -> 7 -> 3 -> NULL

append(&head, 2);
append(&head, 7);
append(&head, 3);

printf("Original Linked List: ");

display(head);

// Reverse the linked list

head = reverse(head);

printf("Reversed Linked List: ");

display(head);

return 0;
}
3. A shopping cart application calculates the total cost of items. The array stores the prices of items
in the cart, and the program computes the total sum of the cart contents..Write a C program to
find the sum of elements in an array
Sum of elements: 30
#include <stdio.h>
// Function to calculate the sum of elements in an array
int calculateSum(int arr[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
}
return sum;
}

// Main function
int main() {
// Array to store item prices
int cart[] = {5, 10, 15}; // Example prices
int size = sizeof(cart) / sizeof(cart[0]); // Calculate the number of elements

printf("Items in the cart: ");

for (int i = 0; i < size; i++) {
printf("%d ", cart[i]);
}
printf("\n");

// Calculate the sum of elements

int total = calculateSum(cart, size);

// Display the total

printf("Sum of elements: %d\n", total);

return 0;
}
4. A file system manager organizes directories and files in a binary tree. The program calculates
the height of the tree to determine the maximum depth of the file structure Write a C program
to find the height of a binary tree.
Height of the binary tree: 2
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a tree node

typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;

// Function to create a new node

Node* createNode(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to calculate the height of a binary tree

int calculateHeight(Node *root) {
if (root == NULL) {
return -1; // Height of an empty tree is -1
}
int leftHeight = calculateHeight(root->left);
int rightHeight = calculateHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Main function
int main() {
// Constructing a simple binary tree
Node *root = createNode(1); // Level 0
root->left = createNode(2); // Level 1
root->right = createNode(3); // Level 1
root->left->left = createNode(4); // Level 2
root->left->right = createNode(5); // Level 2

// Calculate the height of the binary tree

int height = calculateHeight(root);

// Display the height

printf("Height of the binary tree: %d\n", height);

return 0;
}
5. A library system manages a list of books. The program allows the librarian to insert a new book
at the beginning of the list, updating the order of books currently available. Write a program in
C to insert a new node at the beginning of a Singly Linked List.
Test Data and Expected Output :
Input the number of nodes : 3
Input data for node 1 : 5 , Input data for node 2 : 6, Input data for node 3 : 7

Data entered in the list are :

Data = 5 , Data = 6 , Data = 7
a. Input data to insert at the beginning of the list : 4
Data after inserted in the list are :
b. Data = 4 , Data = 5 ,Data = 6, Data = 7
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node

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

// Function to create a new node

Node* createNode(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to insert a node at the beginning

void insertAtBeginning(Node **head, int data) {
Node *newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

// Function to display the linked list

void displayList(Node *head) {
Node *temp = head;
while (temp != NULL) {
printf("Data = %d", temp->data);
if (temp->next != NULL) {
printf(" , ");
}
temp = temp->next;
}
printf("\n");
}

// Main function
int main() {
Node *head = NULL;
int n, data;

// Input the number of nodes

printf("Input the number of nodes: ");
scanf("%d", &n);

// Create the initial list

for (int i = 1; i <= n; i++) {
printf("Input data for node %d: ", i);
scanf("%d", &data);
insertAtBeginning(&head, data); // Insert at beginning to maintain the correct order
}
// Display the list
printf("\nData entered in the list are:\n");
displayList(head);

// Input new data to insert at the beginning

printf("\nInput data to insert at the beginning of the list: ");
scanf("%d", &data);
insertAtBeginning(&head, data);

// Display the updated list

printf("\nData after inserted in the list are:\n");
displayList(head);

return 0;
}

6. An inventory management system uses a stack to store product prices. The program finds the
minimum price in the stack to identify the least expensive product. Write a C program to find
the minimum element in a stack.
Expected Output:

a. Current stack elements: 9 2 4 2 4

b. Minimum element: 2
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Maximum size of the stack

// Define the stack structure

typedef struct {
int data[MAX];
int top;
} Stack;

// Function to initialize the stack

void initializeStack(Stack *stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(Stack *stack) {
return stack->top == -1;
}

// Function to check if the stack is full

int isFull(Stack *stack) {
return stack->top == MAX - 1;
}

// Function to push an element onto the stack

void push(Stack *stack, int value) {
if (isFull(stack)) {
printf("Stack overflow. Cannot add element.\n");
return;
}
stack->data[++(stack->top)] = value;
}

// Function to display the stack elements

void display(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return;
}
printf("Current stack elements: ");
for (int i = stack->top; i >= 0; i--) {
printf("%d ", stack->data[i]);
}
printf("\n");
}

// Function to find the minimum element in the stack

int findMinimum(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty. No minimum element.\n");
exit(1);
}
int min = stack->data[stack->top];
for (int i = stack->top - 1; i >= 0; i--) {
if (stack->data[i] < min) {
min = stack->data[i];
}
}
return min;
}

// Main function
int main() {
Stack stack;
initializeStack(&stack);

// Push elements onto the stack

push(&stack, 9);
push(&stack, 2);
push(&stack, 4);
push(&stack, 2);
push(&stack, 4);

// Display the stack elements

display(&stack);

// Find and display the minimum element

int min = findMinimum(&stack);
printf("Minimum element: %d\n", min);

return 0;
}

7. A code validation tool checks whether a programmer’s code contains balanced parentheses. The
program uses a stack to verify if the parentheses are correctly matched. Write a C program that
checks whether a string of parentheses is balanced or not using stack.
Input an expression in parentheses: ((()))
The expression is balanced.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100 // Maximum size of the stack

// Define the stack structure

typedef struct {
char data[MAX];
int top;
} Stack;

// Function to initialize the stack

void initializeStack(Stack *stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(Stack *stack) {
return stack->top == -1;
}

// Function to check if the stack is full

int isFull(Stack *stack) {
return stack->top == MAX - 1;
}

// Function to push an element onto the stack

void push(Stack *stack, char value) {
if (isFull(stack)) {
printf("Stack overflow. Cannot push element.\n");
return;
}
stack->data[++(stack->top)] = value;
}

// Function to pop an element from the stack

char pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack underflow. Cannot pop element.\n");
return '\0'; // Return null character if stack is empty
}
return stack->data[(stack->top)--];
}

// Function to check if a string of parentheses is balanced

int isBalanced(const char *expression) {
Stack stack;
initializeStack(&stack);

for (int i = 0; i < strlen(expression); i++) {

char ch = expression[i];

if (ch == '(') {
push(&stack, ch);
} else if (ch == ')') {
if (isEmpty(&stack)) {
return 0; // Unmatched closing parenthesis
}
pop(&stack); // Match closing parenthesis
}
}

// If stack is empty, all parentheses are matched

return isEmpty(&stack);
}

// Main function
int main() {
char expression[MAX];

printf("Input an expression in parentheses: ");

scanf("%s", expression);

if (isBalanced(expression)) {
printf("The expression is balanced.\n");
} else {
printf("The expression is not balanced.\n");
}

return 0;
}
8. A browser history feature keeps track of recently visited pages using a stack. As pages are
visited, they are pushed onto the stack, and the program pops them when the user presses the
back button. Write a C program to implement a stack using a singly linked list.
Expected Output:
Push data 3
Push data 5
Push data 6
Push data 8
Pop data: 8
Pop data: 6
Pop data: 5
Pop data: 3
Check a stack is empty or not?
Stack is empty!
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a stack node

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

// Function to create a new node

Node* createNode(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to push data onto the stack

void push(Node **top, int data) {
Node *newNode = createNode(data);
newNode->next = *top;
*top = newNode;
printf("Push data %d\n", data);
}

// Function to pop data from the stack

int pop(Node **top) {
if (*top == NULL) {
printf("Stack underflow. Cannot pop data.\n");
exit(1);
}
Node *temp = *top;
int data = temp->data;
*top = temp->next;
free(temp);
return data;
}
// Function to check if the stack is empty
int isEmpty(Node *top) {
return top == NULL;
}

// Main function
int main() {
Node *stack = NULL;

// Push data onto the stack

push(&stack, 3);
push(&stack, 5);
push(&stack, 6);
push(&stack, 8);

// Pop data from the stack

printf("\tPop data: %d\n", pop(&stack));
printf("\tPop data: %d\n", pop(&stack));
printf("\tPop data: %d\n", pop(&stack));
printf("\tPop data: %d\n", pop(&stack));

// Check if the stack is empty

printf("Check if the stack is empty or not?\n");
if (isEmpty(stack)) {
printf("Stack is empty!\n");
} else {
printf("Stack is not empty!\n");
}
return 0;
}
9. A calculator app builds an expression tree to evaluate mathematical expressions. The program
takes a postfix expression and constructs the tree to evaluate and display the result. Write a C
program to build an expression tree from a postfix expression. Evaluate and display the results.
Enter the expression :f+g*h
fgh *+
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// Define a tree node

typedef struct Node {
char data;
struct Node *left, *right;
} Node;

// Stack structure for tree nodes

typedef struct Stack {
Node *data;
struct Stack *next;
} Stack;

// Function to create a new tree node

Node* createNode(char data) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to push a tree node onto the stack
void push(Stack **top, Node *node) {
Stack *newStack = (Stack *)malloc(sizeof(Stack));
newStack->data = node;
newStack->next = *top;
*top = newStack;
}

// Function to pop a tree node from the stack

Node* pop(Stack **top) {
if (*top == NULL) {
printf("Stack underflow.\n");
exit(1);
}
Stack *temp = *top;
Node *node = temp->data;
*top = temp->next;
free(temp);
return node;
}

// Function to construct an expression tree from a postfix expression

Node* constructTree(char postfix[]) {
Stack *stack = NULL;

for (int i = 0; postfix[i] != '\0'; i++) {

char ch = postfix[i];

if (isalnum(ch)) {
// Operand: Create a node and push it onto the stack
push(&stack, createNode(ch));
} else {
// Operator: Pop two nodes, create a new node, and push it
Node *node = createNode(ch);
node->right = pop(&stack);
node->left = pop(&stack);
push(&stack, node);
}
}
return pop(&stack); // The root of the tree
}

// Function to evaluate the expression tree

int evaluate(Node *root) {
if (root == NULL) return 0;

// If leaf node, return the operand value

if (root->left == NULL && root->right == NULL) {
return root->data - '0'; // Assuming single-digit operands
}

// Evaluate left and right subtrees

int leftValue = evaluate(root->left);
int rightValue = evaluate(root->right);

// Apply the operator at the root

switch (root->data) {
case '+': return leftValue + rightValue;
case '-': return leftValue - rightValue;
case '*': return leftValue * rightValue;
case '/': return leftValue / rightValue;
}
return 0; // Default case
}

// Function for in-order traversal (optional display of the tree)

void inOrder(Node *root) {
if (root != NULL) {
inOrder(root->left);
printf("%c ", root->data);
inOrder(root->right);
}
}

// Main function
int main() {
char postfix[100];
printf("Enter the postfix expression: ");
scanf("%s", postfix);

// Construct the expression tree

Node *root = constructTree(postfix);

printf("In-order traversal of the expression tree: ");

inOrder(root);
printf("\n");

// Evaluate the expression tree

int result = evaluate(root);
printf("The result of the expression is: %d\n", result);
return 0;
}
10. A search engine returns results in a sorted array. The program uses binary search to find the
position of a query keyword in the sorted list of indexed results. Write a C program to find the
position of a target value within a sorted array using binary search.
Note: Binary Search : In computer science, a binary search or half-interval search algorithm
finds the position of a target value within a sorted array. The binary search algorithm can be
classified as a dichotomies divide-and-conquer search algorithm and executes in logarithmic
time.
Given a sorted array arra[] of n elements, write a function to search a given element x in arra[].
Input no. of elements in an array
3
Input 3 value in ascending order
15
18
20
Input the value to be search : 15
Value found at 0 position
#include <stdio.h>

// Function to perform binary search

int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;

while (left <= right) {

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

// Check if target is at mid

if (arr[mid] == target) {
return mid; // Target found
}
// If target is smaller, search in the left half
if (arr[mid] > target) {
right = mid - 1;
}
// If target is larger, search in the right half
else {
left = mid + 1;
}
}

return -1; // Target not found

}

int main() {
int n, target, result;

// Input the size of the array

printf("Input no. of elements in an array: ");
scanf("%d", &n);

int arr[n];

// Input sorted elements into the array

printf("Input %d values in ascending order:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the target value to search

printf("Input the value to be searched: ");
scanf("%d", &target);

// Perform binary search

result = binarySearch(arr, n, target);

// Output the result

if (result != -1) {
printf("Value found at %d position\n", result);
} else {
printf("Value not found in the array\n");
}

return 0;
}

11. A navigation system uses Dijkstra’s algorithm to find the shortest route between two locations.
The program calculates the shortest path from the user's current location to various destination
points. Write a C program that creates a function to find the shortest path from a source vertex
to all other vertices using Dijkstra's algorithm.

#include <stdio.h>
#include <limits.h>

#define V 4 // Number of vertices in the graph (A, B, C, D)

// Function to find the vertex with the minimum distance value

int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;

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

if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}

return min_index;
}

// Function to implement Dijkstra's algorithm to find the shortest path from source to all vertices
void dijkstra(int graph[V][V], int src) {
int dist[V]; // The output array dist[i] holds the shortest distance from src to i
int sptSet[V]; // sptSet[i] will be true if vertex i is included in the shortest path tree

// Initialize all distances as INFINITE and sptSet[] as false

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}

// Distance from source to source is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = 1;

// Update dist[] values of the adjacent vertices of the picked vertex

for (int v = 0; v < V; v++) {
// Update dist[v] if the current vertex is not in the shortest path tree, there is an edge from u to
v,
// and the total distance from source to v through u is smaller than the current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the constructed distance array

printf("Vertex\tDistance from Source %d\n", src);
for (int i = 0; i < V; i++) {
if (dist[i] == INT_MAX)
printf("%d\t\tINF\n", i); // If distance is infinity, print INF
else
printf("%d\t\t%d\n", i, dist[i]);
}
}

int main() {
// Graph representation based on the image (Adjacency matrix)
// The graph is represented as follows:
// A = 0, B = 1, C = 2, D = 3
int graph[V][V] = {
{0, 5, 0, 8}, // A to B = 5, A to D = 8
{5, 0, 2, 7}, // B to A = 5, B to C = 2, B to D = 7
{0, 2, 0, 6}, // C to B = 2, C to D = 6
{8, 7, 6, 0} // D to A = 8, D to B = 7, D to C = 6
};

int source;
printf("Enter the source vertex (0 for A, 1 for B, 2 for C, 3 for D): ");
scanf("%d", &source);

dijkstra(graph, source);

return 0;
}

12. A ticket booking system uses a circular queue to manage reservations. As customers book and
cancel tickets, the program inserts and deletes customer requests from the queue while
maintaining a circular order. Write a C program to implement a circular queue and perform
insertion and deletion operations
Circular Queue:
Front 1 2 3 4 5 Rear
After Insertion:
Front 1 2 3 4 5 6 Rear
After Deletion:
Front 2 3 4 5 6 Rear
#include <stdio.h>
#include <stdlib.h>

#define MAX 5 // Maximum size of the queue

// Define a structure to represent a Circular Queue

struct CircularQueue {
int arr[MAX];
int front, rear;
};

// Function to initialize the queue

void initQueue(struct CircularQueue* q) {
q->front = q->rear = -1;
}

// Function to check if the queue is full

int isFull(struct CircularQueue* q) {
return ((q->rear + 1) % MAX == q->front);
}

// Function to check if the queue is empty

int isEmpty(struct CircularQueue* q) {
return (q->front == -1);
}

// Function to insert an element into the queue (Enqueue)

void enqueue(struct CircularQueue* q, int value) {
if (isFull(q)) {
printf("Queue is full! Cannot insert %d\n", value);
} else {
if (q->front == -1) {
q->front = 0; // Queue is empty, so initialize the front
}
q->rear = (q->rear + 1) % MAX; // Move rear to the next position
q->arr[q->rear] = value; // Insert the value
printf("Inserted %d into the queue.\n", value);
}
}

// Function to delete an element from the queue (Dequeue)

int dequeue(struct CircularQueue* q) {
int value;
if (isEmpty(q)) {
printf("Queue is empty! Cannot dequeue.\n");
return -1;
} else {
value = q->arr[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1; // Queue becomes empty after deletion
} else {
q->front = (q->front + 1) % MAX; // Move front to the next position
}
return value;
}
}

// Function to display the elements of the queue

void display(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
} else {
printf("Queue elements: ");
int i = q->front;
while (i != q->rear) {
printf("%d ", q->arr[i]);
i = (i + 1) % MAX;
}
printf("%d\n", q->arr[q->rear]); // Print the last element
}
}

int main() {
struct CircularQueue q;
initQueue(&q);

// Insert elements into the queue

enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
enqueue(&q, 5); // Queue is now full

display(&q);

// Insert one more element (should fail since the queue is full)
enqueue(&q, 6);

// Dequeue one element

int deletedValue = dequeue(&q);
printf("Deleted value: %d\n", deletedValue);

display(&q);

// Insert another element after deletion

enqueue(&q, 6);
display(&q);

return 0;
}
13. A playlist management system finds the kth last song in a list of songs. The program traverses
the list to identify the kth last song, useful for features like "last played" or "recently added."
Write a C program to find the kth to last element in a singly linked list.
Linked List: 1 2 3 4 5
2nd to Last Element: 4
#include <stdio.h>
#include <stdlib.h>

// Define a structure for a node in the singly linked list

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

// Function to create a new node

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

// Function to find the kth to last element in a linked list

void findKthToLast(struct Node* head, int k) {
struct Node *first = head, *second = head;

// Move the first pointer k steps ahead

for (int i = 0; i < k; i++) {
if (first == NULL) {
printf("List has fewer than %d elements.\n", k);
return;
}
first = first->next;
}

// Move both pointers one step at a time

while (first != NULL) {
first = first->next;
second = second->next;
}

// Now second points to the kth to last element

if (second != NULL) {
printf("The %dth to last element is: %d\n", k, second->data);
}
}

// Function to print the elements of the linked list

void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
// Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);

printf("Linked List: ");

printList(head);

int k = 2;
findKthToLast(head, k); // Find 2nd to last element

return 0;
}
14. A library uses a Binary Search Tree (BST) to manage book IDs, allowing efficient search and
organization. Implement a program to insert book IDs into the BST, find the minimum ID
(smallest book ID), and locate the maximum ID (largest book ID), enabling quick access to
specific records. Implement insertion, minimum, and maximum operations to locate books
quickly
#include <stdio.h>
#include <stdlib.h>

// Define a structure for a node in the Binary Search Tree

struct Node {
int bookID;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int bookID) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->bookID = bookID;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function to insert a book ID into the Binary Search Tree

struct Node* insert(struct Node* root, int bookID) {
if (root == NULL) {
return createNode(bookID); // Create a new node if root is NULL
}

if (bookID < root->bookID) {

root->left = insert(root->left, bookID); // Insert into the left subtree
} else {
root->right = insert(root->right, bookID); // Insert into the right subtree
}

return root; // Return the root node

}

// Function to find the minimum book ID in the BST

struct Node* findMin(struct Node* root) {
while (root != NULL && root->left != NULL) {
root = root->left; // Traverse to the leftmost node
}
return root; // Return the node with the minimum book ID
}
// Function to find the maximum book ID in the BST
struct Node* findMax(struct Node* root) {
while (root != NULL && root->right != NULL) {
root = root->right; // Traverse to the rightmost node
}
return root; // Return the node with the maximum book ID
}

// Function to perform an inorder traversal of the BST (to display the tree in sorted order)
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left); // Traverse the left subtree
printf("%d ", root->bookID); // Visit the root node
inorder(root->right); // Traverse the right subtree
}
}

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

// Insert some book IDs into the Binary Search Tree

root = insert(root, 20);
root = insert(root, 10);
root = insert(root, 30);
root = insert(root, 5);
root = insert(root, 15);
root = insert(root, 25);
root = insert(root, 35);

// Display the tree in sorted order (inorder traversal)

printf("Inorder traversal of the BST (sorted book IDs): ");
inorder(root);
printf("\n");

// Find the minimum and maximum book IDs

struct Node* minNode = findMin(root);
struct Node* maxNode = findMax(root);

if (minNode != NULL) {
printf("Minimum book ID: %d\n", minNode->bookID);
} else {
printf("The tree is empty.\n");
}

if (maxNode != NULL) {
printf("Maximum book ID: %d\n", maxNode->bookID);
} else {
printf("The tree is empty.\n");
}

return 0;
}
15. A symbolic computation tool demands a program to convert infix expressions to postfix notation
for easier evaluation. The program should handle expressions like ((4+8)(6-5))/((3-2)(2+2)) and
produce their postfix equivalents. A symbolic computation tool needs a converter for infix to
postfix notation. Convert expressions like ((4+8)(6-5))/((3-2)(2+2)) into postfix form
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

// Stack structure for operators
struct Stack {
int top;
char items[MAX];
};

// Function to initialize the stack

void initStack(struct Stack* s) {
s->top = -1;
}

// Function to check if the stack is empty

int isEmpty(struct Stack* s) {
return s->top == -1;
}

// Function to check if the stack is full

int isFull(struct Stack* s) {
return s->top == MAX - 1;
}

// Function to push an element onto the stack

void push(struct Stack* s, char c) {
if (isFull(s)) {
printf("Stack overflow\n");
return;
}
s->items[++(s->top)] = c;
}
// Function to pop an element from the stack
char pop(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack underflow\n");
return -1;
}
return s->items[(s->top)--];
}

// Function to peek the top element of the stack

char peek(struct Stack* s) {
if (isEmpty(s)) {
return -1;
}
return s->items[s->top];
}

// Function to check precedence of operators

int precedence(char c) {
if (c == '+' || c == '-') {
return 1;
}
if (c == '*' || c == '/') {
return 2;
}
return 0;
}

// Function to convert infix expression to postfix

void infixToPostfix(char* infix, char* postfix) {
struct Stack s;
initStack(&s);

int i = 0, j = 0;
while (infix[i] != '\0') {
char c = infix[i];

// If the character is an operand (number or letter), add it to the postfix expression

if (isdigit(c)) {
postfix[j++] = c;
}
// If the character is '(', push it onto the stack
else if (c == '(') {
push(&s, c);
}
// If the character is ')', pop from the stack until '(' is found
else if (c == ')') {
while (!isEmpty(&s) && peek(&s) != '(') {
postfix[j++] = pop(&s);
}
pop(&s); // Pop '('
}
// If the character is an operator
else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(c)) {
postfix[j++] = pop(&s);
}
push(&s, c);
}
i++;
}

// Pop all remaining operators from the stack

while (!isEmpty(&s)) {
postfix[j++] = pop(&s);
}

postfix[j] = '\0'; // Null-terminate the postfix expression

}

int main() {
char infix[MAX], postfix[MAX];

// Input infix expression

printf("Enter infix expression: ");
scanf("%s", infix);

// Convert to postfix
infixToPostfix(infix, postfix);

// Output postfix expression

printf("Postfix expression: %s\n", postfix);

return 0;
}
16. A sorting program for organizing exam scores uses the insertion sort algorithm. The program
takes an unsorted array of scores, applies insertion sort, and outputs the scores in ascending
order. Write a C program to implement the insertion sort algorithm.
Original Array: 8 3 5 1 4
After Insertion Sort:1 3 4 5 8
#include <stdio.h>

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

int i, key, j;

// Traverse through 1 to n-1

for (i = 1; i < n; i++) {
key = arr[i]; // The element to be inserted
j = i - 1;

// Move elements of arr[0..i-1] that are greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}

// Place the key after finding its correct position

arr[j + 1] = key;
}
}

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

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {8, 3, 5, 1, 4};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

printArray(arr, n);

insertionSort(arr, n); // Call the insertion sort function

printf("After Insertion Sort: ");

printArray(arr, n); // Output the sorted array

return 0;
}
17. A data processing system uses a stack to temporarily store records for processing. The system
uses a fixed-size stack (int stack[5] = {30, 40, 50, 60}) and needs to ensure that no overflows
occur when new data is added. Write a program that checks if the stack is full before inserting
new records. If a user attempts to add more records than the stack's capacity, the program
should display an error message indicating that the stack is full.
Expected Output:
Error: Stack is full! Cannot add more records.
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5 // Maximum size of the stack

// Stack structure
struct Stack {
int top;
int stack[MAX_SIZE];
};

// Initialize the stack

void initStack(struct Stack *s) {
s->top = -1; // Stack is empty initially
}

// Check if the stack is full

int isFull(struct Stack *s) {
return s->top == MAX_SIZE - 1;
}
// Check if the stack is empty
int isEmpty(struct Stack *s) {
return s->top == -1;
}

// Push an element onto the stack

void push(struct Stack *s, int value) {
if (isFull(s)) {
printf("Error: Stack is full! Cannot add more records.\n");
} else {
s->stack[++(s->top)] = value;
printf("Pushed %d to the stack.\n", value);
}
}

// Pop an element from the stack

int pop(struct Stack *s) {
if (isEmpty(s)) {
printf("Error: Stack is empty! Cannot pop.\n");
return -1;
} else {
return s->stack[(s->top)--];
}
}

// Display the stack elements

void displayStack(struct Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
for (int i = 0; i <= s->top; i++) {
printf("%d ", s->stack[i]);
}
printf("\n");
}
}

int main() {
struct Stack s;
initStack(&s);

// Initial stack with predefined values

s.stack[0] = 30;
s.stack[1] = 40;
s.stack[2] = 50;
s.stack[3] = 60;
s.top = 3; // Stack currently has 4 elements

// Display initial stack

displayStack(&s);

// Try to push a new record

push(&s, 70); // This should succeed

// Try to push another record when the stack is full

push(&s, 80); // This should give an error message

// Display stack after insertion attempts

displayStack(&s);

return 0;
}

18. A shopping cart system stores item prices in a queue. The program should calculate the total
cost of all the items in the cart, displaying both the prices in the queue and the calculated sum.
If a user adds or removes items, the total should be updated accordingly. The queue needs to
handle basic enqueue and dequeue operations and show how the system computes the total cost
efficiently.
Input Example: Queue elements (prices): 1, 2, 3, 4, 5
Output Example:
Queue elements: 1 2 3 4 5
Sum of elements: 15
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5 // Maximum size of the queue

// Queue structure
struct Queue {
int front, rear;
int queue[MAX_SIZE];
int totalCost; // To keep track of the sum of the prices in the queue
};

// Initialize the queue

void initQueue(struct Queue *q) {
q->front = -1;
q->rear = -1;
q->totalCost = 0;
}

// Check if the queue is empty

int isEmpty(struct Queue *q) {
return q->front == -1;
}

// Check if the queue is full

int isFull(struct Queue *q) {
return q->rear == MAX_SIZE - 1;
}

// Enqueue function to add an item to the queue

void enqueue(struct Queue *q, int price) {
if (isFull(q)) {
printf("Error: Queue is full! Cannot add more items.\n");
} else {
if (q->front == -1) {
q->front = 0; // If the queue is empty
}
q->rear++;
q->queue[q->rear] = price;
q->totalCost += price; // Update the total cost
printf("Added item with price: %d\n", price);
}
}

// Dequeue function to remove an item from the queue

int dequeue(struct Queue *q) {
if (isEmpty(q)) {
printf("Error: Queue is empty! Cannot remove items.\n");
return -1;
} else {
int item = q->queue[q->front];
q->totalCost -= item; // Update the total cost
q->front++;
if (q->front > q->rear) { // Reset the queue if it's empty
q->front = q->rear = -1;
}
return item;
}
}

// Display the queue elements

void displayQueue(struct Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
} else {
printf("Queue elements: ");
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->queue[i]);
}
printf("\n");
}
}

// Function to display the total cost

void displayTotalCost(struct Queue *q) {
printf("Total cost of items: %d\n", q->totalCost);
}

int main() {
struct Queue q;
initQueue(&q);

// Example of adding items to the cart

enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
enqueue(&q, 5);

// Display queue and total cost

displayQueue(&q);
displayTotalCost(&q);

// Example of removing items from the cart

printf("Removing item with price: %d\n", dequeue(&q));
displayQueue(&q);
displayTotalCost(&q);

return 0;
}
19. A system needs to convert a given decimal number to its binary equivalent for low-level
processing. The program should take a decimal number as input and output the binary
representation. It will use the division-by-2 method to generate the binary form and output the
result. This conversion helps in performing bit-level operations in various applications. Write a
C program to convert decimal to binary.
#include <stdio.h>

void decimalToBinary(int decimal) {

int binary[32]; // Array to store binary number
int index = 0; // Index for the binary array
// Special case for 0
if (decimal == 0) {
printf("Binary: 0\n");
return;
}

// Divide by 2 and store remainders

while (decimal > 0) {
binary[index] = decimal % 2;
decimal = decimal / 2;
index++;
}

// Print binary number in reverse order

printf("Binary: ");
for (int i = index - 1; i >= 0; i--) {
printf("%d", binary[i]);
}
printf("\n");
}

int main() {
int decimal;

// Input decimal number

printf("Enter a decimal number: ");
scanf("%d", &decimal);

// Convert to binary
decimalToBinary(decimal);

return 0;
}

20. A contact management system uses a hash table to store names and phone numbers. The system
should allow adding, deleting, and searching for contacts. The hash table will efficiently manage
the contacts, ensuring quick lookups and updates. The program should provide functions to
insert a new contact, delete a contact, and search for an existing one. Implement a C program
using a hash table.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10 // Define the size of the hash table

// Structure to store contact details

struct Contact {
char name[50];
char phoneNumber[15];
struct Contact *next; // Pointer to handle collisions (separate chaining)
};

// Hash table array of pointers to linked lists

struct Contact *hashTable[TABLE_SIZE];

// Hash function to map name to an index in the hash table

unsigned int hash(char *name) {
unsigned int hashValue = 0;
while (*name) {
hashValue = (hashValue * 31) + *name; // Simple hash function
name++;
}
return hashValue % TABLE_SIZE;
}

// Function to insert a contact into the hash table

void insertContact(char *name, char *phoneNumber) {
unsigned int index = hash(name);

struct Contact *newContact = (struct Contact*) malloc(sizeof(struct Contact));

strcpy(newContact->name, name);
strcpy(newContact->phoneNumber, phoneNumber);
newContact->next = NULL;

// Insert the new contact at the head of the linked list

if (hashTable[index] == NULL) {
hashTable[index] = newContact;
} else {
newContact->next = hashTable[index];
hashTable[index] = newContact;
}

printf("Contact added: %s, %s\n", name, phoneNumber);

}

// Function to search for a contact in the hash table

void searchContact(char *name) {
unsigned int index = hash(name);
struct Contact *current = hashTable[index];

while (current != NULL) {

if (strcmp(current->name, name) == 0) {
printf("Contact found: %s, %s\n", current->name, current->phoneNumber);
return;
}
current = current->next;
}

printf("Contact not found.\n");

}

// Function to delete a contact from the hash table

void deleteContact(char *name) {
unsigned int index = hash(name);
struct Contact *current = hashTable[index];
struct Contact *prev = NULL;

while (current != NULL) {

if (strcmp(current->name, name) == 0) {
if (prev == NULL) {
// Deleting the first element of the list
hashTable[index] = current->next;
} else {
// Deleting a middle or last element
prev->next = current->next;
}
free(current);
printf("Contact deleted: %s\n", name);
return;
}
prev = current;
current = current->next;
}

printf("Contact not found.\n");

}

// Function to print all contacts in the hash table

void printAllContacts() {
printf("All contacts in the system:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
struct Contact *current = hashTable[i];
while (current != NULL) {
printf("%s: %s\n", current->name, current->phoneNumber);
current = current->next;
}
}
}

int main() {
// Initialize the hash table
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i] = NULL;
}

// Example operations on the contact management system

insertContact("Alice", "1234567890");
insertContact("Bob", "9876543210");
insertContact("Charlie", "5555555555");
insertContact("David", "1112223333");

printAllContacts();

// Searching for a contact

searchContact("Alice");
searchContact("Eve");

// Deleting a contact
deleteContact("Bob");
printAllContacts();

return 0;
}

21. A program allows users to reverse a linked list representing a sequence of numbers. The system
should take an existing list and reverse the order of its elements using a simple linked list
algorithm. This operation is common in situations where the order of items must be flipped,
such as in undo operations.
Input Example:
Original Linked List: 2 -> 7 -> 3 -> NULL
Output Example:
Reversed Linked List: 3 -> 7 -> 2 -> NULL
#include <stdio.h>
#include <stdlib.h>

// Definition of the linked list node

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

// Function to insert a node at the beginning of the list

void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}

// Function to reverse the linked list

void reverseLinkedList(struct Node** head) {
struct Node *previous = NULL, *current = *head, *next = NULL;

while (current != NULL) {

next = current->next; // Save the next node
current->next = previous; // Reverse the current node's pointer
previous = current; // Move previous to the current node
current = next; // Move current to the next node
}

*head = previous; // Update the head to the last node

}

// Function to print the linked list

void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

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

// Inserting nodes into the linked list

insertAtBeginning(&head, 3);
insertAtBeginning(&head, 7);
insertAtBeginning(&head, 2);

printf("Original Linked List: ");

printList(head);

// Reversing the linked list

reverseLinkedList(&head);

printf("Reversed Linked List: ");

printList(head);

return 0;
}
22. A class uses an array to store student roll numbers. The program should allow users to input
roll numbers for 8 students and then print them in order. This is useful for recording and
displaying student data quickly.
Input Example:
Enter 8 roll numbers: 101, 102, 103, 104, 105, 106, 107, 108
Output Example:
Roll Numbers: 101, 102, 103, 104, 105, 106, 107, 108
Design a C program for a Binary Search Tree (BST) to manage student records by their roll
numbers. The program should perform the following operations:
Insert a new student record by roll number.
Search for a student record by roll number.
Display all student records in ascending order of roll numbers
#include <stdio.h>
#include <stdlib.h>

// Definition of the node structure

struct Node {
int roll_number;
struct Node *left, *right;
};

// Function to create a new node

struct Node* createNode(int roll_number) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->roll_number = roll_number;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function to insert a new node into the BST

struct Node* insert(struct Node* root, int roll_number) {
// If the tree is empty, return a new node
if (root == NULL) {
return createNode(roll_number);
}

// Otherwise, recur down the tree

if (roll_number < root->roll_number) {
root->left = insert(root->left, roll_number);
} else if (roll_number > root->roll_number) {
root->right = insert(root->right, roll_number);
}

// Return the (unchanged) node pointer

return root;
}

// Function to search for a roll number in the BST

struct Node* search(struct Node* root, int roll_number) {
// Base case: root is null or roll_number is present at the root
if (root == NULL || root->roll_number == roll_number) {
return root;
}

// Roll number is greater than root's roll_number

if (roll_number > root->roll_number) {
return search(root->right, roll_number);
}

// Roll number is smaller than root's roll_number

return search(root->left, roll_number);
}

// Function for in-order traversal to display the roll numbers in ascending order
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->roll_number);
inOrderTraversal(root->right);
}
}

int main() {
struct Node* root = NULL;
int roll_number;

// Input the roll numbers for 8 students

printf("Enter 8 roll numbers:\n");
for (int i = 0; i < 8; i++) {
scanf("%d", &roll_number);
root = insert(root, roll_number); // Insert roll number into the BST
}

// Display all student roll numbers in ascending order

printf("\nRoll Numbers in Ascending Order: ");
inOrderTraversal(root);
printf("\n");

// Search for a student record by roll number

printf("\nEnter a roll number to search: ");
scanf("%d", &roll_number);
struct Node* result = search(root, roll_number);
if (result != NULL) {
printf("Student with roll number %d found.\n", roll_number);
} else {
printf("Student with roll number %d not found.\n", roll_number);
}

return 0;
}

23. Design a C program to implement Radix Sort for sorting a list of non-negative integers in
ascending order. The program sorts elements based on each digit, starting from the least
significant digit (unit place) and progressing to more significant digits (tens, hundreds, etc.).
The program will display the intermediate results after each pass and finally print the sorted
list.
#include <stdio.h>
#include <stdlib.h>

// Function to perform counting sort on the basis of the digit represented by exp
void countingSort(int arr[], int n, int exp) {
int output[n]; // Output array to store sorted numbers
int count[10] = {0}; // Count array to store frequency of digits (0-9)

// Store count of occurrences in count[]

for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}

// Change count[i] so that count[i] now contains the actual position of this digit in output[]
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}

// Build the output array using the count positions

for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

// Copy the output array to arr[], so that arr[] now contains sorted numbers based on the
current digit
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}

// Function to perform Radix Sort

void radixSort(int arr[], int n) {
// Find the maximum number to know the number of digits
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}

// Do counting sort for every digit (exp is 10^i where i is the current digit number)
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, n, exp);

// Print the array after sorting based on the current digit

printf("Intermediate result after sorting by place %d: ", exp);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
}

int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; // Example array
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Call the radixSort function to sort the array

radixSort(arr, n);
// Print the sorted array
printf("Sorted Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}
24. Design a Binary Search algorithm for the ordered list of elements. The input must be random
number generated from random function, the ordered list of elements must sorted using
insertion sort algorithm. Then, search the key elements present or not, find the time complexity
and print the results. The input size is of 15 elements
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to perform Insertion Sort

void insertionSort(int arr[], int n) {
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

// Shift elements of arr[0..i-1] that are greater than key

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// Function to perform Binary Search

int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

// Check if key is present at mid

if (arr[mid] == key) {
return mid;
}

// If key is greater, ignore the left half

if (arr[mid] < key) {
low = mid + 1;
}
// If key is smaller, ignore the right half
else {
high = mid - 1;
}
}

// Key not present in array

return -1;
}

int main() {
int n = 15;
int arr[n];
srand(time(0)); // Initialize random number generator

// Generate 15 random numbers between 1 and 100

printf("Generated Random Numbers: ");
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100 + 1;
printf("%d ", arr[i]);
}
printf("\n");

// Sort the array using Insertion Sort

insertionSort(arr, n);

// Display the sorted array

printf("Sorted Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Input the key to search

int key;
printf("Enter the number to search: ");
scanf("%d", &key);

// Perform binary search

int result = binarySearch(arr, n, key);
// Output result
if (result != -1) {
printf("Element %d found at index %d.\n", key, result);
} else {
printf("Element %d not found in the array.\n", key);
}

return 0;
}
25. Topological sort is a method of arranging the vertices in a directed acyclic graph (DAG), as a
sequence, such that no vertex appears in the sequence before its predecessor. A directed graph
G is a DAG if it does not have any cycle. We have a set of tasks and a set of dependencies
(precedence constraints) of form “task A must be done before task B”. Design a C program to
display the ordering of the tasks that conforms with the given dependencies.

#include <stdio.h>
#include <stdlib.h>

#define MAX 6 // Assuming there are 6 tasks (vertices)

// Structure for adjacency list node

struct Node {
int vertex;
struct Node* next;
};
// Graph representation using adjacency list
struct Graph {
struct Node* adjList[MAX];
int inDegree[MAX]; // Array to store in-degree of vertices
};

// Function to create a new adjacency list node

struct Node* newNode(int vertex) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->vertex = vertex;
node->next = NULL;
return node;
}

// Function to initialize the graph

void initGraph(struct Graph* graph) {
for (int i = 0; i < MAX; i++) {
graph->adjList[i] = NULL;
graph->inDegree[i] = 0;
}
}

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {
struct Node* node = newNode(dest);
node->next = graph->adjList[src];
graph->adjList[src] = node;
graph->inDegree[dest]++;
}
// Kahn's Algorithm for Topological Sort
void topologicalSort(struct Graph* graph) {
int queue[MAX], front = -1, rear = -1;
int topologicalOrder[MAX];
int idx = 0;

// Push all vertices with zero in-degree to the queue

for (int i = 0; i < MAX; i++) {
if (graph->inDegree[i] == 0) {
queue[++rear] = i;
}
}

// Process the graph

while (front != rear) {
int u = queue[++front];
topologicalOrder[idx++] = u;

// Decrease the in-degree of adjacent vertices

struct Node* temp = graph->adjList[u];
while (temp != NULL) {
int v = temp->vertex;
graph->inDegree[v]--;
if (graph->inDegree[v] == 0) {
queue[++rear] = v;
}
temp = temp->next;
}
}
// Check if there is a cycle (not all vertices are processed)
if (idx != MAX) {
printf("There is a cycle in the graph! Topological sort not possible.\n");
return;
}

// Print the topological order

printf("Topological Sort: ");
for (int i = 0; i < MAX; i++) {
printf("%d ", topologicalOrder[i]);
}
printf("\n");
}

int main() {
struct Graph graph;
initGraph(&graph);

// Adding edges based on the given graph (from the image)

// Add directed edges according to the diagram
addEdge(&graph, 0, 1); // Task 1 -> Task 2
addEdge(&graph, 0, 3); // Task 1 -> Task 4
addEdge(&graph, 1, 4); // Task 2 -> Task 5
addEdge(&graph, 2, 4); // Task 3 -> Task 5
addEdge(&graph, 3, 5); // Task 4 -> Task 6

// Perform Topological Sort

topologicalSort(&graph);
return 0;
}
26. Design a Binary Search algorithm for the ordered list of elements. The input must be random
number generated from random function, the ordered list of elements must sorted using
insertion sort algorithm. Then, search the key elements present or not, find the time complexity
and print the results. The input size is 15 elements.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to perform Insertion Sort

void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

// Move elements of arr[0..i-1] that are greater than key

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// Function to perform Binary Search

int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if the target is at the mid position
if (arr[mid] == target)
return mid; // Target found

// If target is smaller, ignore right half

if (arr[mid] > target)
right = mid - 1;

// If target is larger, ignore left half

else
left = mid + 1;
}

return -1; // Target not found

}

int main() {
srand(time(0)); // Seed for random number generation

int n = 15;
int arr[n];

// Generate 15 random numbers between 1 and 100

for (int i = 0; i < n; i++) {
arr[i] = rand() % 100 + 1;
}

printf("Generated Random Numbers:\n");

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Sort the array using Insertion Sort

insertionSort(arr, n);

printf("\nSorted List Using Insertion Sort:\n");

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Input the target element for binary search

int target;
printf("\nEnter the target element to search: ");
scanf("%d", &target);

// Perform binary search

int result = binarySearch(arr, 0, n - 1, target);

if (result != -1) {
printf("\nElement %d found at index %d.\n", target, result);
} else {
printf("\nElement %d not found in the list.\n", target);
}

// Time Complexity:
printf("\nTime Complexity of Insertion Sort: O(n^2)\n");
printf("Time Complexity of Binary Search: O(log n)\n");
return 0;
}
27. A job scheduling system uses a queue to manage tasks. The system needs operations such as
checking if the queue is empty or full, enqueuing and dequeuing tasks, and fetching the front
and rear tasks. Design a C program to implement these operations for managing the task queue.
Input:
Queue is empty initially.
Operations:
Enqueue tasks A, B, C, D, E.
Check if the queue is full.
Dequeue two tasks.
Check if the queue is empty.
Output:
Queue after enqueueing: A B C D E
Is the queue full? Yes
Queue after dequeuing: C D E
Is the queue empty? No
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX 5 // Maximum size of the queue

// Define the queue structure

typedef struct {
char tasks[MAX][20]; // Array to store tasks (strings of up to 20 characters)
int front, rear;
} Queue;

// Function to initialize the queue

void initQueue(Queue *q) {
q->front = q->rear = -1;
}
// Function to check if the queue is empty
bool isEmpty(Queue *q) {
return q->front == -1;
}

// Function to check if the queue is full

bool isFull(Queue *q) {
return (q->rear + 1) % MAX == q->front;
}

// Function to enqueue a task

void enqueue(Queue *q, const char *task) {
if (isFull(q)) {
printf("Error: Queue is full! Cannot add more tasks.\n");
return;
}

if (q->front == -1) { // If the queue is empty

q->front = 0;
}
q->rear = (q->rear + 1) % MAX; // Circular increment
strcpy(q->tasks[q->rear], task); // Add the task to the queue
}

// Function to dequeue a task

void dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Error: Queue is empty! No tasks to dequeue.\n");
return;
}
printf("Dequeued task: %s\n", q->tasks[q->front]);

if (q->front == q->rear) { // If there's only one task in the queue

q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX; // Circular increment
}
}

// Function to display the tasks in the queue

void displayQueue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return;
}

printf("Queue tasks: ");

int i = q->front;
while (i != q->rear) {
printf("%s ", q->tasks[i]);
i = (i + 1) % MAX; // Circular increment
}
printf("%s\n", q->tasks[q->rear]); // Print the last task
}

// Function to check the front task of the queue

void frontTask(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty. No front task.\n");
} else {
printf("Front task: %s\n", q->tasks[q->front]);
}
}

// Function to check the rear task of the queue

void rearTask(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty. No rear task.\n");
} else {
printf("Rear task: %s\n", q->tasks[q->rear]);
}
}

int main() {
Queue q;
initQueue(&q);

printf("Queue is empty initially.\n");

// Enqueue tasks
enqueue(&q, "A");
enqueue(&q, "B");
enqueue(&q, "C");
enqueue(&q, "D");
enqueue(&q, "E");

// Display queue after enqueueing tasks

printf("\nQueue after enqueueing: ");
displayQueue(&q);
// Check if the queue is full
printf("\nIs the queue full? ");
if (isFull(&q)) {
printf("Yes\n");
} else {
printf("No\n");
}

// Dequeue two tasks

dequeue(&q);
dequeue(&q);

// Display queue after dequeuing tasks

printf("\nQueue after dequeuing: ");
displayQueue(&q);

// Check if the queue is empty

printf("\nIs the queue empty? ");
if (isEmpty(&q)) {
printf("Yes\n");
} else {
printf("No\n");
}

return 0;
}

28. In a calculator application for a mathematical expression evaluator, the user inputs a postfix
expression to compute a result. The application needs to convert the postfix expression into a
prefix format for easier evaluation using a stack-based algorithm.

Given Input:
Postfix Expression: A B + C D - *

Expected Output:

Prefix Expression: * + A B - C D

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <stdlib.h>

#define MAX 100

// Function to check if the character is an operator

int isOperator(char c) {

return (c == '+' || c == '-' || c == '*' || c == '/');

// Function to convert a postfix expression to prefix

void postfixToPrefix(char *postfix) {

char stack[MAX][MAX]; // Stack to store intermediate expressions

int top = -1; // Stack top

// Traverse the postfix expression

for (int i = 0; i < strlen(postfix); i++) {

char c = postfix[i];

// If the character is an operand, push it to the stack

if (isalnum(c)) {

char operand[2] = {c, '\0'}; // Convert character to string

top++;

strcpy(stack[top], operand);

// If the character is an operator

else if (isOperator(c)) {

// Pop two operands from the stack

char operand2[MAX], operand1[MAX];

strcpy(operand2, stack[top]);

top--;

strcpy(operand1, stack[top]);

top--;

// Form a new expression by prefixing the operator

char newExpr[MAX];

snprintf(newExpr, sizeof(newExpr), "%c%s%s", c, operand1, operand2);

// Push the new expression to the stack

top++;

strcpy(stack[top], newExpr);

// The final result is the only element left in the stack

printf("Prefix Expression: %s\n", stack[top]);

int main() {

char postfix[MAX];

// Input the postfix expression

printf("Enter the postfix expression: ");

scanf("%s", postfix);

// Convert postfix to prefix

postfixToPrefix(postfix);

return 0;

29. A ticket booking system requires a deque to accept input from both ends. Tickets can only be
issued (removed) from the front to maintain sequential processing for fairness. The system will
manage ticket reservations, ensuring that new bookings are added efficiently and that customers
are processed from the front of the queue. The program will allow both adding and removing
reservations dynamically. Write a C program using a deque.
#include <stdio.h>
#include <stdlib.h>

#define MAX 5 // Size of deque (can be adjusted)

typedef struct {
int tickets[MAX];
int front, rear;
} Deque;

// Initialize the deque

void initializeDeque(Deque* dq) {
dq->front = -1;
dq->rear = -1;
}
// Check if the deque is full
int isFull(Deque* dq) {
if ((dq->rear + 1) % MAX == dq->front)
return 1;
return 0;
}

// Check if the deque is empty

int isEmpty(Deque* dq) {
if (dq->front == -1)
return 1;
return 0;
}

// Add ticket to the rear

void enqueueRear(Deque* dq, int ticket) {
if (isFull(dq)) {
printf("Error: Deque is full! Cannot add more tickets.\n");
return;
}
if (isEmpty(dq)) {
dq->front = dq->rear = 0;
} else {
dq->rear = (dq->rear + 1) % MAX;
}
dq->tickets[dq->rear] = ticket;
printf("Ticket %d booked successfully!\n", ticket);
}

// Remove ticket from the front

void dequeueFront(Deque* dq) {
if (isEmpty(dq)) {
printf("Error: Deque is empty! No tickets to issue.\n");
return;
}
printf("Ticket %d issued!\n", dq->tickets[dq->front]);
if (dq->front == dq->rear) {
dq->front = dq->rear = -1; // Reset deque
} else {
dq->front = (dq->front + 1) % MAX;
}
}

// Display tickets in the deque

void display(Deque* dq) {
if (isEmpty(dq)) {
printf("Deque is empty!\n");
return;
}
printf("Tickets in the deque: ");
int i = dq->front;
while (i != dq->rear) {
printf("%d ", dq->tickets[i]);
i = (i + 1) % MAX;
}
printf("%d\n", dq->tickets[dq->rear]); // Print last ticket
}

int main() {
Deque dq;
initializeDeque(&dq);

int choice, ticket;

while (1) {
printf("\nTicket Booking System\n");
printf("1. Book a ticket (Add to rear)\n");
printf("2. Issue a ticket (Remove from front)\n");
printf("3. Display tickets\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
if (isFull(&dq)) {
printf("Error: Deque is full! Cannot book more tickets.\n");
} else {
printf("Enter ticket number to book: ");
scanf("%d", &ticket);
enqueueRear(&dq, ticket);
}
break;

case 2:
dequeueFront(&dq);
break;

case 3:
display(&dq);
break;

case 4:
printf("Exiting ticket booking system...\n");
exit(0);

default:
printf("Invalid choice! Please try again.\n");
}
}

return 0;
}

30. A telecom company requires a linked list where each node represents a digit from a customer’s
phone number. If the number is 54681, the list should separate odd and even digits into distinct
nodes: 5 -> 6 -> 1 -> 4 -> 8. Write a C program using a single linked list

#include <stdio.h>
#include <stdlib.h>

// Define a node structure for the linked list

typedef struct Node {
int digit;
struct Node* next;
} Node;

// Function to create a new node

Node* createNode(int digit) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->digit = digit;
newNode->next = NULL;
return newNode;
}

// Function to append a node to a linked list

void appendNode(Node** head, int digit) {
Node* newNode = createNode(digit);
if (*head == NULL) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}

// Function to print the linked list

void printList(Node* head) {
while (head != NULL) {
printf("%d ", head->digit);
head = head->next;
}
printf("\n");
}

// Function to separate odd and even digits into two linked lists
void separateDigits(Node* head, Node** oddList, Node** evenList) {
while (head != NULL) {
if (head->digit % 2 == 0) {
appendNode(evenList, head->digit); // Even digits
} else {
appendNode(oddList, head->digit); // Odd digits
}
head = head->next;
}
}

int main() {
// Input the phone number as a linked list of digits
Node* phoneNumber = NULL;
Node* oddDigits = NULL;
Node* evenDigits = NULL;

int number = 54681;

// Insert digits into the phone number list
while (number > 0) {
appendNode(&phoneNumber, number % 10);
number /= 10;
}

// Reverse the phone number list to get digits in correct order

Node* reversedPhoneNumber = NULL;
while (phoneNumber != NULL) {
appendNode(&reversedPhoneNumber, phoneNumber->digit);
Node* temp = phoneNumber;
phoneNumber = phoneNumber->next;
free(temp);
}

// Separate the odd and even digits into two lists

separateDigits(reversedPhoneNumber, &oddDigits, &evenDigits);

// Output the result

printf("Odd digits: ");
printList(oddDigits);

printf("Even digits: ");

printList(evenDigits);
// Concatenate odd and even lists (odd first, then even)
Node* finalList = oddDigits;
if (oddDigits == NULL) {
finalList = evenDigits; // If odd list is empty, use even list
} else {
Node* temp = oddDigits;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = evenDigits; // Link odd and even lists
}

// Print the final result

printf("Final phone number (Odd + Even): ");
printList(finalList);

return 0;
}

Internal Examiner 2 HoD/CSE Dean Academics