Govt. E. Raghvendra Rao P. G.
Science College
Bilaspur (CG)
Department of Computer Application
ASSIGNMENT
Subject: Data Structure
Submitted By:
Name: Himanshu Hirulkar
Class: BCA 2nd Semester
Roll No: 25195
Enrollment No: ABVV/GERS/2025/0951
Submitted To:
Sanjeev Pandey Sir
INDEX
S. No Content Page No.
1. Dequeue Operations with Algorithms 03-06
2. Radix Sort on Given Array 07-09
3. Infix to Prefix and Postfix Conversion 09-10
4. AVL Tree Insertion 11-12
5. Prim’s Algorithm (Minimum Spanning Tree) 13-15
Page 2 of 15
Q.1 Write all several operations of Dequeue with algorithms
1. Definition
A Dequeue (Double Ended Queue) is a linear data structure in which insertion and deletion
operations can be performed from both ends, i.e., front and rear. It is a more flexible form of
a queue because elements can be added or removed from both sides.
2. Types of Dequeue
(i) Input Restricted Dequeue
In this type, insertion is allowed only at one end (rear), while deletion can be performed
from both front and rear.
(ii) Output Restricted Dequeue
In this type, deletion is allowed only at one end (front), while insertion can be performed
from both ends.
3. Representation of Dequeue
A dequeue can be implemented using an array. Two variables are used:
• front → points to the first element
• rear → points to the last element
4. Basic Operations of Dequeue
1. Insert at Front
2. Insert at Rear
3. Delete from Front
4. Delete from Rear
5. Conditions
Overflow Condition:
Occurs when the deque is full.
rear == MAX - 1
Underflow Condition:
Occurs when the deque is empty.
front == -1 OR front > rear
Page 3 of 15
6. Algorithms
(i) Insert at Front
Algorithm: InsertFront(x)
Step 1: If front == 0
Print "Overflow"
Stop
Step 2: If front == -1
front = rear = 0
Else
front = front - 1
Step 3: deque[front] = x
Step 4: Stop
(ii) Insert at Rear
Algorithm: InsertRear(x)
Step 1: If rear == MAX - 1
Print "Overflow"
Stop
Step 2: If front == -1
front = rear = 0
Else
rear = rear + 1
Step 3: deque[rear] = x
Step 4: Stop
(iii) Delete from Front
Algorithm: DeleteFront()
Step 1: If front == -1
Print "Underflow"
Stop
Step 2: data = deque[front]
Step 3: If front == rear
front = rear = -1
Else
front = front + 1
Step 4: Return data
Page 4 of 15
(iv) Delete from Rear
Algorithm: DeleteRear()
Step 1: If rear == -1
Print "Underflow"
Stop
Step 2: data = deque[rear]
Step 3: If front == rear
front = rear = -1
Else
rear = rear - 1
Step 4: Return data
7. Diagram
Draw the following diagrams in your assignment:
Initial Dequeue:
[ 10 , 20 , 30 ]
↑ ↑
front rear
After InsertFront(5):
[ 5 , 10 , 20 , 30 ]
↑ ↑
front rear
After DeleteRear():
[ 5 , 10 , 20 ]
↑ ↑
front rear
8. Advantages of Dequeue
• Allows insertion and deletion from both ends
• More flexible than a simple queue
• Can be used as both stack and queue
Page 5 of 15
9. Applications of Dequeue
• Undo and redo operations
• Palindrome checking
• Sliding window problems
• Task scheduling
Conclusion
A dequeue is a powerful data structure that provides flexibility in performing operations
from both ends. It is widely used in various applications where efficient insertion and
deletion are required.
Page 6 of 15
Q.2 Apply Radix Sort on the following numbers: 170, 45, 75, 90, 802, 24, 2, 66
1. Definition
Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting
from the least significant digit (LSD) to the most significant digit (MSD). It uses a stable
sorting technique such as counting sort at each digit level.
2. Given Data
170, 45, 75, 90, 802, 24, 2, 66
3. Concept of Radix Sort
• Numbers are grouped based on digits (units, tens, hundreds).
• Sorting is performed from rightmost digit to leftmost digit.
• At each step, numbers are arranged in ascending order based on the current digit.
4. Steps of Radix Sort
Step 1: Sort according to Unit Place (1’s digit)
Number Unit Digit
170 0
45 5
75 5
90 0
802 2
24 4
2 2
66 6
After sorting by unit digit:
170, 90, 802, 2, 24, 45, 75, 66
Page 7 of 15
Step 2: Sort according to Tens Place (10’s digit)
Number Tens Digit
170 7
90 9
802 0
2 0
24 2
45 4
75 7
66 6
After sorting by tens digit:
802, 2, 24, 45, 66, 170, 75, 90
Step 3: Sort according to Hundreds Place (100’s digit)
Number Hundreds Digit
802 8
2 0
24 0
45 0
66 0
170 1
75 0
90 0
After sorting by hundreds digit:
2, 24, 45, 66, 75, 90, 170, 802
5. Final Sorted Output
2, 24, 45, 66, 75, 90, 170, 802
Page 8 of 15
6. Diagram
Step 1 (Unit Place Buckets):
0 → 170, 90
2 → 802, 2
4 → 24
5 → 45, 75
6 → 66
Step 2 (Tens Place Buckets):
0 → 802, 2
2 → 24
4 → 45
6 → 66
7 → 170, 75
9 → 90
7. Advantages of Radix Sort
• Faster than comparison-based sorting for large datasets
• Stable sorting algorithm
• Works efficiently when the range of digits is small
8. Disadvantages of Radix Sort
• Requires extra memory
• Not suitable for floating-point numbers directly
• Complexity depends on number of digits
Conclusion
Radix Sort is an efficient sorting technique for integers that processes numbers digit by digit.
It provides a stable and fast method for sorting large datasets when the number of digits is
limited.
Page 9 of 15
Q.3 Convert the following Infix expression into Prefix and Postfix
Given Expression:
(𝐴𝑋 ∗ (𝐵𝑋 ∗ (((𝐶𝑌 + 𝐴𝑌) + 𝐵𝑌) ∗ 𝐶𝑋)))
1. Definitions
• Infix Expression: Operator is written between operands.
• Prefix Expression: Operator is written before operands.
• Postfix Expression: Operator is written after operands.
2. Conversion Rules
1. Use a stack to manage operators
2. Follow operator precedence: *, / > +, -
3. Evaluate expressions inside parentheses first
3. Conversion Steps
(𝐶𝑌 + 𝐴𝑌) = 𝐶𝑌𝐴𝑌 +
(𝐶𝑌𝐴𝑌 + +𝐵𝑌) = 𝐶𝑌𝐴𝑌 + 𝐵𝑌 +
((𝐶𝑌𝐴𝑌 + 𝐵𝑌+) ∗ 𝐶𝑋) = 𝐶𝑌𝐴𝑌 + 𝐵𝑌 + 𝐶𝑋 ∗
(𝐵𝑋 ∗ (𝐶𝑌𝐴𝑌 + 𝐵𝑌 + 𝐶𝑋 ∗)) = 𝐵𝑋𝐶𝑌𝐴𝑌 + 𝐵𝑌 + 𝐶𝑋 ∗∗
(𝐴𝑋 ∗ (𝐵𝑋𝐶𝑌𝐴𝑌 + 𝐵𝑌 + 𝐶𝑋 ∗∗)) = 𝐴𝑋𝐵𝑋𝐶𝑌𝐴𝑌 + 𝐵𝑌 + 𝐶𝑋 ∗∗∗
4. Postfix Expression
𝐴𝑋𝐵𝑋𝐶𝑌𝐴𝑌 + 𝐵𝑌 + 𝐶𝑋 ∗∗∗
5. Prefix Expression
∗ 𝐴𝑋 ∗ 𝐵𝑋 ∗ + + 𝐶𝑌𝐴𝑌𝐵𝑌𝐶𝑋
6. Expression Tree
Draw the expression tree with:
• Root node: *
• Left child: AX
• Right subtree representing BX * (((CY+AY)+BY) * CX)
• Internal nodes as operators and leaf nodes as operands
Conclusion
Prefix and postfix notations provide efficient ways to evaluate expressions without using
parentheses.
Page 10 of 15
Q.4 Construct an AVL Tree by inserting the following elements: 21, 26, 30, 9, 4, 14, 28
1. Definition
An AVL Tree is a self-balancing Binary Search Tree in which the difference between the
heights of left and right subtrees (Balance Factor) of any node is at most 1.
Balance Factor = Height(Left Subtree) − Height(Right Subtree)
Balanced if the value is −1, 0, or +1.
2. Rotations in AVL Tree
To maintain balance, the following rotations are used:
• LL Rotation (Left-Left)
• RR Rotation (Right-Right)
• LR Rotation (Left-Right)
• RL Rotation (Right-Left)
3. Insertion Steps
Insert elements one by one and rebalance when required.
Step 1: Insert 21
21
Step 2: Insert 26
21
\
26
Step 3: Insert 30
Unbalanced at node 21 → RR Rotation
26
/ \
21 30
Step 4: Insert 9
26
/ \
21 30
/
9
Page 11 of 15
Step 5: Insert 4
Unbalanced at node 21 → LL Rotation
26
/ \
9 30
/\
4 21
Step 6: Insert 14
Unbalanced at node 26 → LR Rotation
21
/ \
9 26
/\ \
4 14 30
Step 7: Insert 28
Unbalanced at node 26 → RL Rotation
21
/ \
9 28
/\ /\
4 14 26 30
4. Final AVL Tree
21
/ \
9 28
/\ /\
4 14 26 30
5. Conclusion
An AVL Tree maintains balance after each insertion using rotations, ensuring that operations
like search, insertion, and deletion are efficient with time complexity O(log n).
Page 12 of 15
Q.5 Apply Prim’s Algorithm to find the Minimum Spanning Tree
1. Definition
Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
connected, weighted, undirected graph. It selects edges with the minimum weight such that
all vertices are connected without forming any cycle.
2. Algorithm Steps
1. Start with any one vertex
2. Select the edge with the minimum weight connected to the current tree
3. Add the selected edge and vertex to the tree
4. Repeat until all vertices are included
5. Ensure no cycles are formed
Step-by-Step MST Construction (Prim’s Algorithm)
Step 1: Start from A
• Choose minimum edge → A–B (2)
Step 2: From A, B
• Possible edges: B–C (1), B–D (4), A–C (3)
• Choose → B–C (1)
Step 3: From A, B, C
• Possible edges: C–D (2), B–D (4), A–C (3), C–E (6)
• Choose → C–D (2)
Page 13 of 15
Step 4: From A, B, C, D
• Possible edges: D–E (2), B–D (4), C–E (6)
• Choose → D–E (2)
Step 5: All vertices included
Minimum Spanning Tree is complete.
Final Selected Edges
• A–B = 2
• B–C = 1
• C–D = 2
• D–E = 2
Total Cost
Total Cost = 2 + 1 + 2 + 2 = 7
3. Working Procedure
• Maintain a set of selected vertices
• At each step, choose the smallest edge connecting a selected vertex to an unselected
vertex
• Continue until all vertices are covered
4. Example (General Explanation)
Let the graph have vertices and weighted edges. Starting from any vertex:
• Step 1: Select the smallest edge connected to the starting vertex
• Step 2: Add the next minimum edge that connects a new vertex
• Step 3: Continue selecting minimum edges without forming cycles
• Step 4: Stop when all vertices are connected
6. Advantages
• Simple and efficient for dense graphs
• Guarantees minimum total weight
• Easy to implement
Page 14 of 15
7. Disadvantages
• Not suitable for disconnected graphs
• Requires a weighted graph
Conclusion
Prim’s Algorithm is an effective method to construct a Minimum Spanning Tree by selecting
the minimum weight edges step by step, ensuring all vertices are connected with minimum
cost.
Page 15 of 15