Advanced Data Structures and

Algorithms (24CSH-232)
Compiled by : Subhayu

ify
te
No
Advanced Data Structures and Algorithms (24CSH-232)

Course Content

Unit-1 : Basic of Algorithms, Trees

Ch 1 : Basic of Algorithms - Analysis Framework, Worst, Average, and best-case

analysis, Analysis. Asymptotic notations. O notation, Omega notation, Theta notation.
Algorithm performance analysis. Time and space complexity. Analysis of iterative and
recursive algorithms, Recurrence Equations and their Solution: Substitution method &
master theorem recursion tree method.

Ch 2 : Trees - Basic terminology, Binary Trees, Representation of Binary Trees in Mem-

ory, traversing Binary Trees, Traversal Algorithms using stacks, Header Nodes, Threads,
Binary Search Trees, Searching, Inserting & Deleting in Binary Search Trees, AVL Search

ify
trees, B Trees, Heap & Heap Sort, Segment tree & tries, Red Black Tree, Operations Per-
formed on Red Black Tree, 2-3 Tree, B+-Tree.
te
Unit-2 : Graphs, Hashing & File Organization, Prims and Kruskal Algorithm

Ch 3 : Graphs - Graph Theory terminology, sequential representation of graphs (ad-

jacency matrix, Path Matrix), traversing a graph, Operations on Graph, Shortest Path
No

algorithms: Dijkstra’s Algorithm, Bellman-Ford Algorithm, Spanning Trees & some top-
ics of Advanced graph.

Ch 4 : Hashing and File organization - Hash Table, Hash Functions, Collision Reso-
lution Strategies, Hash Table Implementation. Concepts of files, Organization of records
into Blocks, File organization: Sequential, Relative, Index Sequential, Inverted File.

Unit-3 : Divide and Conquer, Greedy Methods

Ch 5 : Divide and Conquer: Understanding of divide and conquer approach. Al-

gorithms for FindMin and Max, Sorting: Quick Sort, 2 Way Merge Sort, heap sort.
Searching: Linear Search and Binary Search, Strassen’s matrix multiplication and con-
vex hull. Decrease and Conquer Approach: Topological Sort.

Ch 6 : Greedy Methods- Understanding Greedy approach, Greedy Algorithms for

knapsack fractional problem, Minimum spanning tree, Prims and Kruskal Algorithm.
Chapter 1

Basics of Algorithms

1.1 Introduction

ify
An algorithm is a finite sequence of well-defined instructions to solve a specific problem.
Algorithms form the foundation of computer science and are evaluated based on their
efficiency, correctness, and clarity.
Key Points:
te
• Every algorithm must terminate after a finite number of steps.

• Each step should be clear and unambiguous.

• Should solve the problem correctly for all valid inputs.

No

1.2 Analysis Framework

Algorithm analysis determines the efficiency of an algorithm in terms of:

• Time Complexity: Amount of time taken to execute the algorithm.

• Space Complexity: Amount of memory required by the algorithm.

1.2.1 Case Analysis

• Best Case: Minimum time required for algorithm to complete (ideal scenario).

• Worst Case: Maximum time taken for algorithm to complete (pessimistic sce-
nario).

• Average Case: Expected time over all inputs.

Example: Linear Search of an element in an array of size n.

2
Advanced Data Structures and Algorithms (24CSH-232)

• Best Case: Element is at the first position ⇒ O(1)

• Worst Case: Element is at last position or absent ⇒ O(n)

• Average Case: Element is uniformly likely to be at any position ⇒ O(n/2) ≈ O(n)

1.3 Asymptotic Notations

Used to describe the growth of an algorithm’s time/space complexity as input size grows.

• Big O Notation (O): Upper bound on runtime. Guarantees the algorithm will
not exceed this time.

T (n) = O(f (n)) ⇐⇒ ∃c > 0, n0 > 0 : T (n) ≤ c · f (n) for all n ≥ n0

taken.
ify
• Omega Notation (Ω): Lower bound on runtime. Guarantees minimum time

T (n) = Ω(f (n)) ⇐⇒ ∃c > 0, n0 > 0 : T (n) ≥ c · f (n) for all n ≥ n0

te
• Theta Notation (Θ): Tight bound. Runtime grows exactly as f (n).

T (n) = Θ(f (n)) ⇐⇒ T (n) = O(f (n)) and T (n) = Ω(f (n))
No

Example: If T (n) = 3n2 + 5n + 10, then T (n) = O(n2 ), T (n) = Ω(n2 ), and T (n) =
Θ(n2 ).

1.4 Algorithm Performance Analysis

Performance analysis focuses on:

• Counting number of basic operations (comparisons, assignments, arithmetic opera-

tions)

• Considering time for memory access

• Evaluating iterative and recursive algorithms

1.4.1 Iterative Algorithm Analysis Example

Problem: Sum of first n integers using loop
Advanced Data Structures and Algorithms (24CSH-232)

sum = 0
for i = 1 to n:
sum = sum + i

Analysis:

• One addition per iteration, total n additions

• Time Complexity T (n) = O(n)

1.4.2 Recursive Algorithm Analysis Example

Problem: Factorial of n

function fact(n):
if n == 0:

else: ify
return 1

return n * fact(n-1)

Analysis:
te
• Each call performs one multiplication and one recursive call

• n recursive calls ⇒ T (n) = O(n)

No

• Space Complexity = O(n) due to call stack

1.5 Recurrence Equations and Their Solution

Recursion leads to recurrence relations to describe runtime.

1.5.1 Substitution Method

Assume a solution and prove by induction.
Example: T (n) = 2T (n/2) + n (Merge Sort)

Assume T (n) ≤ cn log n, prove by substitution.

1.5.2 Recursion Tree Method

Draw a tree representing recursive calls; sum the costs level-wise.
Example: T (n) = 2T (n/2) + n

• Level 0: n
Advanced Data Structures and Algorithms (24CSH-232)

• Level 1: 2 subproblems, each n/2 ⇒ 2 ∗ (n/2) = n

• Level 2: 4 subproblems, each n/4 ⇒ 4 ∗ (n/4) = n

• Total cost ≈ n log n

1.5.3 Master Theorem

For recurrences of form:
T (n) = aT (n/b) + f (n)

• Case 1: f (n) = O(nlogb a−ϵ ) ⇒ T (n) = Θ(nlogb a )

• Case 2: f (n) = Θ(nlogb a ) ⇒ T (n) = Θ(nlogb a log n)

• Case 3: f (n) = Ω(nlogb a+ϵ ) ⇒ T (n) = Θ(f (n))

1.6 ify
Solved Examples
Example 1: Iterative Sum of n numbers Problem: Find sum of first 100 integers.
te
Solution:

sum = 0
for i = 1 to 100:
No

sum = sum + i
Output: 5050

Example 2: Recurrence Relation Problem: Solve T (n) = 2T (n/2) + n using

Master Theorem. Solution:
a = 2, b = 2, f (n) = n

nlog2 2 = n

f (n) = Θ(nlogb a ) ⇒ T (n) = Θ(n log n)

Example 3: Factorial using recursion

fact(5)
= 5 * fact(4)
= 5 * 4 * fact(3)
= 5 * 4 * 3 * fact(2)
= 5 * 4 * 3 * 2 * fact(1)
= 5 * 4 * 3 * 2 * 1 = 120
Advanced Data Structures and Algorithms (24CSH-232)

1.7 Summary
• Algorithms are evaluated based on correctness, efficiency, and clarity.

• Asymptotic notations (O, Ω, Θ) describe growth trends.

• Iterative and recursive algorithms can be analyzed using operation counts, recur-
rence relations, and the Master Theorem.

• Recursion tree and substitution methods help visualize and solve recurrences.

ify
te
No
Chapter 2

Trees

2.1 Introduction

ify
A tree is a non-linear hierarchical data structure consisting of nodes, with one node
designated as the root, and zero or more subtrees of child nodes, connected via edges.
Trees are widely used in computer science for representing hierarchical data, such as file
systems, organizational charts, and expression parsing.
te
2.1.1 Basic Terminology
• Node: Basic unit of a tree containing data.
No

• Root: Topmost node of the tree.

• Parent and Child: If node A is connected to node B, then A is parent of B, and

B is child of A.

• Leaf Node: Node with no children.

• Edge: Connection between two nodes.

• Height of Tree: Length of longest path from root to a leaf.

• Depth of Node: Number of edges from root to the node.

• Degree of Node: Number of children a node has.

2.2 Binary Trees

A binary tree is a tree in which each node has at most two children: left and right.

7
Advanced Data Structures and Algorithms (24CSH-232)

2.2.1 Representation of Binary Trees in Memory

Binary trees can be represented using:

• Linked Representation: Each node has a data field and two pointers (left and
right child).

• Array Representation: For a complete binary tree, if a node is at index i, then:

Left child index = 2i, Right child index = 2i + 1

2.2.2 Traversing Binary Trees

Tree traversal refers to visiting all nodes in a specific order.

ify
• Inorder (LNR): Left, Node, Right

• Preorder (NLR): Node, Left, Right

• Postorder (LRN): Left, Right, Node

te
Traversal using Stacks

Iterative traversal can use an explicit stack instead of recursion for managing nodes.
Example: Iterative Inorder Traversal
No

push root to stack

while stack not empty or current != NULL:
while current != NULL:
push current
current = current->left
current = pop from stack
visit(current)
current = current->right

2.3 Advanced Binary Tree Concepts

2.3.1 Header Nodes and Threads
• Header Node: A dummy node used to simplify traversal.

• Threaded Binary Tree: NULL pointers in nodes are replaced by pointers to the
inorder predecessor or successor for efficient traversal.
Advanced Data Structures and Algorithms (24CSH-232)

2.3.2 Binary Search Tree (BST)

A BST is a binary tree where for each node:

Left subtree nodes < Node data < Right subtree nodes

Operations on BST

• Searching: Start from root, traverse left/right based on comparison.

• Insertion: Add a new node maintaining BST property.

• Deletion: Remove node maintaining BST property. Three cases: leaf node, node
with one child, node with two children.

2.3.3

ify
AVL Trees
An AVL tree is a self-balancing BST where the height difference between left and right
subtrees of any node is at most 1. Rotations (single and double) are used to maintain
balance after insertions and deletions.
te
2.3.4 B Trees
A B-tree is a self-balancing search tree that maintains sorted data and allows search,
sequential access, insertion, and deletion in logarithmic time. Widely used in databases
No

and filesystems.

2.3.5 Heap and Heap Sort

• Heap: Complete binary tree with max-heap (parent ≥ children) or min-heap
(parent ≤ children).

• Heap Sort: Build max-heap and repeatedly extract maximum to sort array in
O(n log n) time.

2.3.6 Segment Tree

Used for answering range queries efficiently, e.g., sum or minimum over a segment of an
array in O(log n) time.

2.3.7 Tries
A trie is a tree used for storing strings where each node represents a character. Efficient
for prefix search.
Advanced Data Structures and Algorithms (24CSH-232)

2.3.8 Red-Black Tree

A self-balancing BST with nodes colored red or black, maintaining:

• Root is black

• Red nodes cannot have red children

• Every path from root to leaf has same number of black nodes

2.3.9 2-3 Trees and B+-Trees

• 2-3 Tree: Each node has 2 or 3 children; ensures balance.

• B+-Tree: A B-tree variant where all values are stored at leaf nodes; internal nodes
only store keys for navigation.

2.4 ify
Solved Examples
Example 1: Inorder Traversal of BST
te
BST:
10
/ \
No

5 15
Inorder Traversal: 5 10 15

Example 2: Inserting in BST

Insert 12 into BST:

10
/ \
5 15

12 < 15 => goes to left of 15

BST after insertion:
10
/ \
5 15
/
12

Example 3: Max-Heap Construction

Advanced Data Structures and Algorithms (24CSH-232)

Array: [4, 10, 3, 5, 1]

Max-Heap:
10
/ \
5 3
/ \
4 1

2.5 Summary
• Trees are hierarchical structures used to store data efficiently.

• Binary Trees, BSTs, AVL Trees, Heaps, and B-Trees have different properties and

ify
applications.

• Traversals can be done recursively or iteratively using stacks.

• Advanced trees like Red-Black, Segment Trees, Tries, and B+-Trees are crucial for
efficient searching, insertion, and deletion.
te
No
Advanced Data Structures and Algorithms (24CSH-232)

Unit-1: Basic of Algorithms and Trees - Question

Bank
Q1. Define an algorithm. List the key characteristics.
Answer:
An algorithm is a step-by-step procedure to solve a specific problem.
Characteristics:

• Finiteness: Algorithm must terminate after a finite number of steps.

• Definiteness: Each step must be precisely defined.

• Input: Accepts zero or more inputs.

Q2.
ify
• Output: Produces at least one output.

• Effectiveness: Each operation must be basic enough to perform manually.

Explain worst-case, best-case, and average-case analysis

te
with examples.
Answer:
No

• Best-case: Minimum steps taken (e.g., element found at first position in linear
search).

• Worst-case: Maximum steps taken (e.g., element not present in linear search).

• Average-case: Expected number of steps (e.g., element present at random posi-

tions).

Example (Linear Search in array [5,2,7,1], search 1):

• Best-case: 1 step

• Worst-case: 4 steps

• Average-case: (1 + 2 + 3 + 4)/4 = 2.5 steps

Advanced Data Structures and Algorithms (24CSH-232)

Q3. Explain asymptotic notations with examples.

Answer:

• Big-O notation (O): Upper bound of running time. Example: f (n) = 3n+2 =⇒
O(n)

• Omega notation (Ω): Lower bound of running time. Example: f (n) = 3n+2 =⇒
Ω(n)

• Theta notation (Θ): Tight bound. Example: f (n) = 3n + 2 =⇒ Θ(n)

Q4. Find the time complexity of the following code:

ify
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)

Answer:
printf("%d", i*j);
te
- Outer loop runs n times - Inner loop runs n times for each outer iteration - Total
operations = n × n = n2 - Time Complexity: O(n2 )

Q5. Solve the recurrence T (n) = 2T (n/2) + n using Master Theo-

No

rem.
Answer:
- T (n) = aT (n/b) + f (n), here a = 2, b = 2, f (n) = n - Compare f (n) = n with
nlogb a = nlog2 2 = n - Case 2 of Master Theorem: T (n) = Θ(n log n)

2.5.1 Q6. Define a tree and list basic terminology.

Answer:
A tree is a hierarchical non-linear data structure consisting of nodes connected by edges.
Terminology: Node, Root, Parent, Child, Leaf, Height, Depth, Degree, Edge.

Q7. Represent the following Binary Tree in memory (linked

representation):
10
/ \
5 15
Advanced Data Structures and Algorithms (24CSH-232)

Answer:

struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node* root = (struct Node*)malloc(sizeof(struct Node));
root->data = 10;
root->left = (struct Node*)malloc(sizeof(struct Node));
root->left->data = 5;
root->right = (struct Node*)malloc(sizeof(struct Node));
root->right->data = 15;

10
/ \
ify
Q8. Perform inorder traversal of the BST:
te
5 15

Answer:
Inorder (Left, Node, Right): 5 10 15
No

Q9. Insert 12 into the BST:

10
/ \
5 15

Answer:
- Compare 12 with 10: go right - Compare 12 with 15: go left - Insert as left child of 15
BST after insertion:

10
/ \
5 15
/
12
Advanced Data Structures and Algorithms (24CSH-232)

Q10. Explain AVL tree and rotations with example.

Answer:
AVL tree: self-balancing BST; height difference of left and right subtree ≤ 1. - Left
Rotation: when right-heavy - Right Rotation: when left-heavy
Example: Inserting 30,20,10 causes left-left imbalance → Right rotation on root

Q11. Construct a max-heap from array [4, 10, 3, 5, 1].

Answer:
Heap after insertion (level order):

10
/ \
5 3

4
/ \
1 ify
Q12. Explain B-Tree and B+-Tree differences.
te
Answer:

• B-Tree: Keys stored in all nodes, maintains sorted order.

No

• B+-Tree: Only leaf nodes store data, internal nodes store keys for navigation.

• Both allow multiple children, self-balancing, used in databases.

Q13. What is a threaded binary tree?

Answer:
A tree where NULL pointers are replaced by pointers to the inorder predecessor or suc-
cessor, allowing efficient traversal without stack or recursion.

Q14. Write recursive function to count nodes in a binary tree.

Answer:

int countNodes(struct Node* root) {

if(root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
Advanced Data Structures and Algorithms (24CSH-232)

Q15. Difference between iterative and recursive tree traversal.

Answer:

• Recursive: Simple, uses function call stack.

• Iterative: Uses explicit stack; avoids function call overhead.

• Both visit all nodes, produce same output.

ify
te
No
Chapter 3

Graphs

3.1 Graph Theory Terminology

them.
Key Terms:
ify
A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting

• Vertex (Node): A fundamental unit or point in a graph.

te
• Edge: Connection between two vertices; can be directed or undirected.

• Degree: Number of edges incident to a vertex.

No

• Path: A sequence of vertices connected by edges.

• Cycle: A path that starts and ends at the same vertex.

• Weighted Graph: Each edge carries a weight (cost, distance, etc.).

• Spanning Tree: A subgraph connecting all vertices without cycles.

3.2 Sequential Representation of Graphs

3.2.1 Adjacency Matrix
A 2D array A[n][n], where n is the number of vertices:

1, if edge exists between vertex i and j
A[i][j] =
0, otherwise

Example: Graph with vertices V = {0, 1, 2} and edges E = {(0, 1), (1, 2)}

17
Advanced Data Structures and Algorithms (24CSH-232)

 
0 1 0
A = 1 0 1
 

0 1 0

3.2.2 Adjacency List

Each vertex stores a list of its adjacent vertices. Efficient for sparse graphs.
Example:

0 -> 1
1 -> 0,2
2 -> 1

3.2.3 Path Matrix

ify
The path matrix indicates the number of paths between vertices. Can be computed
from adjacency matrix powers.
te
3.3 Graph Traversal
3.3.1 Breadth-First Search (BFS)
No

- Visits vertices level by level using a queue. - Starts from a chosen source vertex.
Example BFS from vertex 0: 0 → 1 → 2

3.3.2 Depth-First Search (DFS)

- Explores deepest vertices first using recursion or stack.
Example DFS from vertex 0: 0 → 1 → 2

3.4 Operations on Graphs

• Insert/Delete Vertex

• Insert/Delete Edge

• Find degree of a vertex

• Check connectivity
Advanced Data Structures and Algorithms (24CSH-232)

3.5 Shortest Path Algorithms

3.5.1 Dijkstra’s Algorithm
- Finds the shortest path from a single source in a weighted graph with non-negative
weights. - Uses a priority queue or array to track shortest distances.
Example: Graph with vertices 0,1,2 and edges with weights: 0→1 (4), 0→2 (2), 1→2
(5)
Step-by-step:

1. Initialize distance: dist[0]=0, dist[1]=∞ dist[2]=∞

2. Pick vertex with minimum distance → 0

3. Update neighbors: dist[1]=4, dist[2]=2

ify
4. Pick next minimum → 2, update neighbors: dist[1] remains 4

5. Pick next minimum → 1, done

Shortest distances: 0→0:0, 0→1:4, 0→2:2

te
3.5.2 Bellman-Ford Algorithm
- Computes shortest paths from a single source, allows negative weights. - Relaxes all
No

edges |V | − 1 times. - Detects negative cycles.

3.6 Spanning Trees

- A spanning tree connects all vertices without cycles. - Minimum Spanning Tree
(MST) has minimum total edge weight.

3.6.1 Prim’s Algorithm

• Starts with a single vertex.

• Repeatedly adds the minimum weight edge connecting tree to remaining vertices.

3.6.2 Kruskal’s Algorithm

• Sort edges by weight

• Add edges to MST without forming cycles (using Union-Find)

Advanced Data Structures and Algorithms (24CSH-232)

3.7 Advanced Graph Topics (Brief )

• Directed Acyclic Graphs (DAG)

• Topological Sorting

• Strongly Connected Components (SCC)

• Graph coloring

3.8 Solved Example

Problem: Find MST using Prim’s Algorithm for graph:
Vertices: 0,1,2 Edges: 0→1 (4), 0→2 (2), 1→2 (5)
Solution:

ify
1. Start with vertex 0. MST=0

2. Choose min edge from 0: 0→2 (2) → Add 2

3. Next min edge: 0→1 (4) → Add 1

te
MST edges: 0→2, 0→1 Total weight: 2 + 4 = 6
No
Chapter 4

Hashing and File Organization

4.1 Hashing
4.1.1
ify
Hash Table
A hash table is a data structure that stores data in an array format using a hash
function to compute an index for each key. It allows fast insertion, deletion, and
search operations, ideally in O(1) time.
te
4.1.2 Hash Functions
A hash function maps a key to an index in the hash table.
No

Common hash functions:

• Division method: h(k) = k mod m, where m is table size.

• Multiplication method: h(k) = ⌊m · (k · A mod 1)⌋, 0 < A < 1.

• Folding method: Divide key into parts, sum or combine them.

4.1.3 Collision and Resolution Strategies

A collision occurs when two keys map to the same index.
Resolution Strategies:

• Chaining: Store multiple keys at the same index using linked list.

• Open addressing: Find next available slot:

– Linear probing
– Quadratic probing
– Double hashing

21
Advanced Data Structures and Algorithms (24CSH-232)

4.1.4 Hash Table Implementation Example

// Example: Hash table using division method and chaining
int hash(int key) {
return key % TABLE_SIZE;
}

4.2 File Organization

4.2.1 Concept of Files
A file is a collection of related records stored on secondary storage (like disk). Files are
used to store persistent data.

4.2.2
ify
Organization of Records into Blocks
• Records are grouped into blocks for efficient disk access.

• Each block contains one or more records.

te
• Accessing one block is faster than accessing multiple single records.

4.2.3 File Organization Methods

No

Sequential File Organization

• Records are stored one after another in sorted order.

• Efficient for reading all records sequentially.

• Search requires linear or binary search (if sorted).

Relative File Organization

• Each record has a unique relative record number (RRN).

• Direct access possible using RRN.

Index Sequential File Organization

• Maintains an index for fast access along with sequential storage.

• Combines advantages of sequential and direct access.

Advanced Data Structures and Algorithms (24CSH-232)

Inverted File Organization

• Creates an inverted index mapping attributes to record locations.

• Efficient for multi-key searches.

4.3 Solved Example: Hashing with Chaining

Problem: Insert keys 12, 25, 36, 20 into a hash table of size 10 using division method
and chaining.
Solution:

• h(12) = 12 mod 10 = 2 → insert 12 at index 2

• h(25) = 25 mod 10 = 5 → insert 25 at index 5

ify
• h(36) = 36 mod 10 = 6 → insert 36 at index 6

• h(20) = 20 mod 10 = 0 → insert 20 at index 0

Hash Table:
te
Index 0: 20
Index 1: -
Index 2: 12
No

Index 3: -
Index 4: -
Index 5: 25
Index 6: 36
Index 7: -
Index 8: -
Index 9: -
Advanced Data Structures and Algorithms (24CSH-232)

Unit-2 : Question Bank

1. Define a graph. Explain the difference between directed and undirected
graphs.
Answer: A graph G = (V, E) consists of a set of vertices V and a set of edges E.

• Directed graph (digraph): edges have a direction (from u to v).

• Undirected graph: edges have no direction; (u, v) is same as (v, u).

2. Represent the following graph using an adjacency matrix: Vertices V =

{0, 1, 2}, edges E = {(0, 1), (1, 2), (0, 2)}
Answer:  
0 1 1
A = 1 0 1
 

ify 1 1 0

3. Perform BFS starting from vertex 0 for the graph: V = {0, 1, 2, 3}, edges:
(0, 1), (0, 2), (1, 2), (2, 3)
Answer:
te
• Start at 0: Visit 0
• Queue neighbors: 1, 2 → Visit 1 → Enqueue 2 (already in queue)
No

• Visit 2 → Enqueue 3
• Visit 3

BFS order: 0 → 1 → 2 → 3

4. Perform DFS starting from vertex 0 for the same graph.

Answer:

• Start at 0 → Visit 0
• Go to neighbor 1 → Visit 1
• Neighbor 2 → Visit 2
• Neighbor 3 → Visit 3

DFS order: 0 → 1 → 2 → 3

5. Explain Dijkstra’s algorithm and find shortest path from 0 to all vertices
for: Vertices: 0,1,2 Edges with weights: 0→1 (4), 0→2 (2), 1→2 (5)
Answer:
Advanced Data Structures and Algorithms (24CSH-232)

(a) Initialize distances: dist[0]=0, dist[1]=∞, dist[2]=∞

(b) Pick vertex with min distance → 0
(c) Update neighbors: dist[1]=4, dist[2]=2
(d) Pick next min → 2, check neighbor 1: dist[1] remains 4
(e) Pick next min → 1, done

Shortest distances: 0→0:0, 0→1:4, 0→2:2

6. Use Bellman-Ford Algorithm to find shortest paths from 0: Vertices: 0,1,2

Edges: 0→1 (4), 0→2 (5), 1→2 (-2)
Answer:

(a) Initialize distances: dist[0]=0, dist[1]=∞, dist[2]=∞

ify
(b) Relax edges —V—-1 = 2 times
• First iteration: 0→1: dist[1]=4, 0→2: dist[2]=5, 1→2: dist[2]=2 (4 + -2)
• Second iteration: no changes
te
Shortest distances: 0→0:0, 0→1:4, 0→2:2

7. Explain Spanning Tree and draw MST using Prim’s algorithm for: Ver-
tices: 0,1,2 Edges with weights: 0→1 (4), 0→2 (2), 1→2 (5)
No

Answer:

(a) Start with vertex 0 → MST=0

(b) Choose min edge from MST → 0→2 (2) → Add 2
(c) Next min edge → 0→1 (4) → Add 1

MST edges: 0→2, 0→1, Total weight = 6

8. Define hash table and give an example of a simple hash function.

Answer:

• Hash Table: Stores key-value pairs for fast access using hash functions.
• Example: Division method: h(k) = k mod 10
• Insert key 23 → 23 mod 10 = 3, store at index 3

9. Explain collision and two resolution strategies.

Answer:

• Collision: When two keys map to same index.

Advanced Data Structures and Algorithms (24CSH-232)

• Resolution Strategies: 1. Chaining: Linked list at each index. 2. Open

addressing: Linear probing, Quadratic probing, Double hashing.

10. Insert keys 12, 25, 36, 20 into a hash table of size 10 using chaining.
Answer:

Index 0: 20
Index 1: -
Index 2: 12
Index 3: -
Index 4: -
Index 5: 25
Index 6: 36
Index 7: -
Index
Index ify
8:
9:
-
-

11. Define file and explain the organization of records into blocks.
Answer:
te
• A file is a collection of related records stored on disk.
• Blocks: Disk access unit containing one or more records. Faster access than
single record reads.
No

12. Explain sequential and relative file organization.

Answer:

• Sequential: Records stored in order; easy for sequential reading.

• Relative: Each record has a relative record number (RRN); allows direct
access using RRN.

13. Explain Index Sequential and Inverted file organization.

Answer:

• Index Sequential: Maintains index for fast access while storing records se-
quentially.
• Inverted File: Stores mapping from attributes to record locations; useful for
multi-key searches.

14. Illustrate creating a hash table for student IDs 101, 102, 203 using divi-
sion method with table size 10.
Answer:
Advanced Data Structures and Algorithms (24CSH-232)

• 101 mod 10 = 1, store at index 1

• 102 mod 10 = 2, store at index 2
• 203 mod 10 = 3, store at index 3

15. Explain adjacency matrix and adjacency list with example for a graph:
Vertices 0,1,2; edges 0→1,1→2
Answer: Adjacency Matrix:
 
0 1 0
A = 0 0 1
 

0 0 0

Adjacency List:

0 -> 1
1 -> 2
2 -> -
ify
te
No
Chapter 5

Divide and Conquer

5.1 Introduction

ify
Divide and Conquer is a fundamental algorithmic paradigm where a problem is broken
down into smaller subproblems, solved independently, and their solutions combined to
solve the original problem.

• Steps:
te
1. Divide: Split the problem into smaller subproblems.
2. Conquer: Solve the subproblems recursively.
No

3. Combine: Merge the solutions of subproblems to get the final solution.

• Applications: Sorting (Quick Sort, Merge Sort), Searching (Binary Search), Ma-
trix Multiplication (Strassen), finding Min/Max.

5.2 Finding Minimum and Maximum using Divide

and Conquer
• Instead of scanning the array sequentially, divide the array into two halves, find
Min and Max in each half recursively, and then combine.

Algorithm:

1. If array has one element, return it as both min and max.

2. If array has two elements, compare and assign min and max.

3. Else, divide array into two halves.

4. Recursively find min and max in both halves.

28
Advanced Data Structures and Algorithms (24CSH-232)

5. Combine results:
Min = min(min left, min right)

Max = max(max left, max right)

Example: Array = [5, 2, 9, 1, 6]

• Divide: [5,2,9] and [1,6]

• Recursive Min/Max: - Left: Min=2, Max=9 - Right: Min=1, Max=6

• Combine: Min=1, Max=9

5.3 Sorting Algorithms Using Divide and Conquer

5.3.1
ify
Quick Sort
• Concept: Choose a pivot, partition array into elements less than pivot (left) and
greater than pivot (right), and recursively sort subarrays.

• Steps:
te
1. Pick a pivot element (e.g., last element).
2. Partition array: elements ≤ pivot on left, > pivot on right.
No

3. Recursively sort left and right subarrays.

Example: Array = [8, 3, 1, 7]

1. Pivot=7, partition → [3,1 — 7 — 8]

2. Left [3,1] → pivot=1 → [1 — 3]

3. Right [8] → sorted

Sorted Array: [1, 3, 7, 8]

5.3.2 Merge Sort (2-Way Merge Sort)

• Concept: Divide array into two halves, recursively sort, then merge sorted halves.

Steps:

1. Divide array into two halves.

2. Recursively sort left and right halves.

Advanced Data Structures and Algorithms (24CSH-232)

3. Merge two sorted halves.

Example: Array = [6, 2, 8, 5]
1. Divide → [6,2] & [8,5]

2. Sort left → [2,6], right → [5,8]

3. Merge → [2,5,6,8]

5.3.3 Heap Sort

• Build a max heap from array.

• Repeatedly remove the max element (root), place it at the end, and heapify re-
maining elements.

ify
• Array becomes sorted in ascending order.

Example: Array = [4,10,3,5]

1. Build max heap → [10,5,3,4]

2. Remove max 10 → heapify → [5,4,3]

te
3. Remove max 5 → heapify → [4,3]

4. Sorted array → [3,4,5,10]

No

5.4 Searching Algorithms Using Divide and Conquer

5.4.1 Binary Search
• Works on sorted array.

• Repeatedly divide search interval in half until target is found.

Steps:
1. Find middle element.

2. If middle = target → found.

3. If middle < target → search right half.

4. If middle > target → search left half.

5. Repeat recursively.
Example: Array = [1,3,5,7,9], Search=5
1. Mid=5 → Found
Advanced Data Structures and Algorithms (24CSH-232)

5.5 Strassen’s Matrix Multiplication

• Faster than standard O(n3 ) multiplication.

• Divides n × n matrices into n/2 × n/2 submatrices and recursively multiplies them
using 7 multiplications instead of 8.

Step: For matrices A and B, divide into 4 blocks each → compute 7 products recur-
sively → combine.

5.6 Convex Hull (Divide and Conquer Approach)

• Used in computational geometry to find the minimal convex polygon enclosing a
set of points.

• Steps:
ify
1. Divide points into left and right halves by x-coordinate.
2. Recursively find convex hull for each half.
te
3. Merge two convex hulls.

5.7 Decrease and Conquer Approach

No

• Instead of dividing into two equal parts, solve a smaller subproblem by removing
or reducing a single element.

• Example: Topological Sort (remove vertex with no incoming edges, recurse).

Advanced Data Structures and Algorithms (24CSH-232)

Practice Questions
1. Explain the divide and conquer strategy. Why is it preferred over brute
force?
Answer: Divide and conquer works by breaking a problem into smaller subprob-
lems, solving each subproblem independently, and then combining the results to get
the final solution.
Advantages over brute force:

• Reduces time complexity by solving smaller problems.

• Recursion simplifies implementation.
• Enables parallel processing of subproblems.

2. Compare quick sort, merge sort, and heap sort in terms of time com-

Answer:ify
plexity, space complexity, and stability.

• Quick sort: Avg O(n log n), Worst O(n2 ), In-place, Unstable.
• Merge sort: Always O(n log n), Requires O(n) extra space, Stable.
te
• Heap sort: Always O(n log n), In-place, Unstable.

3. What is the difference between divide and conquer and decrease and
No

conquer?
Answer:

• Divide & Conquer splits the problem into multiple subproblems, solves each
recursively, and merges results. Example: Merge Sort.
• Decrease & Conquer reduces problem size by one (or constant), solves recur-
sively. Example: Topological Sort.

4. Define recurrence relation. How is it used to analyze recursive algo-

rithms?
Answer: A recurrence relation expresses the running time of a recursive algorithm
in terms of smaller inputs. Solving it (using substitution, recursion tree, or master
theorem) gives the algorithm’s asymptotic time complexity.

5. Explain Strassen’s matrix multiplication. Why is it faster than standard

multiplication?
Answer: Strassen’s algorithm divides two n × n matrices into n/2 × n/2 submatri-
ces, performs 7 multiplications instead of 8, and combines results. Time complexity
reduces from O(n3 ) to O(n2.81 ).
Advanced Data Structures and Algorithms (24CSH-232)

6. What is a convex hull? Explain how divide and conquer can be applied.
Answer: A convex hull is the smallest convex polygon enclosing a set of points.
Divide: Split points into two halves.
Conquer: Recursively find hulls of each half.
Combine: Merge hulls to form the full convex hull.

7. Why is recursion essential in divide and conquer algorithms? Explain

with example.
Answer: Recursion naturally expresses the divide → solve → combine approach.
Example: Merge Sort recursively splits an array into halves, sorts each half, and
merges.

8. Find min and max of [12,7,9,15,2] using divide and conquer.

Answer:

ify
• Split array: [12,7,9] and [15,2]

• Left half: [12,7,9] → Split → [12,7] & [9] → Compare: min=7, max=12
te
• Right half: [15,2] → Compare: min=2, max=15

• Combine: Overall min = 2, max = 15

No

9. Sort [8,4,5,2] using quick sort.

Answer:

• Pivot=8, partition: [4,5,2] — 8 — []

• Left partition: Pivot=4, [2] — 4 — [5]

• Final sorted array: [2,4,5,8]

10. Sort [10,7,2,5] using merge sort.

Answer:

• Split: [10,7] & [2,5]

• Left: [10,7] → [10] & [7] → Merge → [7,10]

• Right: [2,5] → [2] & [5] → Merge → [2,5]

Advanced Data Structures and Algorithms (24CSH-232)

• Merge final: [2,5,7,10]

11. Perform binary search for 6 in [1,3,5,6,8,9].

Answer:

• Low=0, High=5, Mid=2 → arr[2]=5 ¡6 → search right

• Low=3, High=5, Mid=4 → arr[4]=8 ¿6 → search left

• Low=3, High=3, Mid=3 → arr[3]=6 → Found

12. Illustrate heap sort for [4,10,3,5] step by step.

Answer:

• Build max-heap: [10,5,3,4]

ify
• Swap 10 and 4 → [4,5,3,10], heapify → [5,4,3,10]

• Swap 5 and 3 → [3,4,5,10], heapify → [4,3,5,10]

te
• Swap 4 and 3 → [3,4,5,10], heapify → [3,4,5,10]
No

• Sorted array: [3,4,5,10]

13. Demonstrate Strassen’s multiplication for 2 × 2 matrices: A = [[1, 2], [3, 4]],
B = [[5, 6], [7, 8]]
Answer:

• Compute 7 products P1 to P7 using Strassen formulas

• Combine to get result: [[19, 22], [43, 50]]

14. Find convex hull of points (0,0),(2,2),(3,1),(0,3) using divide and con-
quer.
Answer:

• Split points into two halves: [(0,0),(2,2)] & [(3,1),(0,3)]

• Find hulls of each → Merge → Convex hull points: (0,0),(3,1),(2,2),(0,3)

15. Explain topological sort using decrease and conquer on a DAG.

Answer:
Advanced Data Structures and Algorithms (24CSH-232)

• Identify vertex with in-degree 0 → remove and add to sorted list

• Update in-degrees → Repeat until all vertices processed

• Result: Topologically sorted vertices

16. Compare time complexity of quick sort, merge sort, and heap sort on
large datasets and explain why divide and conquer is beneficial.
Answer:

• Quick sort avg O(n log n), worst O(n2 )

• Merge sort always O(n log n)

ify
• Heap sort always O(n log n)

• Divide and conquer reduces recursion depth, enables parallel processing, and
te
is more efficient than naive brute force.
No
Chapter 6

Greedy Methods

6.1 Introduction to Greedy Approach

ify
Definition: A greedy algorithm builds up a solution piece by piece, always choosing the
next piece that offers the most immediate benefit (locally optimal choice), with the hope
of finding the global optimum.
te
Characteristics of Greedy Algorithms:

• Makes a sequence of choices, each locally optimal.

• Does not reconsider previous choices.

No

• Works well when problem exhibits Greedy Choice Property and Optimal Sub-
structure.

Applications:

• Fractional Knapsack problem

• Minimum Spanning Trees (Prims & Kruskal)

• Huffman Coding

• Job Scheduling Problem

6.2 Fractional Knapsack Problem

Problem: Given weights and values of n items, and a knapsack capacity W , select frac-
tions of items to maximize total value.

36
Advanced Data Structures and Algorithms (24CSH-232)

Greedy Strategy: Pick items in descending order of value/weight ratio until

knapsack is full.

Example: Items: (v1 , w1 ) = (60, 10), (v2 , w2 ) = (100, 20), (v3 , w3 ) = (120, 30)
Knapsack Capacity W = 50
Solution:

1. Compute value/weight ratio:

r1 = 60/10 = 6, r2 = 100/20 = 5, r3 = 120/30 = 4

2. Pick item 1 fully: weight 10, value 60 → remaining capacity = 40

ify
3. Pick item 2 fully: weight 20, value 100 → remaining capacity = 20

4. Pick item 3 partially: weight 20/30 fraction → value = 120 * (20/30) = 80

te
5. Total value = 60 + 100 + 80 = 240

6.3 Minimum Spanning Tree (MST)

No

Definition: A spanning tree of a connected, weighted graph is a tree connecting all

vertices with minimum total edge weight.

Greedy Algorithms for MST:

1. Prims Algorithm

• Start from any vertex, add the smallest weight edge connecting the tree to a
new vertex.
• Repeat until all vertices are included.

2. Kruskal Algorithm

• Sort all edges in ascending order of weight.

• Pick the smallest edge that does not form a cycle.
• Repeat until (V − 1) edges are selected.
Advanced Data Structures and Algorithms (24CSH-232)

6.4 Prim’s Algorithm - Step by Step Example

Graph vertices: A, B, C, D, E
Edge weights:

(A, B) = 2, (A, C) = 3, (B, C) = 1, (B, D) = 4, (C, D) = 5, (C, E) = 6, (D, E) = 7

Solution:

1. Start at vertex A

2. Pick minimum edge connected to A: (A,B)=2

3. Next pick minimum edge connecting tree {A,B}: (B,C)=1

4. Next pick minimum edge connecting tree {A,B,C}: (A,C)=3 → forms cycle, discard.

ify
Next (B,D)=4 → add

5. Next pick edge connecting tree {A,B,C,D} to E: (C,E)=6

6. MST edges: (A,B),(B,C),(B,D),(C,E) with total weight = 2+1+4+6=13

te
6.5 Kruskal’s Algorithm - Step by Step Example
Graph edges sorted by weight: (B, C) = 1, (A, B) = 2, (A, C) = 3, (B, D) = 4, (C, D) =
No

5, (C, E) = 6, (D, E) = 7
Solution:

1. Pick smallest edge (B,C)=1 → add

2. Next edge (A,B)=2 → add

3. Next edge (A,C)=3 → forms cycle → discard

4. Next edge (B,D)=4 → add

5. Next edge (C,D)=5 → forms cycle → discard

6. Next edge (C,E)=6 → add

7. MST edges: (B,C),(A,B),(B,D),(C,E), total weight = 1+2+4+6=13

Advanced Data Structures and Algorithms (24CSH-232)

Practice Questions
Q1: Explain the greedy choice property and give an example.
Answer: The greedy choice property states that a global optimum can be reached by
selecting a local optimum at each step. Example: Fractional Knapsack: Choosing the
item with the highest value/weight ratio first is a local optimal choice that leads to the
global maximum value.

Q2: Solve fractional knapsack problem for items:

(value,weight) = (40,2),(100,20),(50,10) and capacity = 25.
Solution:

1. Compute value/weight ratio:

r1 = 40/2 = 20, r2 = 100/20 = 5, r3 = 50/10 = 5

ify
2. Pick item 1 fully: weight 2, value 40 → remaining capacity = 23

3. Pick item 2 fully: weight 20, value 100 → remaining capacity = 3

te
4. Pick item 3 partially: fraction = 3/10 → value = 50*(3/10)=15
No

5. Total value = 40+100+15=155

Q3: Apply Prim’s algorithm on a graph with vertices A,B,C,D,E,F and

edges: (A,B)=3,(A,C)=1,(B,C)=7,(B,D)=5,(C,D)=2,(D,E)=7,(C,F)=6. Draw
MST.
Solution:

1. Start at A, add smallest edge: (A,C)=1

2. Connect C to smallest edge not forming cycle: (C,D)=2

3. Connect D to smallest edge not forming cycle: (B,D)=5

4. Connect C to smallest edge to F: (C,F)=6

Advanced Data Structures and Algorithms (24CSH-232)

5. Connect D to E: (D,E)=7

6. MST edges: (A,C),(C,D),(D,B),(C,F),(D,E)

Total weight = 1+2+5+6+7=21

Q4: Apply Kruskal’s algorithm on the same graph.

Solution:

1. Sort edges by weight: (A,C)=1, (C,D)=2, (A,B)=3, (B,D)=5, (C,F)=6, (D,E)=7,

(B,C)=7

2. Pick edges without forming cycles:

ify
• (A,C)=1 → add
• (C,D)=2 → add
• (A,B)=3 → add
• (B,D)=5 → forms cycle → discard
te
• (C,F)=6 → add
• (D,E)=7 → add
No

3. MST edges: (A,C),(C,D),(A,B),(C,F),(D,E), total weight = 21

Q5: Compare Prim’s and Kruskal’s algorithm in terms of data structures,

efficiency, and working principle.
Answer:

• Prim: Uses adjacency list/matrix, adds vertices one by one, good for dense graphs.
Complexity: O(E + V log V ) with heap.

• Kruskal: Uses edge list, adds edges one by one avoiding cycles, good for sparse
graphs. Complexity: O(E log E) with union-find.

Q6: Write pseudo-code for fractional knapsack.

Answer:

Sort items by value/weight ratio descending

Initialize totalValue = 0, capacity = W
for each item i in sorted list:
if item weight <= capacity:
Advanced Data Structures and Algorithms (24CSH-232)

take full item

capacity -= weight
totalValue += value
else:
take fraction = capacity / weight
totalValue += value * fraction
break
Return totalValue

Q7: Discuss real-life applications of greedy algorithms.

Answer:

• Financial planning: selecting highest return investments

ify
• Network design: MST for cable layout

• Data compression: Huffman coding

• Scheduling: job scheduling with deadlines

te
Q8: If a greedy algorithm fails to give optimal solution, explain why it
violates greedy choice property with example.
Answer: Greedy algorithm fails if the local choice does not lead to global optimum.
No

Example: 0-1 Knapsack: Greedy by value/weight may select heavy high-ratio items
first, leaving less total value than optimal combination.

Q9: Show step-by-step MST formation using Prim’s algorithm for a weighted
graph of your choice.
Example Graph: Vertices X,Y,Z,W, edges: (X,Y)=4,(X,Z)=1,(Y,Z)=3,(Y,W)=2,(Z,W)=5
Solution:

1. Start at X: pick (X,Z)=1

2. Pick smallest edge to tree: (Z,Y)=3

3. Pick smallest edge to tree: (Y,W)=2

4. MST edges: (X,Z),(Z,Y),(Y,W) with total weight = 1+3+2=6

Advanced Data Structures and Algorithms (24CSH-232)

Q10: Solve fractional knapsack problem where some items can be partially
taken to maximize profit for capacity 30.
Items: (value,weight) = (60,10),(100,20),(120,30)
Solution:

1. Compute value/weight ratio:

r1 = 6, r2 = 5, r3 = 4

2. Take item 1 fully: weight 10, value 60 → remaining capacity = 20

3. Take item 2 fully: weight 20, value 100 → remaining capacity = 0

ify
4. Item 3 cannot be taken

5. Total value = 60+100=160

te
No
Advanced Data Structures and Algorithms (24CSH-232)

Final Examination – Sample Paper

Total Marks : 60
Time Allotted : 3 hours

Instructions:

• The question paper consists of 3 sections. It is compulsory for students to attempt

all questions of Section A and Section B.

• Section A has 5 questions of 2 marks each, Section B has 4 questions of 5 marks

each, and Section C has 4 questions of 10 marks each (out of which any 3 are to be
attempted).

ify
• Question no. 10 & 11 of Section C are compulsory to be attempted.

• Students to attempt ANY ONE question from question no. 12 & question no. 13
of Section C.
te
Section A (5x2 = 10 marks)
1. Explain the difference between iterative and recursive algorithm analysis. Which is
No

generally more space efficient? Why?

2. Using Kruskal’s algorithm, find MST for edges:

(A,B)=3,(A,C)=1,(B,C)=7,(B,D)=5,(C,D)=2.

3. What is topological sort? How is it different from other sorting techniques?

4. Explain heap sort. Sort [4,10,3,5] using heap sort step by step.

5. List the key characteristics of Greedy algorithms. Enlist few problems following the
Greedy approach.

Section B (4x5 = 20 marks)

6. Explain AVL trees. Insert [30, 40, 50] into an empty AVL tree and show rotations.

7. Compare Prim’s and Kruskal’s algorithms. Which is better for sparse graphs?
Why?
Advanced Data Structures and Algorithms (24CSH-232)

8. Apply the two-way merge sort to sort [6,3,9,5,2,8,7,1]. Illustrate the merge process
in detail.

9. Solve fractional knapsack problem: items (value,weight)=(60,10),(100,20),(120,30)

and capacity=50. Show calculation of fractions and total value.

Section C (3x10 = 30 marks)

10. A recursive algorithm has the recurrence T (n) = 2T (n/2) + n. Solve it using the
master theorem.

11. Describe collision resolution strategies: linear probing, quadratic probing, and

ify
chaining. Which is more efficient for high load factor?

12. Explain the divide and conquer approach. Solve min and max of [12,7,9,15,2] using
divide and conquer.
OR
te
" # " #
1 2 5 6
13. Solve Strassen’s matrix multiplication for 2 × 2 matrices: A = ,B= .
3 4 7 8
Verify your answer by performing standard matrix multiplication as well.
No