Subject Code/Name: 24CB391/ Data Structures and Algorithms Branch/Sem.

/Year: CSE(Cyber)/III/II

Continuous Internal Assessment Test – 1

PART A

1 Give the general recurrence for divide and conquer algorithms

The general recurrence relation for Divide and Conquer algorithms is:
T(n) = a * T(n/b) + f(n)
Where:
• T(n) → Total time to solve a problem of size n
• a → Number of subproblems into which the problem is divided
• n/b → Size of each subproblem (problem is divided into equal parts of size n/b)
• f(n) → Time required to divide the problem and combine the results
2 Define an algorithm. List some essential properties of algorithms
Define an Algorithm:
An algorithm is a finite sequence of well-defined instructions used to solve a problem or
perform a task.
Essential Properties of an Algorithm
1. Finiteness – Must terminate after a limited number of steps
2. Definiteness – Each step must be clear and unambiguous
3. Input – Accepts zero or more inputs
4. Output – Produces at least one output
5. Effectiveness – All operations must be basic and feasible
3 Using python, create a deep copy of a nested list b=[[1,2],[3,4]]
import copy
b = [[1, 2], [3, 4]]
deep_b = [Link](b)
This creates a fully independent copy of b, including all nested elements—modifying
deep_b won’t affect b.
4 Given the loop for i in range(n): sum +=i, state its time complexity in Big O notation

The loop runs n times, and each iteration performs a constant-time addition.
Time Complexity: The loop runs n times, so the time complexity is O(n).
This is linear time, since the number of operations grows proportionally with n.
5 Write a Python code snippet to access a global variable inside a function
Accessing a Global Variable Inside a Function (Python)
# Global variable
greeting = "Hello, World!"
# Function accessing the global variable
def display():
print(greeting)
display()
This works because the function is reading the global variable, not modifying it.
6 A string “((a+b)*c)” is given. Use a stack-based approach to check whether the parentheses
are balanced. State the result.

expr = "((a+b)*c)"
stack = []
for char in expr:
if char == '(':
[Link](char)
elif char == ')':
if not stack:
print("Unbalanced")
break
[Link]()
 else:
print("Balanced" if not stack else "Unbalanced")
Result: The string "((a+b)*c)" is Balanced — every opening ( has a matching closing ).

7 Draw the diagram of a double-ended queue (deque) after inserting elements A, B, C at the
rear and deleting one element from the front

Deque Operation
Steps:
1. Insert A → rear
2. Insert B → rear
3. Insert C → rear
4. Delete one element → front (removes A)

Resulting Deque Diagram

Front → [ B ] [ C ] ← Rear
Explanation:
 A was inserted first and deleted from the front.
 B and C remain in the deque, with B now at the front.
8 Explain how traversal is performed in a singly linked list
Traversal in a Singly Linked List
Traversal involves visiting each node from the head to the end of the list by following the
next pointer.
Steps:
1. Start at the head node
2. Access and process the data
3. Move to the next node using .next
4. Repeat until the current node is None
9 State the uses of Abstract Datatype(ADT)
Uses of Abstract Data Type (ADT)
Abstract Data Types (ADTs) are used to:
1. Encapsulate Logic – Hide internal implementation and expose only essential
operations
2. Improve Modularity – Enable clean, maintainable code by separating interface
from implementation
3. Enhance Reusability – Allow different internal structures (e.g., array or linked list)
without changing usage
4. Support Robust Design – Prevent direct access to data, reducing errors and
improving security
ADTs like Stack, Queue, and Tree help structure complex programs with predictable
behavior and clean interfaces.
10 In a circular singly linked list, the nodes are [1->2->3->1]. Show the front and rear pointers
after deleting node 2.

Circular Singly Linked List – After Deleting Node 2

Initial List:
Front → [1] → [2] → [3] → (back to 1)
After Deletion of Node 2:
Front → [1] → [3] → (back to 1)
Pointers:
 Front points to node 1
 Rear points to node 3 (since it's the last before looping back)
The circular link is preserved: 3 → 1
 PART B

11. a) Construct an ADT for a Bank Account with the following specifications:
 Attributes: account_number, account_holder, balance
 Operations: deposit(amount), withdraw(amount), check_balance()
a. Build a python code to define a class BankAccount that implements the
above ADT
b. Ensure that withdrawal does not allow negative balance(use conditional
statements)
c. Develop two account objects, perform deposit and withdrawal operations,
and display the updated balances.
d. How the class implementation encapsulates the data and provides
abstraction
Answers:
Python Code Implementation:
class BankAccount:
def __init__(self, account_number, account_holder, balance=0):
self.__account_number = account_number
self.__account_holder = account_holder
self.__balance = balance

def deposit(self, amount):

self.__balance += amount
print(f"Deposited Rs.{amount}. Updated Balance: Rs.{self.__balance}")

def withdraw(self, amount):

if amount <= self.__balance:
self.__balance -= amount
print(f"Withdrawn Rs.{amount}. Updated Balance: Rs.{self.__balance}")
else:
print("Insufficient balance! Withdrawal denied.")

def check_balance(self):
print(f"Account Balance for {self.__account_holder}: Rs.{self.__balance}")

# Creating two account objects and performing operations

acc1 = BankAccount(101, "Alice", 5000)
acc2 = BankAccount(102, "Bob", 3000)

[Link](1500)
[Link](2000)
acc1.check_balance()

[Link](500)
[Link](4000)
acc2.check_balance()
Explanation – Encapsulation and Abstraction:
• **Encapsulation**: The data attributes (account_number, account_holder, balance)
are declared as private using double underscores (__). They can only be accessed or
modified through class methods. This prevents unauthorized access.

• **Abstraction**: The internal implementation details (like how balance is updated)

are hidden from the user. The user interacts only through defined methods such as
deposit(), withdraw(), and check_balance(), without knowing the underlying logic.

Thus, the class provides both data security and simplicity through encapsulation and
abstraction.
 OR
11. b) i. Differentiate Data types, Dat structures and Abstract Data Types (5m)
ii. Identify the different types of namespaces in Python. Provide a small code example
to illustrate each type (8m)
i. Difference Between Data Types, Data Structures, and Abstract Data Types
Concept Definition Examples Key Focus

Basic classification of data that

int, float, str, Nature of
Data Types defines the kind of value a variable
bool data
holds

Organized collection of data that

list, dict, set, Organization
Data Structures allows efficient access and
tuple and storage
modification

Logical model defining operations on Stack,

Abstract Data Behavior and
data, independent of Queue,
Types (ADTs) operations
implementation Tree, Graph

Analogy:
 Data types = building blocks (e.g., bricks)
 Data structures = how bricks are arranged (e.g., wall, house)
 ADTs = blueprint of what the structure should do (e.g., open door, store
items)

ii. Types of Namespaces in Python (8 marks)

Python uses namespaces to avoid naming conflicts. There are four main types:
1. Built-in Namespace
Created when the Python interpreter starts. Includes functions like print(),
len(), etc.
print(len("HelloWorld")) # 'len' is from built-in namespace
2. Global Namespace
Created when a module or script is run. Variables and functions defined at
the top level belong here.
brand = "HelloWorld" # Global namespace
def show_brand():
print(brand) # Accessing global variable
3. Local Namespace
Created inside functions. Contains names defined within that function.
def create_product():
product_name = "Planner" # Local namespace
print(product_name)
4. Enclosing Namespace (Nonlocal)
Exists in nested functions. The inner function can access variables from the
outer function.
def outer():
category = "Digital"
def inner():
print(category) # Enclosing namespace

inner()
LEGB Rule: Python resolves names in the order: Local → Enclosing → Global → Built-
in

12 a) i. Design a class hierarchy for the scenario:

  Person (base class) with attributes: name, ID
 Student (derived class) with attributes: grade
 Faculty(derived class) with attributes: department
a. Develop a Python code snippet to define the classes using inheritance
b. Implement a method display_info() in the base class and override it in derived
classes to include class-specific information.
c. Create at least one object of each class, call display_info() for each and illustrate
polymorphism
ii. Compare Single and Multiple Inheritance with example

i. Class Hierarchy with Inheritance and Polymorphism

a. Define Classes Using Inheritance

# Base class
class Person:
def __init__(self, name, ID):
[Link] = name
[Link] = ID

def display_info(self):
print(f"Name: {[Link]}, ID: {[Link]}")

# Derived class: Student

class Student(Person):
def __init__(self, name, ID, grade):
super().__init__(name, ID)
[Link] = grade

def display_info(self):
print(f"Name: {[Link]}, ID: {[Link]}, Grade: {[Link]}")

# Derived class: Faculty

class Faculty(Person):
def __init__(self, name, ID, department):
super().__init__(name, ID)
[Link] = department

def display_info(self):
print(f"Name: {[Link]}, ID: {[Link]}, Department: {[Link]}")

b. Method Overriding with display_info()

 The base class Person has a generic display_info() method.
 Both Student and Faculty override it to include their specific attributes.

c. Create Objects and Illustrate Polymorphism

# Create objects
p = Person("Alex", 1001)
s = Student("Bala", 1002, "A+")
f = Faculty("Dr. Kumar", 1003, "Computer Science")

# Polymorphic behavior
for individual in [p, s, f]:
individual.display_info()

Output:
Name: Alex, ID: 1001
 Name: Bala, ID: 1002, Grade: A+
Name: Dr. Kumar, ID: 1003, Department: Computer Science
Polymorphism: The same method display_info() behaves differently based on the
object type.

ii. Compare Single and Multiple Inheritance

Feature Single Inheritance Multiple Inheritance
One child class inherits from One child class inherits from multiple
Definition
one parent parents
Can be complex due to method
Simplicity Easier to manage and debug
resolution order
Example Student(Person) Researcher(Student, Faculty)

Single Inheritance Example

class Animal:
def sound(self):
print("Generic sound")

class Dog(Animal):
def sound(self):
print("Woof!")

Multiple Inheritance Example

class Swimmer:
def swim(self):
print("Swimming")

class Flyer:
def fly(self):
print("Flying")

class Duck(Swimmer, Flyer):

pass

d = Duck()
[Link]() # Swimming
[Link]() # Flying

Python uses Method Resolution Order (MRO) to resolve conflicts in multiple

inheritance.

OR
12.b) i. Explain shallow copying and deep copying in Python
ii. Given the following Python Code:
import copy
employees = [
{‘id’: 1, ‘name’:’Alice’,’projects’:[‘P1’,’P2’]};
{‘id’: 2, ‘name’:Bob,’projects’:[‘P3’]};
]
a. Develop Python code to create a shallow copy of the employees list and
demonstrate how modifying a nested list in the original affects the copy.
b. Develop Python code to create a deep copy of the employees list and
demonstrate that modifications in the original do not affect the copied list.

i. Shallow Copy vs Deep Copy in Python

 Shallow Copy
 Creates a new object but copies references to nested objects.
 Changes to nested elements in the original affect the copy.
Deep Copy
 Creates a new object and recursively copies all nested objects.
 Changes to the original do not affect the copy.

Use the copy module:

import copy
[Link](obj) # Shallow copy
[Link](obj) # Deep copy

ii. Python Code Example with employees List

Original List
import copy

employees = [
{'id': 1, 'name': 'Alice', 'projects': ['P1', 'P2']},
{'id': 2, 'name': 'Bob', 'projects': ['P3']}
]

a. Shallow Copy and Nested Modification

shallow_copy = [Link](employees)

# Modify nested list in original

employees[0]['projects'].append('P4')

# Observe effect on shallow copy

print("Original:", employees)
print("Shallow Copy:", shallow_copy)

Result: Both employees and shallow_copy show 'P4' in Alice’s project list—because
the nested list is shared.

b. Deep Copy and Isolation

deep_copy = [Link](employees)

# Modify nested list in original

employees[1]['projects'].append('P5')

# Observe effect on deep copy

print("Original:", employees)
print("Deep Copy:", deep_copy)

Result: Only employees shows 'P5' in Bob’s project list—deep_copy remains

unchanged.

13.a) Elaborate about the asymptotic notations with appropriate examples

Asymptotic Notations in Algorithm Analysis

Asymptotic notations describe the growth rate of an algorithm’s time or space
complexity as the input size n becomes very large. They help us compare algorithms
independent of hardware or implementation details.
 1. Big-O Notation (O) – Upper Bound / Worst Case
 Describes the maximum time an algorithm can take.
 Used to analyze worst-case performance.
Example:
If an algorithm takes f(n) = 3n + 2 steps, then
[ f(n) = O(n) ]

It means the algorithm will not take more than linear time for large n.

2. Omega Notation (Ω) – Lower Bound / Best Case

 Describes the minimum time an algorithm will take.
 Used to analyze best-case performance.
Example:
If f(n) = 3n + 2, then
[ f(n) = Ω(n) ]

It guarantees the algorithm takes at least linear time.

3. Theta Notation (Θ) – Tight Bound / Average Case

 Describes both upper and lower bounds.
 Used when the algorithm always takes a predictable amount of time.
Example:
If f(n) = 3n + 2, then
[ f(n) = Θ(n) ]

It means the algorithm consistently takes linear time.

Summary Table
Notation Meaning Use Case Example Function Interpretation
O(n) Upper bound Worst case 3n + 2 ≤ linear time
Ω(n) Lower bound Best case 3n + 2 ≥ linear time
Θ(n) Tight bound Average case 3n + 2 ≈ linear time

Real-Life Analogy
Imagine you're driving from Chennai to Coimbatore:
 Big-O: Worst-case time (traffic, rain)
 Omega: Best-case time (empty roads)
 Theta: Typical time under normal conditions

OR
13.b) i. A warehouse wants to find the maximum quantity among n products using divide-
and-conquer. Write a recursive pseudocode to solve this.
ii. ALGORITHM Q(n)
//Input: A positive integer n
If n=1 return 1
Else return Q(n-1)+2*n-1
Identify the basic operation in the algorithm. Setup the recurrence relation for the
number of times the algorithm’s basic operation is executed and solve it using back
substitution.

i. Recursive Pseudocode – Maximum Quantity Using Divide and Conquer

Goal: Find the maximum quantity among n products stored in an array Q[0...n-1].
Pseudocode
FUNCTION FindMax(Q, low, high)
IF low == high THEN
 RETURN Q[low]
ELSE
mid ← (low + high) // 2
max1 ← FindMax(Q, low, mid)
max2 ← FindMax(Q, mid + 1, high)
RETURN max(max1, max2)
Explanation
 Divide: Split the array into two halves.
 Conquer: Recursively find the max in each half.
 Combine: Return the greater of the two.
Time Complexity:
[ T(n) = 2T(n/2) + O(1) -> O(n) ]

ii. Analyzing ALGORITHM Q(n)

Given:
Q(n):
if n == 1:
return 1
else:
return Q(n-1) + 2*n - 1
Basic Operation:
 The addition Q(n-1) + 2n - 1 is the basic operation.

Recurrence Relation:
Let C(n) be the number of times the basic operation is executed.
[ C(n) = C(n-1) + 1,\quad \text{with } C(1) = 0 ]

Solving by Back Substitution:

[ \begin{align*} C(n) &= C(n-1) + 1 \ &= C(n-2) + 1 + 1 \ &= C(n-3) + 1 + 1 + 1 \ &\dots \
&= C(1) + (n - 1) \ &= 0 + (n - 1) \end{align*} ]

Final Answer:
[ C(n) = n - 1 ]

14 a) A university’s registrar office manages a singly linked list of student records. Each
node stores a Student’s ID(integer) and their GPA (A floating-point number). The list is
kept sorted in ascending order of student IDs.
i. Explain the concept of a “head” and a “tail” in a singly linked list
ii. Develop a C function manage_records(Node** head, int student_id, float
new_gpa). This function will perform a combined search, update and insertion
operation. The function should:
 Search: Traverse the list to find if a student with the given student_id already
exists
 Update: If the student is found, update their GPA to the new_gpa
 Insertion: If the student is not found, the function must create a new node
with the given ID and GPA and insert it into the correct sorted position in the
list to maintain the ascending order of student IDs.

i. Concept of “Head” and “Tail” in a Singly Linked List

 Head:
The first node in a singly linked list. It acts as the entry point to the list. All
traversals begin from the head.
 Tail:
 The last node in the list. Its next pointer is NULL, indicating the end of the
list. Unlike doubly linked lists, singly linked lists don’t have a backward
reference from tail to previous nodes.
Example:
Head → [ID: 101, GPA: 3.5] → [ID: 102, GPA: 3.8] → [ID: 103, GPA: 3.9] → NULL
↑
Tail

ii. C Function: manage_records for Search, Update, and Sorted Insertion

C Code Snippet
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

int student_id;
float gpa;
struct Node* next;
} Node;

void manage_records(Node** head, int student_id, float new_gpa) {

Node *prev = NULL, *curr = *head;

// Traverse to find the correct position or existing node

while (curr != NULL && curr->student_id < student_id) {
prev = curr;
curr = curr->next;
}

// If student already exists, update GPA

if (curr != NULL && curr->student_id == student_id) {
curr->gpa = new_gpa;
return;
}

// Create new node

Node* new_node = (Node*)malloc(sizeof(Node));
new_node->student_id = student_id;
new_node->gpa = new_gpa;
new_node->next = curr;

// Insert at head or between nodes

if (prev == NULL) {
*head = new_node;
} else {
prev->next = new_node;
}
}

Explanation
 Search: Traverses until it finds the student or the correct insert position.
 Update: If found, updates GPA.
 Insert: If not found, inserts the new node in sorted order.

Maintains ascending order of student IDs.

 OR
14 b) i. Compare and contrast the array-based implementation and the linked list
implementation of the List ADT
ii. A web browser uses a doubly linked list to store the history of visited web pages.
Each node in the list represents a web page. How the prev and next pointers are used
to implement the “Back” and “Forward” navigation buttons. Construct a C function
go_back(Node* current) that returns the prev node and go_forward(Node* current)
that returns the next node.

i. Array-Based vs Linked List Implementation of List ADT

Feature Array-Based List Linked List
Fixed size (static or dynamic
Memory Allocation Dynamic (node-by-node)
block)
Access Time Fast (O(1) via index) Slow (O(n) traversal)
Efficient (O(1) if pointer
Insertion/Deletion Costly (O(n) due to shifting)
known)
May waste space due to over-
Memory Usage Efficient, no unused space
allocation
Poorer (non-contiguous
Cache Performance Better (contiguous memory)
memory)
Ease of Slightly complex (pointer
Simple
Implementation management)

Summary:
 Use arrays when fast indexing is needed and size is predictable.
 Use linked lists when frequent insertions/deletions are required.

ii. Browser History Navigation Using Doubly Linked List

Concept
Each node stores a web page and has:
 prev → pointer to the previous page
 next → pointer to the next page
Back Button: Moves to prev
Forward Button: Moves to next

C Function Implementation
typedef struct Node {
char* url;
struct Node* prev;
struct Node* next;
} Node;

// Go back to previous page

Node* go_back(Node* current) {
if (current != NULL && current->prev != NULL)
return current->prev;
return current; // Stay on current if no previous
}

// Go forward to next page

Node* go_forward(Node* current) {
if (current != NULL && current->next != NULL)
return current->next;
 return current; // Stay on current if no next
}

Usage Example:
current = go_back(current); // Navigate back
current = go_forward(current); // Navigate forward

15 a) A simple operating system uses a circularly linked list to distribute incoming processes
to three different processing cores(Core 1, Core 2, Core 3). Each node stores a process
ID. The system distributes the processes in a round-robin fashion.
i. Define the round-robin scheduling algorithm. Why is a circular linked list a suitable
data structure to model this algorithm?
ii. Construct a C function distribute_and_search(Node** head, int num_processes, int
target_id) that performs a round-robin distribution for num_processes to three cores.
The function should traverse the list and for each processes, assign it a core (Core1,
then core 2, then Core 3 and go back to 1). After distribution, the function must
search for a specific process by its target_id and print which core it was assigned to.
You must handle the search after the distribution is complete.
iii. Provide the logic of your round-robin distribution and the search process.

i. Round-Robin Scheduling & Circular Linked List

Round-Robin Scheduling Algorithm
Round-robin scheduling assigns each process a fixed time slice (quantum) and cycles
through all processes in order. It ensures fair CPU time distribution and avoids
starvation.
Key Features:
 Time-sharing
 Equal priority
 Cyclic execution
Why Circular Linked List?
A circular linked list naturally supports round-robin behavior:
 The last node points back to the first.
 Enables continuous traversal without resetting pointers.
 Efficient for cyclic scheduling of processes.
Think of it like a rotating queue—once you reach the end, you loop back to the
beginning.

ii. C Function: distribute_and_search

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

typedef struct Node {

int process_id;
int core_assigned; // 1, 2, or 3
struct Node* next;
} Node;

void distribute_and_search(Node** head, int num_processes, int target_id) {

if (*head == NULL) return;

Node* current = *head;

int core = 1;
int count = 0;

// Round-robin distribution
 do {
current->core_assigned = core;
core = (core % 3) + 1; // Cycle through 1 → 2 → 3 → 1
current = current->next;
count++;
} while (current != *head && count < num_processes);

// Search for target_id

current = *head;
count = 0;
do {
if (current->process_id == target_id) {
printf("Process %d assigned to Core %d\n", target_id, current->core_assigned);
return;
}
current = current->next;
count++;
} while (current != *head && count < num_processes);

printf("Process %d not found\n", target_id);

}

iii. Logic Explanation

Round-Robin Distribution
 Start from the head node.
 Assign cores in sequence: Core 1 → Core 2 → Core 3 → repeat.
 Use (core % 3) + 1 to cycle through cores.
Search Process
 Traverse the circular list.
 Compare each node’s process_id with target_id.
 If found, print the assigned core.
 If not found after full traversal, report absence.
This approach ensures fair distribution and efficient lookup in a cyclic structure.

OR
15 b) An online ticket booking system stores booking IDs in an array. As new bookings
arrive, they must be added, and cancellations must be handled. Apply the concept of
arrays as an ADT by developing C functions for append(), prepend(), insert(pos,
element), and delete(pos). Demonstrate their use with step by step explanation and
code in managing booking IDs when:
 A new booking arrives at the end
 A VIP booking must be added at the beginning
 A booking is inserted at a given slot and
 A cancelled booking must be removed

Array as an ADT in Ticket Booking System

An Array ADT provides a fixed-size, index-based structure with operations like:
 Append: Add at the end
 Prepend: Add at the beginning
 Insert: Add at a specific position
 Delete: Remove from a specific position

C Code: Array ADT Operations

#include <stdio.h>
#define MAX 100

typedef struct {
int data[MAX];
int size;
} BookingArray;

// Append: Add at end

void append(BookingArray* arr, int booking_id) {
if (arr->size < MAX) {
arr->data[arr->size++] = booking_id;
}
}

// Prepend: Add at beginning

void prepend(BookingArray* arr, int booking_id) {
if (arr->size < MAX) {
for (int i = arr->size; i > 0; i--) {
arr->data[i] = arr->data[i - 1];
}
arr->data[0] = booking_id;
arr->size++;
}
}

// Insert at position (0-based index)

void insert(BookingArray* arr, int pos, int booking_id) {
if (arr->size < MAX && pos >= 0 && pos <= arr->size) {
for (int i = arr->size; i > pos; i--) {
arr->data[i] = arr->data[i - 1];
}
arr->data[pos] = booking_id;
arr->size++;
}
}

// Delete from position (0-based index)

void delete(BookingArray* arr, int pos) {
if (pos >= 0 && pos < arr->size) {
for (int i = pos; i < arr->size - 1; i++) {
arr->data[i] = arr->data[i + 1];
}
arr->size--;
}
}

// Display current bookings

void display(BookingArray arr) {
printf("Current Bookings: ");
for (int i = 0; i < [Link]; i++) {
printf("%d ", [Link][i]);
}
printf("\n");
}

Demonstration: Step-by-Step Booking Management

 int main() {
BookingArray bookings = {.size = 0};

// 1. New booking arrives at the end

append(&bookings, 101);
append(&bookings, 102);
display(bookings); // Output: 101 102

// 2. VIP booking added at the beginning

prepend(&bookings, 999);
display(bookings); // Output: 999 101 102

// 3. Insert booking at position 1

insert(&bookings, 1, 888);
display(bookings); // Output: 999 888 101 102

// 4. Cancel booking at position 2 (removes 101)

delete(&bookings, 2);
display(bookings); // Output: 999 888 102

return 0;
}

Output
Current Bookings: 101 102
Current Bookings: 999 101 102
Current Bookings: 999 888 101 102
Current Bookings: 999 888 102

PART C

16 a) A scientific calculator evaluates complex infix expressions with operators +-*/^ and
multiple nested parenthesis.
It uses array-based stacks for infix-to-postfix conversion and another stack for postfix
evaluation.
Expression: ((3+5)*2^(3-1))/(4-2)
i. Evaluate the use of two stacks (operator & operand) versus other approaches
ii. Construct a C program for infix-to-postfix conversion and postfix evaluation, including
error checks for mismatched parentheses and overflow
iii. Simulate step-by-step stack operations showing intermediate postfix and operand
stack states

i. Why Use Two Stacks: Operator & Operand

Using two stacks—one for operators and one for operands—is a classic and efficient
approach for expression evaluation:
Advantages:
 Operator Stack: Handles precedence and associativity rules during infix-to-
postfix conversion.
 Operand Stack: Stores values during postfix evaluation for quick computation.
Compared to Other Approaches:
Approach Pros Cons
Clear separation of logic; Requires careful precedence
Two-stack method
efficient handling
Single stack with Harder to manage nested
Less memory usage
parsing parentheses
Complex to implement for
Recursive parsing Elegant for compilers
calculators
Conclusion: Two stacks offer clarity, modularity, and are ideal for real-time calculators.

ii. C Program: Infix to Postfix + Postfix Evaluation

Expression: ((3+5)*2^(3-1))/(4-2)

Key Features:
 Handles + - * / ^ operators
 Supports nested parentheses
 Includes error checks for:
o Mismatched parentheses
o Stack overflow
C Code Snippet (Simplified)
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>

#define MAX 100

char op_stack[MAX];
int top_op = -1;

double val_stack[MAX];
int top_val = -1;

void push_op(char ch) {

if (top_op < MAX - 1) op_stack[++top_op] = ch;
else printf("Operator stack overflow\n");
}

char pop_op() {
return (top_op >= 0) ? op_stack[top_op--] : '\0';
}

void push_val(double val) {

if (top_val < MAX - 1) val_stack[++top_val] = val;
else printf("Value stack overflow\n");
}

double pop_val() {
return (top_val >= 0) ? val_stack[top_val--] : 0;
}

int precedence(char op) {

if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
 if (op == '+' || op == '-') return 1;
return 0;
}

int is_operator(char ch) {

return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}

// Infix to Postfix Conversion

void infix_to_postfix(const char* expr, char* postfix) {
int i = 0, k = 0;
while (expr[i]) {
if (isdigit(expr[i])) {
postfix[k++] = expr[i];
} else if (expr[i] == '(') {
push_op(expr[i]);
} else if (expr[i] == ')') {
while (top_op >= 0 && op_stack[top_op] != '(')
postfix[k++] = pop_op();
if (top_op < 0) {
printf("Mismatched parentheses\n");
return;
}
pop_op(); // Remove '('
} else if (is_operator(expr[i])) {
while (top_op >= 0 && precedence(op_stack[top_op]) >= precedence(expr[i]))
postfix[k++] = pop_op();
push_op(expr[i]);
}
i++;
}
while (top_op >= 0) {
if (op_stack[top_op] == '(') {
printf("Mismatched parentheses\n");
return;
}
postfix[k++] = pop_op();
}
postfix[k] = '\0';
}

// Postfix Evaluation
double evaluate_postfix(const char* postfix) {
int i = 0;
while (postfix[i]) {
if (isdigit(postfix[i])) {
push_val(postfix[i] - '0');
} else if (is_operator(postfix[i])) {
double b = pop_val();
double a = pop_val();
switch (postfix[i]) {
case '+': push_val(a + b); break;
case '-': push_val(a - b); break;
case '*': push_val(a * b); break;
case '/': push_val(a / b); break;
case '^': push_val(pow(a, b)); break;
}
 }
i++;
}
return pop_val();
}

iii. Stack Simulation for Expression: ((3+5)*2^(3-1))/(4-2)

Step 1: Infix to Postfix Conversion

Postfix: 35+23 1-^*42-/
Operator Stack (during conversion):
Push '(': [ ( ]
Push '(': [ (, ( ]
Push '+': [ (, (, + ]
Pop '+': → postfix: 3 5 +
Push '*': [ * ]
Push '^': [ *, ^ ]
Push '-': [ *, ^, - ]
Pop '-': → postfix: 3 5 + 2 3 1 -
Pop '^': → postfix: 3 5 + 2 3 1 - ^
Pop '*': → postfix: 3 5 + 2 3 1 - ^ *
Push '/': [ / ]
Pop '/': → postfix: 3 5 + 2 3 1 - ^ * 4 2 - /

Step 2: Postfix Evaluation

Postfix: 35+23 1-^*42-/
Operand Stack Simulation:
Push 3 → [3]
Push 5 → [3, 5]
Apply '+' → [8]
Push 2 → [8, 2]
Push 3 → [8, 2, 3]
Push 1 → [8, 2, 3, 1]
Apply '-' → [8, 2, 2]
Apply '^' → [8, 4]
Apply '*' → [32]
Push 4 → [32, 4]
Push 2 → [32, 4, 2]
Apply '-' → [32, 2]
Apply '/' → [16]

Final Result: 16

OR
16 b) An emergency room in a hospital uses a priority queue to manage patients. Each
patient has:
Name (A,B,C,…)
Priority (1= highest, 3=lowest).
Patients with higher priority are always treated first. If two patients have the same
priority, they are served in arrival order (FCFS).

Patient Priority Position

A 2 Front
B 1
C 3
 D 2 Rear

1. Using the above data, Perform the following operations step by step, updating the
diagram after each step:
Insertion: Add a new patient E(Priority 1).
Deletion: Remove the highest priority patient for treatment
Peek: Show which patient is next to be treated without removing them.

2. Infer the traversal operation to display all patients in the queue in order of treatment
priority.

Priority Queue Setup

Each patient has:
 Priority: 1 (highest) → 3 (lowest)
 Arrival Order: First-Come-First-Served (FCFS) within same priority
Initial Queue State
Priority 1 → [ B ]
Priority 2 → [ A, D ] // A arrived before D
Priority 3 → [ C ]

1. Step-by-Step Operations
Insertion: Add E (Priority 1)
E is added after B (same priority, FCFS applies)
Priority 1 → [ B, E ]
Priority 2 → [ A, D ]
Priority 3 → [ C ]
Diagram After Insertion
┌────────────┐
│ Priority 1 │ → B → E
│ Priority 2 │ → A → D
│ Priority 3 │ → C
└────────────┘

Deletion: Remove Highest Priority Patient

Remove B (first in Priority 1 queue)
Priority 1 → [ E ]
Priority 2 → [ A, D ]
Priority 3 → [ C ]
Diagram After Deletion
┌────────────┐
│ Priority 1 │ → E
│ Priority 2 │ → A → D
│ Priority 3 │ → C
└────────────┘
B is treated first

Peek: Who’s Next to Be Treated?

Peek at the front of Priority 1 → E
Next Patient: E

2. Traversal Logic for Treatment Order

To display patients in order of treatment:
Traversal Strategy
1. Traverse Priority 1 queue in arrival order
2. Then Priority 2 queue
 3. Then Priority 3 queue
Final Queue State
Treatment Order:
→ E (Priority 1)
→ A (Priority 2)
→ D (Priority 2)
→ C (Priority 3)