Q.2 Explain memory fragmentation in detail.

Ans : Memory Fragmentation

Memory fragmentation occurs when free memory is divided into small, scattered blocks, which
can prevent large contiguous memory allocations even if there is enough free memory in total.
There are two main types:
1. External Fragmentation:
o This happens when free memory is divided into separate blocks between allocated
memory, making it difficult to find a single large block.
o Example: If you have 100 MB of free memory in several small chunks, you may not
be able to allocate a large block, like 50 MB, even though there’s enough memory
overall.
2. Internal Fragmentation:
o This occurs when allocated memory blocks have unused space inside them.
o Example: If you allocate memory in fixed sizes, like 8 KB blocks, but a program only
needs 6 KB, the remaining 2 KB in that block is wasted.
Causes of Fragmentation:
• Allocating and freeing memory of different sizes.
• Frequent allocation and deallocation.
Problems Due to Fragmentation:
• Wasted memory and reduced performance.
• Allocation failures when contiguous blocks are needed.
Solutions:
• Memory Compaction: Moves allocated memory blocks together to combine free space,
but is often slow.
• Paging: Divides memory into fixed-size pages, reducing external fragmentation.
• Buddy System: Allocates memory in powers of two, allowing adjacent blocks to be
combined.
• Garbage Collection (in managed languages like Java): Reclaims and compacts memory.
Q.8) Explain first fit, best fit and worst fit method with example.
Ans : Memory Allocation Methods
In memory management, processes are allocated memory blocks of varying sizes. Three
common methods used to allocate memory are First Fit, Best Fit, and Worst Fit. Each method
has different strategies for choosing a suitable memory block from the available free memory
blocks.
1. First Fit
The First Fit method allocates the first available memory block that is large enough to satisfy the
request. It scans memory from the beginning and stops as soon as it finds a block that is big
enough.
Example: Suppose we have the following free memory blocks:
• Block sizes: [100 KB, 500 KB, 200 KB, 300 KB, 600 KB]
Let's say a process requests 250 KB of memory.
• First Fit Process:
o The first block (100 KB) is too small.
o The second block (500 KB) is large enough, so we allocate it.
• Memory Allocation Result:
o After allocation: [100 KB, 250 KB allocated (250 KB remaining), 200 KB, 300 KB, 600
KB]
Advantages of First Fit
• Fast allocation, as it stops as soon as a suitable block is found.
• Minimizes search time.
Disadvantages of First Fit
• Can lead to external fragmentation as smaller free blocks may be left scattered in
memory.
2. Best Fit
The Best Fit method allocates the smallest free memory block that is large enough to satisfy the
request. It searches the entire list of available blocks to find the one that will leave the least
amount of unused space after allocation.
Example: Suppose we have the following free memory blocks:
• Block sizes: [100 KB, 500 KB, 200 KB, 300 KB, 600 KB]
If a process requests 250 KB:
• Best Fit Process:
o The best fit block is the 300 KB block (smallest block that can fit 250 KB).
• Memory Allocation Result:
 o After allocation: [100 KB, 500 KB, 200 KB, 50 KB (300 KB allocated), 600 KB]
Advantages of Best Fit
• Reduces wasted space in memory, as it leaves the smallest possible fragment.
Disadvantages of Best Fit
• Slower than First Fit, as it requires scanning the entire memory list.
• Can create many small gaps, increasing fragmentation over time.
3. Worst Fit
The Worst Fit method allocates the largest available memory block to the process. The idea is to
leave larger leftover blocks, which might be more useful for future allocations.
Example: Suppose we have the following free memory blocks:
• Block sizes: [100 KB, 500 KB, 200 KB, 300 KB, 600 KB]
If a process requests 250 KB:
• Worst Fit Process:
o The largest available block is 600 KB, so we allocate it.
• Memory Allocation Result:
o After allocation: [100 KB, 500 KB, 200 KB, 300 KB, 350 KB (600 KB allocated)]
Advantages of Worst Fit
• May reduce fragmentation by leaving larger memory blocks free for future allocations.
Disadvantages of Worst Fit
• Can lead to inefficient memory use, as large blocks are broken up for smaller allocations.
• Slower than First Fit due to the need to search for the largest block.
Q.10) Explain winding and unwinding phase of recursion.
Ans : Winding and Unwinding Phases of Recursion
In recursion, when a function calls itself, it goes through two distinct phases: the winding phase
(where recursive calls are made) and the unwinding phase (where recursive calls start returning).
1. Winding Phase : The winding phase refers to the phase in which recursive calls are being
made. During this phase:
• The function keeps calling itself with updated arguments until it reaches the base case,
which is a condition that stops further recursive calls.
• Each recursive call stores its state (its arguments and local variables) in the call stack, a
special memory structure that keeps track of all active function calls.
Example (Factorial Calculation): For a recursive function that calculates the factorial of n, the
function will keep calling itself until n is 1 (the base case):

def factorial(n):
if n == 1:
return 1 # base case
return n * factorial(n - 1)

For factorial(4), the winding phase goes as follows:

• factorial(4) calls factorial(3)
• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1) (base case)
Each of these calls is pushed onto the stack, and the recursion continues until the base case is
reached.
2. Unwinding Phase : The unwinding phase occurs when the base case is reached, and the
function starts returning values from the call stack in reverse order of the winding phase. This
phase "unwinds" the stack, with each call returning its result to the previous call in the stack.
Continuing with the example:
• When factorial(1) returns 1, it unwinds to factorial(2), which multiplies 2 * 1 and returns 2.
• Then factorial(2) returns 2 to factorial(3), which calculates 3 * 2 = 6 and returns 6.
• Finally, factorial(4) receives 6 and calculates 4 * 6 = 24.
The result of factorial(4) is 24, and the recursion is complete.
Q.11) State the application of stack.
Ans : Applications of Stack
A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle,
where elements are added and removed from the same end, called the top. Stacks
are widely used in various applications across computer science and software
development due to their LIFO behavior. Here are some common applications:
1. Expression Evaluation and Syntax Parsing:
o Application: Stacks are used in compilers and calculators to evaluate
expressions, especially those written in postfix (Reverse Polish
Notation) and to check for balanced parentheses in expressions.
o Example: Infix expressions (like (a + b) * c) are converted to postfix
(ab+c*) using a stack for easier evaluation by machines.
2. Function Call Management:
o Application: The system stack (call stack) is used to manage function
calls in programming languages. Each time a function is called, its
execution context (local variables, return address, etc.) is pushed onto
the stack, and it’s popped off when the function returns.
o Example: Recursive function calls use the stack to keep track of each
function's state, allowing the function to "wind and unwind" during
execution.
3. Undo Mechanism in Applications:
o Application: Stacks are used to implement the "undo" functionality in
text editors and other applications. Each change is pushed onto a
stack, and when the user undoes an action, the previous state is
popped from the stack.
o Example: In a text editor, each text change is stored on a stack;
pressing "undo" reverts to the most recent change by popping the
stack.
4. Backtracking Algorithms:
o Application: Stacks are used in backtracking algorithms where you
need to explore all possible options, such as solving mazes, puzzles,
and implementing depth-first search (DFS) in graph traversal.
o Example: In DFS, vertices are pushed to the stack as they are visited
and popped off as the algorithm backtracks to explore other branches.
5. Expression Conversion:
 o Application: Stacks help convert expressions from infix (human-
readable) to postfix or prefix forms, which are easier for machines to
process.
o Example: Converting (a + b) * c from infix to postfix using a stack results
in ab+c*.
6. Memory Management:
o Application: Stacks are used in memory allocation, particularly in
managing local variables in function calls.
o Example: When a function is called, the stack frame for that function's
local variables is pushed onto the stack and popped off when the
function exits.
7. Parsing and Compilers:
o Application: Stacks are essential in parsing syntax trees and
expression trees in compilers. They manage nested structures like
loops and function calls.
o Example: Parsing an expression like (a + (b * c)) involves pushing and
popping elements to check for syntax correctness.
8. Browser History:
o Application: Web browsers use a stack to store the history of pages
visited. When the user navigates back, the stack pops the most recent
page, while pushing the current page onto a forward history stack.
o Example: Visiting a new page pushes it onto the history stack; pressing
"back" pops the current page and loads the previous one.
Q.13) Define the term
i) Directed Graph
• A directed graph (or digraph) is a graph where each edge has a direction,
going from one vertex to another. This means each connection between
nodes is one-way, represented by arrows pointing from one node to another.
• Example: A social network where a "follow" is one-way, meaning user A can
follow user B without B following A.

ii) Minimum Spanning Tree

• A minimum spanning tree (MST) is a subset of the edges of a weighted,
undirected graph that connects all vertices without forming any cycles and
with the minimum possible total edge weight.
• Applications: MSTs are used in network design, like designing the most
efficient wiring layout for electrical grids or computer networks.

iii) Heap Sort

• Heap sort is a comparison-based sorting algorithm that uses a binary heap
data structure. It first transforms the array into a max-heap (or min-heap) and
then repeatedly extracts the maximum (or minimum) element, rebuilding the
heap after each extraction.
• Time Complexity: O(n log n)

iv) Undirected Graph

• An undirected graph is a graph where edges have no direction, meaning the
connection between any two nodes is two-way. If there's an edge between
nodes A and B, it can be traversed from A to B and vice versa.
• Example: A friendship network, where a friendship between two people is
mutual.
v) AVL Tree
• An AVL tree is a self-balancing binary search tree. Named after its inventors,
Adelson-Velsky and Landis, it maintains a balance factor of -1, 0, or 1 for each
node to ensure that the height of the tree remains logarithmic (O(log n)).
Whenever nodes are inserted or deleted, the tree re-balances itself through
rotations.
• Use: AVL trees are used in databases and memory management systems to
maintain quick access times.

vi) Hash Function

• A hash function is a function that takes an input (or "key") and returns a fixed-
size string of bytes. This value is typically used as an index in a hash table. A
good hash function minimizes collisions, where two keys map to the same
index.
• Applications: Hash functions are used in data retrieval, checksums,
cryptography, and caching.

vii) Collision
• In hashing, a collision occurs when two different keys produce the same
hash value and therefore point to the same location in a hash table. Collision
resolution techniques are used to handle these situations and ensure that
data can still be efficiently retrieved.

viii) Weighted Graph

• A weighted graph is a graph in which each edge is assigned a weight (or cost).
The weight represents the "cost" of traversing the edge, which could be a
physical distance, time, or any other metric.
• Example: A road network where distances between cities are the weights of
edges connecting nodes representing the cities.
Q.14) Write a short note on:
i) B+ Tree
• A B+ Tree is a type of self-balancing tree data structure that maintains sorted data
and allows for efficient insertion, deletion, and search operations. It is an
extension of the B-tree but has additional properties:
o Leaf nodes contain the actual values and are linked, making sequential
access faster.
o All data is stored in the leaf nodes, while internal nodes only store keys to
guide the search.
o Applications: B+ trees are widely used in database and file systems for
indexing due to their efficient search and range query performance.
ii) Threaded Binary Tree
• A threaded binary tree is a binary tree variant that uses null pointers to make tree
traversal more efficient. Normally, binary tree nodes have two pointers (left and
right), which may be null if there’s no child. In a threaded binary tree:
o These null pointers are replaced by "threads" to the in-order successor or
predecessor, depending on the type of threading (single or double).
o Advantages: Allows in-order traversal without needing a stack or recursion,
making traversal faster and using memory more efficiently.
iii) Expression Tree
• An expression tree is a binary tree used to represent expressions, typically in
mathematical or logical form.
o Operators are stored in internal nodes, and operands (variables or
constants) are stored in leaf nodes.
o The tree structure allows for easy evaluation of expressions by recursively
evaluating subtrees from the leaves up to the root.
o Example: For the expression (a + b) * (c - d), * is the root, with + and - as
internal nodes, and a, b, c, d as leaf nodes.
iv) Binary Search
• Binary search is an efficient algorithm to find an element in a sorted array or list. It
divides the search interval in half repeatedly until the target element is found or
the interval is empty.
o Algorithm: Start with the middle element. If it matches the target, return it. If
the target is smaller, search the left half; if larger, search the right half.
o Time Complexity: O(log n), making it highly efficient for large datasets.
o Requirements: Works only on sorted data.
v) Selection Sort
• Selection sort is a simple comparison-based sorting algorithm. It divides the input
list into a sorted and an unsorted part.
o Algorithm: Find the smallest (or largest) element in the unsorted part and
swap it with the first unsorted element. Repeat this process for each position
until the entire list is sorted.
o Time Complexity: O(n^2), making it inefficient for large datasets.
o Advantages: Simple to implement, with a minimal number of swaps, which
can be beneficial in some applications.
vi) BFS and DFS
• BFS (Breadth-First Search): A graph traversal algorithm that explores all nodes at
the current depth level before moving to the next depth level. BFS uses a queue
and is useful for finding the shortest path in unweighted graphs.
o Applications: Shortest path finding, peer-to-peer networks, and social
network analysis.
• DFS (Depth-First Search): A graph traversal algorithm that explores as far as
possible along each branch before backtracking. DFS uses a stack (or recursion)
and is suitable for pathfinding and detecting cycles.
o Applications: Pathfinding, maze solving, topological sorting, and finding
connected components.

vii) Game Tree

• A game tree is a tree structure that represents all possible moves in a game. Each
node represents a game state, while edges represent moves from one state to
another.
o Example: Chess, tic-tac-toe, and other two-player games use game trees to
represent possible game outcomes.
o Minimax Algorithm: Often used to evaluate nodes in the game tree by
choosing moves that maximize the player's advantage and minimize the
opponent's advantage.
o Applications: Used in AI for strategic games to calculate the best move for a
player by evaluating future moves.
Q.2) Write a program to implement if (isEmpty()) { cout << "Queue is
circular queue using array. empty.\n"; return; }
Ans : #include <iostream> int i = front;
using namespace std; cout << "Queue: ";
class CircularQueue { while (i != rear) { cout << queue[i] << "
"; i = (i + 1) % size; }
private:
cout << queue[rear] << endl;
int front, rear, size;
}
int* queue;
};
public:
int main() {
CircularQueue(int s) : front(-1), rear(-1),
size(s) { queue = new int[size]; } CircularQueue q(5);
CircularQueue() { delete[] queue; } q.enqueue(10); q.enqueue(20);
q.enqueue(30);
bool isFull() { return (rear + 1) % size ==
front; } q.display();
bool isEmpty() { return front == -1; } q.dequeue(); q.dequeue();
void enqueue(int item) { q.display();
if (isFull()) { cout << "Queue is full!\n"; q.enqueue(40); q.enqueue(50);
return; }
q.display();
rear = (rear + 1) % size;
return 0;
if (front == -1) front = 0;
}
queue[rear] = item;
OUTPUT :
cout << "Enqueued: " << item << endl;
Enqueued: 10
}
Enqueued: 20
void dequeue() {
Enqueued: 30
if (isEmpty()) { cout << "Queue is
Queue: 10 20 30
empty!\n"; return; }
Dequeued: 10
cout << "Dequeued: " << queue[front]
<< endl; Dequeued: 20

front = (front == rear) ? (front = rear = - Queue: 30

1) : (front + 1) % size;
Enqueued: 40
}
Enqueued: 50
void display() {
Queue: 30 40 50
Q.3) Write a program to implement stack cout << temp->data << " ";
ADT using linked list.
cout << endl;
Ans : #include <iostream>
}
using namespace std;
~Stack() { while (top) pop(); }
class Stack {
};
private:
int main() {
struct Node {
Stack s;
int data;
s.push(10);
Node* next;
s.push(20);
};
s.push(30);
Node* top;
s.display();
public:
s.pop();
Stack() : top(nullptr) {}
s.display();
void push(int value) {
s.push(40);
top = new Node{value, top};
s.display();
cout << "Pushed: " << value << endl;
return 0;
}
}
void pop() {
OUTPUT :
if (!top) { cout << "Stack is empty!\n";
Pushed: 10
return; }
Pushed: 20
cout << "Popped: " << top->data <<
endl; Pushed: 30

Node* temp = top; 30 20 10

top = top->next; Popped: 30

delete temp; 20 10

} Pushed: 40

bool isEmpty() { return !top; } 40 20 10

void display() {
if (!top) { cout << "Stack is empty.\n";
return; }
for (Node* temp = top; temp; temp =
temp->next)
Q.5) Write an algorithm to convert infix to Pop '(' and discard it.
postfix expression.
stack = [+, *]
Ans : Input: A + B * (C + D)
10.End of expression:
• Initialize:
Pop * and append to postfix.
stack = [], postfix = []
postfix = [A, B, C, D, +, *]
1. Scan 'A': Operand → Append to
Pop + and append to postfix.
postfix.
postfix = [A, B, C, D, +, *, +]
postfix = [A]
2. Scan '+': Operator → Push onto
stack. CODE

stack = [+] #include <iostream>

#include <stack>
3. Scan 'B': Operand → Append to
#include <cctype>
postfix.
using namespace std;
postfix = [A, B]
// Function to get precedence of
4. Scan '*': Operator → Higher
operators
precedence than +, push onto
stack. int precedence(char op) {

stack = [+, *] if (op == '+' || op == '-') {

5. Scan '(': Parenthesis → Push onto return 1;

stack.
}
stack = [+, *, (]
if (op == '*' || op == '/') {
6. Scan 'C': Operand → Append to
return 2;
postfix.
}
postfix = [A, B, C]
return 0;
7. Scan '+': Operator → Push onto
stack (inside parenthesis). }

stack = [+, *, (, +] // Function to perform infix to postfix

conversion
8. Scan 'D': Operand → Append to
postfix. string infixToPostfix(string infix) {

postfix = [A, B, C, D] stack<char> operators;

9. Scan ')': Closing parenthesis → Pop string postfix = "";

from stack until '(' is encountered. for (int i = 0; i < infix.length(); i++) {
Pop + and append to postfix. char c = infix[i];
postfix = [A, B, C, D, +] if (isalnum(c)) {
 postfix += c; return postfix;
} }
// If the character is an opening int main() {
parenthesis '(', push it to the stack
string infix;
else if (c == '(') {
cout << "Enter infix expression: ";
operators.push(c);
cin >> infix;
}
string postfix = infixToPostfix(infix);
else if (c == ')') {
cout << "Postfix expression: " << postfix
while (!operators.empty() && << endl;
operators.top() != '(') {
return 0;
postfix += operators.top();
}
operators.pop();
}
OUTPUT
operators.pop(); // Pop '(' from the
Enter infix expression: A+B*(C-D)
stack
}
Postfix expression: ABCD-*+
else if (c == '+' || c == '-' || c == '*' || c ==
'/') {
while (!operators.empty() &&
precedence(operators.top()) >=
precedence(c)) {
postfix += operators.top();
operators.pop();
}
operators.push(c);
}
}
// Pop all the remaining operators from
the stack to postfix
while (!operators.empty()) {
postfix += operators.top();
operators.pop();
}