Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur

Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

Set-I
Q.No Question BL CO MM
1 A company stores employee IDs in a Binary Search Tree (BST). 3 3 10
Each node represents an employee ID. Due to frequent searches and
additions, the tree becomes unbalanced. Illustrate how an AVL tree
could help maintain balance, and perform a rotation example on a set
of IDs [5, 3, 8, 2, 4, 7, 9,12,16,1] if needed.

2 A delivery service wants to minimize road usage while connecting 4 3 10

several warehouse locations in a city. Analyze how the Minimum
Spanning Tree (MST) algorithm can optimize the routes between
warehouses. Provide a step-by-step application of Prim's and
Kruskal’s algorithm on below graph.

3 A database holds customer records by their unique IDs. Explain how 3 4 10

hashing can efficiently handle quick access to records. Demonstrate
how a hash function would handle IDs [121, 123, 127,
130,133,137,140] using a modulo hash function with collision
resolution by linear probing.

4 You are given unsorted scores [43, 87, 12, 99, 58, 33, 27,45,66,50] 3 4 10
from a class test and need to display them in descending order for
award allocation. Apply the quicksort algorithm step-by-step to
arrange these scores. Also mention time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40
SET-II

Q.No Question BL CO MM
1 An online library catalog system uses a B-Tree to store book records due 4 3 10
to its efficiency in handling large amounts of data. Illustrate how the B-
Tree would handle a large volume of book records, and show how a new
record with ID 36 is added to an existing B-Tree with nodes [20, 30, 40,
50,60,65,70,15].

2 A GPS navigation system needs to find the shortest route between two 3 3 10
locations. Demonstrate how Dijkstra's algorithm finds the shortest path,
and apply it step-by-step to find the shortest path on a simple weighted
graph.

3 In a phone directory application, explain how binary search is used to 3 4 10

quickly find a person’s phone number. If a directory has sorted names
[Adams, Carter, David, Evans, James, Johnson, Smith, Williams],
demonstrate a binary search to find the position of Johnson.

4 A set of patient records [102, 88, 145, 36, 50, 77, 110, 37, 90, 86] need 3 4 10
to be sorted by admission date for proper queue management. Show
step-by-step how selection sort would organize these records. Also
mention time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40
SET-III

Q.No Question BL CO MM
1 Demonstrate how in-order, pre-order, and post-order traversal techniques 3 3 10
would be used in a medical imaging storage system (such as MRI scan
data). If given a binary tree with nodes [A, B, C, D, E, F, G, H, I, J, K],
perform an in-order, pre-order, and post-order traversal and list the output
sequence.

2 A social network wants to check for connected communities. Illustrate 4 3 10

how Breadth First Search (BFS) can be used to explore the connections
and show each step of BFS for below graph. (You can select A as starting
vertex).

3 In a product inventory system, hash-based indexing is used to find product 3 4 10

information quickly. Apply hash function h(x) = x % 10, hash the IDs [23,
34, 45, 12, 56, 69, 43, 54, 75] with collision resolution using quadratic
probing. Also explain popular hash functions.
4 Show the process step-by-step that insertion sort would be suitable for 3 4 10
sorting a nearly sorted sales transaction list [10, 5, 15, 20, 25,12, 9, 18,
27, 23,12]. Also mention time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

SET-IV

Q.No Question BL CO MM
1 A video game uses a Binary Search Tree to manage in-game items 4 3 10
by rarity levels. Analyze how a BST would optimize the search for
a specific rarity level and perform insertion of items [10, 5, 15, 2, 7,
12, 17,20,18, 6, 9] into a BST.

2 To schedule maintenance across multiple network nodes, a 3 3 10

company wants to ensure connectivity while minimizing
redundancy. Use Kruskal’s algorithm and Prim’s algorithm to form
a Minimum Spanning Tree for below graph, explaining each step.

3 Explain the use of hashing in organizing data in a digital library 3 4 10

system. Use a common hash function to hash book IDs [102, 210,
305, 405, 506, 270,195, 170] and show the resulting hash table
with linear probing for collisions.

4 Show how heap sort can be used to order priority tasks in a to-do 3 4 10
list [20, 50, 10, 5, 15, 40, 35,45]. Provide a step-by-step solution to
sort this list. Also mention time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment -II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

SET-V
Q.No Question BL CO MM
1 Analyze how a self-balancing AVL tree can improve search 4 3 10
efficiency in an online ticket reservation system. Given the sequence
[30, 20, 40, 10, 25, 35, 50], draw the AVL tree after each insertion,
indicating any rotations required.

2 A municipal planning team needs to analyze shortest paths for an 3 3 10

emergency response system. Describe how Depth First Search
(DFS) could help map routes. Use DFS on a below graph and outline
each step (You can select 0 as starting vertex).

3 An e-commerce platform uses a hash function to quickly access user 3 4 10

data. Demonstrate a hash function with collision resolution using
quadratic probing for the user IDs [305, 420, 317, 522, 609,550, 427,
329]. Also explain some popular hash functions.

4 Apply radix sort to arrange employee ID numbers [170, 45, 75, 90, 3 4 10
802, 24, 2, 66, 55, 96, 672] in ascending order and show the
sorting stages. Also mention time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

SET-VI
Q.No Question BL CO MM
1 Explain how a Binary Tree can be used to represent and analyze the 4 3 10
structure of a file directory. Using a sample structure with folders
and subfolders as nodes, performing pre-order and in-order traversal
to print the folder names in sequence.

2 A company wants to calculate the shortest route for its logistics 3 3 10

network between distribution points. Apply Dijkstra’s algorithm to
below graph providing the shortest path between two specific nodes
with complete steps.

3 Explain the use of hashing in organizing data in a digital library 3 4 10

system. A local library system wants to use hashing to organize
books by their catalog numbers. Use the hash function h(x) = x % 7
and apply it to the catalog numbers [34, 78, 21, 56, 63, 90,77,12,
49] with linear probing for collision resolution.

4 Describe the bubble sort method by sorting a list of daily sales [33, 3 4 10
15, 17, 29, 10, 45, 20, 25, 60, 12, 19] in ascending order. Show each
swap step by step until the list is fully sorted. Explain the use of
hashing in organizing data in a digital library system. Also mention
time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

SET-VII
Q.No Question BL CO MM
1 In an online ordering system, customer orders are organized based 3 3 10
on urgency levels. If each order's urgency level is represented as a
node in an AVL Tree, explain how balancing the tree after each new
order improves retrieval efficiency. Insert the urgency levels [30,
15, 40, 10, 25, 35, 50] step-by-step, showing the AVL tree structure
and rotations after each insertion.

2 A telecom company needs to lay cables between several cities with 3 3 10

minimum cost and ensure each city is connected. Describe how the
Minimum Spanning Tree (MST) can be used to minimize costs.
Apply Kruskal’s and Prim’s algorithm to a sample graph showing
each step to obtain the MST.

3 In a medical database, patient IDs are hashed for faster lookup. 3 4 10

Using a hash function h(x) = x % 13, insert the IDs [126, 139, 142,
154, 177, 189, 190, 193] into the hash table, using quadratic probing
for collision resolution. Illustrate each step in constructing the hash
table.

4 A large supermarket chain needs to analyze weekly sales data. 4 4 10

Given a set of sales amounts [275, 150, 500, 90, 200, 305, 400, 405,
165], show how heap sort would organize these amounts from
lowest to highest, providing each step in building and sorting the
heap. Also mention time complexity of all cases.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

(Set-VIII)
Q.No Question BL CO MM
1 You are given a Binary Search Tree (BST) containing the 3 3 10
elements [50, 30, 70, 20, 40, 60, 80]. Write a function to find the
Lowest Common Ancestor (LCA) of two nodes in this BST. The
function should efficiently compute the LCA when given two
node values (e.g., 20 and 40). Demonstrate your approach and
provide the time complexity.

2 A logistics company wants to find the optimal route between its 3 3 10

warehouses. You are given a graph with nodes representing
warehouses and edges representing roads with weights as travel
times. Implement Dijkstra’s algorithm to find the shortest travel
time between a given warehouse A and all other warehouses.
Consider the following graph represented as an adjacency list:

3 Apply a hash table that uses quadratic probing to handle 3 4 10

collisions. Implement the insertion and search functions for a
hash table of size 7 and insert the elements [10, 22, 31, 4, 15, 28,
17]. Show each step of the insertion process and explain how
quadratic probing resolves collisions.

4 A sorting algorithm is required for a time-sensitive application 3 4 10

where each element is associated with an integer key. You are
given an array of integers [170, 45, 75, 90, 802, 24, 2, 66].
Implement Radix Sort to sort this array. Explain how Radix Sort
works, and show the step-by-step process for sorting this array.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

(Set-IX)
Q.No Question BL CO MM
1 You are tasked with designing an AVL Tree to maintain a dynamic 3 3 10
set of customer records where the key is the customer ID. Insert the
following customer IDs into an initially empty AVL Tree: [10, 20,
30, 25, 28, 27, 5]. Show the AVL Tree after each insertion,
including any necessary rotations.

2 Given a network of computers where the following graph represents 3 3 10

the connections between them, perform a Depth-First Search (DFS)
starting from node A:

Use a stack to simulate the DFS and provide the order in which the
nodes are visited. If two nodes have the same discovery time,
prioritize alphabetically.

3 Implement a hash table using chaining (linked lists) for collision 3 4 10

resolution. The hash function is h(x) = x % 10. Insert the following
elements into the hash table: [15, 25, 35, 20, 30, 40, 50].
Demonstrate how the chaining mechanism works, and write a
function to search for the element 30 in the hash table.

4 You are given an array of 1 million elements and need to sort it as 4 4 10

quickly as possible. Given the constraints, you decide to use Quick
Sort. Explain the worst-case scenario for Quick Sort and how you
can improve the algorithm’s efficiency. Use the following array to
demonstrate: [10, 80, 30, 90, 40, 50, 70].
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40
(Set-X)
Q.No Question BL CO MM
1 Construct a B-Tree of order 3 using the following elements: [10, 3 3 10
20, 5, 6, 12, 30, 7, 17]. Show the tree after each insertion.

2 A company’s delivery system is represented by the following graph, 3 3 10

where nodes represent locations and edges represent roads with
distances:

Find the shortest path from location A to F using Dijkstra’s

algorithm.

3 An array has the following elements: [54, 26, 93, 17, 77, 31, 44, 55, 3 4 10
20]. Demonstrate the steps involved in searching for the number 77
using binary search. First, sort the array and then proceed with the
binary search steps.

4 Implement the Counting Sort algorithm to sort the following array: 3 4 10

[4, 2, 2, 8, 3, 3, 1]. Show each step of the counting array creation
and the final sorted output.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

(Set-XI)
Q.No Question BL CO MM
1 You are given a list of numbers: [20, 10, 30, 5, 15, 25, 35]. Construct 3 3 10
a Binary Search Tree (BST) from this list. After constructing the
tree, perform an in-order, pre-order, and post-order traversal, and
provide the output for each traversal.
2 Consider a connected undirected graph represented by the 3 3 10
following adjacency matrix:

Using Prim’s algorithm, find the minimum spanning tree (MST)

and the total weight of the MST.

3 A company's employee data is stored in an array where each 4 4 10

element represents an employee's ID. Design a hash function to
store and search the employee data using chaining as the collision
resolution technique. Illustrate with the employee IDs: [1234, 5678,
9101, 1121, 3141, 1617, 1820] and a hash table size of 5.

4 Sort the following array using Quick Sort: [29, 10, 14, 37, 14]. Show 3 4 10
each step of the sorting process, including the selection of the pivot
element at each stage.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-II
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

(Set-XII)

Q.No. Question BL CO MM
1 A database needs to store records in a balanced tree structure for 4 3 10
efficient search, insertion, and deletion operations. Justify why an
AVL Tree or a B-Tree is more suitable for this purpose than a
normal binary search tree (BST). Provide a real-life example
where this might be used.

2 A tech company’s network is modeled as an undirected graph. The 3 3 10

goal is to ensure that all servers remain connected while minimizing
the total connection cost. Use Kruskal’s algorithm to find the
Minimum Spanning Tree (MST) for the following graph:

Show each step, including edge selection and cycle detection.

3 In a social media application, user profiles are stored using hash 4 4 10

tables. Each profile is identified by a unique username. Apply a
hash function for storing usernames and implement a collision
resolution mechanism using chaining. Insert the following
usernames: ["alice", "bob", "charlie", "david", "eve"]. Search for
the username "david" and explain how collisions are resolved.

4 Consider a scenario where you need to sort user data by their 3 4 10

registration timestamps. You are given the following data: [170, 45,
75, 90, 802, 24, 2, 66]. Use Counting Sort to sort the data and
explain how it is particularly useful for certain types of inputs like
this.
 Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering

Assignment Sheet-I
Session 2024_25 (Odd Semester)

Subject: Data Structure & Algorithm (3CDS4-05)

Max Marks- 40

(Set-XIII)

Q. Question BL CO MM
No.
1 Given a Binary Tree that represents a file directory structure, write an 3 3 10
algorithm to convert this Binary Tree into its mirror image (left and
right children of all nodes are swapped). For example, given the tree:

mirror image →

2 Construct the minimum spanning tree (MST) for the given graph 3 3 10
using Kruskal’s Algorithm. Also find total weight of the MST.

3 Consider an array of product IDs [45, 23, 89, 12, 78, 67, 49]. 3 4 10
Implement a binary search algorithm to find whether the product ID
67 exists in the array. First, sort the array using any sorting algorithm,
then apply binary search. Explain each step of the binary search
process.

4 You are tasked with implementing a sorting algorithm for a time- 3 4 10

sensitive system. Given the array [64, 34, 25, 12, 22, 11, 90], sort the
array using Heap Sort. Show how Heap Sort works and why it is an
efficient choice for large datasets.
Swami Keshvanand Institute of Technology, Management &Gramothan, Jaipur
Department of Computer Science & Engineering