CONTINUOUS INTERNAL ASSESSMENT – 1 ANSWER KEY

PART – A (2x10=20)
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
Finiteness – Must terminate after a limited number of steps
Definiteness – Each step must be clear and unambiguous
input – Accepts zero or more inputs
Output – Produces at least one output
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)

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:
Insert A → rear
Insert B → rear
Insert C → rear
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:
Start at the head node
Access and process the data
Move to the next node using .next
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:
Encapsulate Logic – Hide internal implementation and expose only essential operations
Improve Modularity – Enable clean, maintainable code by separating interface from implementation
Enhance Reusability – Allow different internal structures (e.g., array or linked list) without changing
usage
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 (5x13=65)
11 Construct an ADT for a Bank Account with the following specifications:
11 Attributes: account_number, account_holder, balance
11 Operations: deposit(amount), withdraw(amount), check_balance()
a) Build a python code to define a class BankAccount that implements the above ADT
Ensure that withdrawal does not allow negative balance(use conditional statements)
Develop two account objects, perform deposit and withdrawal operations, and display the
updated balances.
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. i. Differentiate Data types, Dat structures and Abstract Data Types (5m)
b) 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
Key
Concept Definition Examples
Focus
Basic
classification
Data of data that int, float, str, Nature of
Types defines the bool data
kind of value a
variable holds
Organized
collection of
Data data that Organiza
list, dict, set,
Structur allows tion and
tuple
es efficient storage
access and
modification
Logical model
defining
Abstract Behavior
operations on
Data Stack, Queue, and
data,
Types Tree, Graph operation
independent of
(ADTs) s
implementatio
n
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

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
Develop a Python code snippet to define the classes using inheritance
Implement a method display_info() in the base class and override it in derived classes to
include class-specific information.
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 One child class
Definition inherits from one inherits from multiple
parent parents
Can be complex due
Easier to manage
Simplicity to method resolution
and debug
order
Researcher(Student,
Example Student(Person)
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 i. Explain shallow copying and deep copying in Python
.b) ii. Given the following Python Code:
import copy
employees = [
{‘id’: 1, ‘name’:’Alice’,’projects’:[‘P1’,’P2’]};
{‘id’: 2, ‘name’:Bob,’projects’:[‘P3’]};
]
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.
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 Elaborate about the asymptotic notations with appropriate examples

.a)

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
Exam
Notati Meani Use ple Interpretat
on ng Case Functi ion
on
Upper Worst ≤ linear
O(n) 3n + 2
bound case time
Lowe
Best ≥ linear
Ω(n) r 3n + 2
case time
bound
Aver
Tight ≈ linear
Θ(n) age 3n + 2
bound time
case

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 i. A warehouse wants to find the maximum quantity among n products using divide-and-
.b) 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 university’s registrar office manages a singly linked list of student records. Each node stores
a) 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
1 i. Compare and contrast the array-based implementation and the linked list implementation of the List
4 ADT
b 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
Memory Allocation Dynamic (node-by-node)
dynamic block)
Access Time Fast (O(1) via index) Slow (O(n) traversal)
Costly (O(n) due to Efficient (O(1) if pointer
Insertion/Deletion
shifting) known)
May waste space due to
Memory Usage Efficient, no unused space
over-allocation
Better (contiguous Poorer (non-contiguous
Cache Performance
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

1 A simple operating system uses a circularly linked list to distribute incoming processes to three
5 different processing cores(Core 1, Core 2, Core 3). Each node stores a process ID. The system
a 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
1 An online ticket booking system stores booking IDs in an array. As new bookings arrive, they must be
5 added, and cancellations must be handled. Apply the concept of arrays as an ADT by developing C
b 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)