ADVANCED DATA STRUCTURES AND ALGORITHMS (R1UC531B)
Assignment for ETE
Submission Guidelines for Programming Assignment
• Prepare your solutions in handwritten format and compile them into a single PDF
document.
• The first page of your submission must include the following details clearly:
o Course Title: Advanced Data Structures and Algorithms (R1UC531B).
o Student’s Full Name
o Admission Number
o Section
• Ensure each program includes:
o Clear and correct implementation in any programming language
o Time and space complexity analysis with brief justification
• Deadline for submission on GU LMS: Jan 20, 2026
Instructions: Attempt each section based on the topic. Use diagrams, pseudocode, and examples
wherever applicable. Submit your responses in a well-organized format.
1. Differentiate between Big O, Big Omega, and Big Theta notations with suitable
examples. Why is asymptotic analysis important?
2. Compare static and dynamic arrays. Write an algorithm to find the maximum and
minimum elements in an array and analyse its time complexity.
3. Write an algorithm to reverse an array in-place. Trace the algorithm for the input: {10,
20, 30, 40, 50}.
4. Explain any two methods to find the Kth smallest or Kth largest element in an array.
Compare their efficiencies.
5. Explain the structure and implementation of a singly linked list. Write algorithms for
insertion and deletion at a given position.
6. Differentiate between singly, doubly, and circular linked lists. Mention one real-life
application of each.
7. Implement a stack using a linked list. Explain push and pop operations with diagrams.
8. Convert the infix expression
(A + B) * (C - D)
into postfix expression and explain each step using stack operations.
9. Write an algorithm to evaluate a postfix expression and show the evaluation steps for:
23*54*+9-
10. Explain the principles of recursion. Differentiate between tail recursion and non-tail
recursion with examples.
11. Write a recursive algorithm to compute:
a) Fibonacci series
b) (a^n) (a raised to the power n)
Analyse the time complexity of both.
12. Implement a queue using linked list. Explain enqueue and dequeue operations. How
does a priority queue (heap) differ from a normal queue?
13. Explain the concept of hashing. Discuss collision resolution techniques such as
chaining and linear probing with examples.
14. Trees
a) Construct a binary tree from the following traversals:
o Inorder: D B E A F C
o Preorder: A B D E C F
b) Explain inorder, preorder, and postorder traversals of a Binary Search Tree.
c) Describe insertion, deletion, and searching in a BST.
15. Given the undirected graph with vertices {0,1,2,3,4} and edges {(0–1), (0–2), (1–3),
(2–4)}
a) Perform DFS starting from vertex 0
b) Perform BFS starting from vertex 0
16. Explain how to detect a cycle in an undirected graph using DFS. Write program for
DFS. For the graph with edges {(0–1), (1–2), (2–3), (3–1)}, determine whether
a cycle exists using DFS.
17. Define connected components in an undirected graph. Write a program to find the
number of connected components. Given vertices {0,1,2,3,4,5} and edges
{(0–1), (1–2), (3–4)}, find the number of connected components.
18. Write program for Prim’s and Kruskal Algorithm. Given the weighted graph:
Edge Weight
A–B 2
A–C 3
B–C 1
B–D 4
C–D 5
Apply Prim’s algorithm and Kruskal algorithm and find the MST and its total cost.
19. Write program for Floyd Warshall algorithm. Given the adjacency matrix below, find
the shortest paths between all pairs using Warshall’s algorithm:
0 3 ∞ 7
8 0 2 ∞
5 ∞ 0 1
2 ∞ ∞ 0
20. Write a program for longest common subsequence. Find the length and DP table for
the LCS of strings:
X = "AGGTAB"
Y = "GXTXAYB"
21. Write the program for Coin Change (Minimum Coins) problem.
Given coins {1, 3, 4} and target value 6, find the minimum number of coins using
dynamic programming.
22. Write program for 0/1 Knapsack.
Given:
Item Weight Value
1 2 12
2 1 10
3 3 20
4 2 15
Knapsack capacity = 5
Construct the DP table and find the maximum profit.
23. Write the program for Sum of set problem. Given set {10, 7, 5, 18, 12, 20, 15}
and target sum 35, find all possible subsets using backtracking.
24. Write the program for N-Queen problem. Place 4 queens on a 4 × 4 chessboard such
that no two queens attack each other. Show all valid solutions.
25. What is probabilistic data structure.
26. Write a program to solve fractional knapsack problem.
Given:
Item Weight Profit
A 10 60
B 20 100
C 30 120
Knapsack capacity = 50, Find the maximum profit using the greedy approach.
27. Write a program for Activity Selection problem.
Given activities with (start, finish) times:
(1,2), (3,4), (0,6), (5,7), (8,9), (5,9)
Select the maximum number of non-overlapping activities.
28. Write a program for Job Sequencing with Deadlines problem.
Job Deadline Profit
J1 2 60
J2 1 100
J3 3 20
J4 2 40
J5 1 20
Determine the job sequence that maximizes profit.
29. Write a program for Huffman Coding.
Construct the Huffman tree and codes for the characters:
Character Frequency
A 5
B 9
C 12
D 13
E 16
F 45
Case Study Based Problems
1. Minimum Spanning Tree (MST)
Case Study:
A telecommunications company wants to lay fiber optic cables to connect 6 cities (A, B, C,
D, E, F). The cost to connect each pair of cities is given in the table below:
From To Cost
A B 4
A C 2
B C 1
B D 5
C D 8
C E 10
D E 2
D F 6
E F 3
Questions:
a) Construct the Minimum Spanning Tree using Prim’s algorithm.
b) Construct the MST using Kruskal’s algorithm.
c) Compare the total cost of both MSTs.
d) Suggest which algorithm is better for this network scenario and why.
2. Longest Common Subsequence (LCS)
Case Study:
A DNA research lab is analyzing genetic sequences. Two DNA sequences are:
• Sequence 1: ACGTAG
• Sequence 2: GACTAG
Questions:
a) Find the Longest Common Subsequence (LCS).
b) Suggest how LCS can help in genetic similarity analysis.
c) Draw the DP table used to calculate the LCS.
3. Coin Change (Minimum Coins)
Case Study:
A vending machine dispenses coins of denominations {1, 3, 4}. A customer wants to get 6
units as change.
Questions:
a) Determine the minimum number of coins required using dynamic programming.
b) Show the DP table used in your solution.
c) Discuss what happens if one coin type is removed. How does it affect the solution?
4. All pairs Shortest Path – Floyd-Warshall Algorithm
Case Study:
A logistics company wants to determine the shortest distance between its warehouses (nodes
0,1,2,3) based on the following distance matrix:
0 3 ∞ 7
8 0 2 ∞
5 ∞ 0 1
2 ∞ ∞ 0
Questions:
a) Apply Floyd-Warshall Algorithm to find the shortest paths between all pairs of
warehouses.
b) Identify the most cost-effective route from warehouse 0 to 3.
c) Discuss how this algorithm can help in routing optimization.
5. 0/1 Knapsack (Dynamic Programming)
Case Study:
A delivery drone can carry a maximum weight of 5 kg. The following packages are available:
Package Weight (kg) Value ($)
P1 2 12
P2 1 10
P3 3 20
P4 2 15
Questions:
a) Determine which packages the drone should carry to maximize total value.
b) Construct the DP table.
c) Explain how this solution helps in resource optimization for delivery services.
6. Fractional Knapsack (Greedy Algorithm)
Case Study:
A jewellery company wants to ship gold bars in a truck with capacity 50 kg. Available bars:
Bar Weight (kg) Value ($)
A 10 60
B 20 100
C 30 120
Questions:
a) Determine the maximum value the truck can carry using the fractional knapsack
approach.
b) Discuss how fractional knapsack is different from 0/1 Knapsack in this context.
7. Activity Selection (Greedy)
Case Study:
A conference hall has activities scheduled at these times:
(1,2), (3,4), (0,6), (5,7), (8,9), (5,9)
Questions:
a) Select the maximum number of non-overlapping activities.
b) Discuss how this approach can be applied in resource allocation in meeting rooms.
8. Huffman Coding (Greedy)
Case Study:
A file contains the following characters and frequencies:
Character Frequency
A 5
B 9
C 12
D 13
E 16
F 45
Questions:
a) Construct the Huffman tree.
b) Generate the Huffman codes for each character.
c) Explain how Huffman coding reduces storage requirements in file compression.
9. Job Sequencing Problem (Greedy)
Case Study:
A factory has jobs with deadlines and profits:
Job Deadline Profit
J1 2 60
J2 1 100
J3 3 20
J4 2 40
J5 1 20
Questions:
a) Determine the sequence of jobs to maximize profit.
b) Explain how greedy strategy ensures optimal profit.