SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
ASSIGNMENT - I
Course/Code: Advanced Data Structures & Algorithm Analysis/23CS3T03 Max. Marks : 5M
Year / Semester:II/I A.Y: 2025-2026
Answer all the questions:
Question Blooms
Related
Question Taxonomy Marks
No
CO
Level
1 Explain AVL Tree rotations b. create AVL with 10,20,25,5,7,12,9 CO1
L3
2 Explain min-heap and work on example 10,20,5,30,15,3,0 CO1
L3
3 Why is it more useful to analyze the asymptotic behavior of an CO1
L2
algorithm rather than its exact runtime?
4 Delete the nodes in the sequence F M G D B in the CO1
given below tree
L3
5
5 Analyze the following recursive function and determine its CO1
time complexity.
Python
def recursive_sum(n):
L4
if n <= 1:
return 1
return n + recursive_sum(n - 1)
6 Analyze the complexity of the time search, insertion, and deletion CO1
operations in a B-tree of order . How do these complexities L4
compare to an AVL tree?
7 Formulate an algorithm for an in-place deletion of a key from aL6
B- CO1
SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
tree. Explain the various cases (e.g., simple deletion, redistribution,
merging) that your algorithm would need to handle.
8 Given a B-tree of order , insert the following keys: 15, 8, 20, 3, 12, CO1
L3
25, 18. Show the tree's state after all insertions.
9 How would you delete the key 25 from the B-tree created in CO1
the previous question? Show the steps. L3
10 What's the key difference between a standard Binary Search CO1
Tree (BST) and an AVL tree? L1
11 Define the balance factor of a node in an AVL tree. What CO1
are the allowed values? L1
ASSIGNMENT - II
SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
Explain the key difference between Merge Sort
12 and Quick Sort in terms of how they handle the L2 CO2
"combine" step.
Why does Strassen's algorithm improve the
asymptotic time complexity of matrix
13 L2 CO2
multiplication from to? Explain the reduction in a
number of multiplications.
Perform Strassen's multiplication on the following
two 2x2 matrices:
14 L3 CO2
Show all the intermediate matrices (M1 through
M7).
Analyze the best-case, average-case, and worst-
case time complexities of Quick Sort. Why is it
15 L4 CO2
still preferred over Merge Sort in many practical
scenarios despite its worst-case complexity?
Justify why the Divide and Conquer approach is
not always the best solution for all problems.
16 Provide a counterexample of a problem where a L5 CO2
5
different algorithmic paradigm would be more
suitable.
Construct a Max-Heap from the following
unsorted array: [5, 10, 3, 15, 2, 8]. Show the array's
17 L3 CO2
state after each major step of the build-heap
process.
Demonstrate the Heap Sort algorithm on the array
[6, 5, 3, 1, 8, 7, 2, 4]. Show the heap after the
18 L3 CO2
build-heap phase and the array after each
extraction.
Explain the difference between Breadth-First
19 Search (BFS) and Depth-First Search (DFS). L2 CO2
What data structure is used to implement each?
You are given two algorithms to find the
connected components of a graph: one using BFS
20 and one using DFS. Evaluate which algorithm L5 CO2
would be more suitable for a very large, sparse
SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
ASSIGNMENT - III
Question Blooms Marks
Related
Question Taxonomy
No
CO
Level
Solve Single source shortest path for the below figure:
22 L4 CO3
Explain Greedy Algorithms and show how job
23 L3 CO3
sequencing and knapsack problem works
You are a software engineer tasked with finding the
shortest path in a graph that may contain negative
24 L5 CO3
edge weights. Evaluate whether Dijkstra's algorithm
is a suitable choice. Justify your answer.
Solve the 0/1 Knapsack Problem for a knapsack of
capacity 5 with the following items using a dynamic 5
programming table.
25 Item A: (Weight=2, Value=3) L3 CO3
Item B: (Weight=3, Value=4)
Item C: (Weight=4, Value=5)
Given a set of keys and their search probabilities,
construct an Optimal Binary Search Tree and find
the minimum expected search cost.
26 L3 CO3
Keys: A, B, C, D
frequencies:4,2,6,3
27 Compare and contrast the 0/1 Knapsack problem L4 CO3
(solvable with DP) and the Fractional Knapsack
problem (solvable with a greedy approach). Why
does the optimal substructure of the 0/1 Knapsack
SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
problem lend itself to DP?
Why can the Traveling Salesperson Problem be
solved using dynamic programming for a small
28 L4 CO3
number of vertices, but not for a large number?
Analyze the complexity.
Compare Prim's and Kruskal's algorithms for
29 finding an MST. Under what circumstances would L4 CO3
one be more efficient than the other?
Given a set of items with weights and values, use the
Greedy Knapsack algorithm to fill a knapsack with a
capacity of 15. The items are: Item A (Weight=5,
30 Value=25), Item B (Weight=6, Value=30), Item C L3 CO3
(Weight=3, Value=12), Item D (Weight=4,
Value=16). Show the items selected and the total
value.
Given the following jobs, deadlines, and profits, find
the maximum profit using the Job Sequencing with
Deadlines algorithm. Show your steps.
Job A: (Deadline=2, Profit=100)
31 L3 CO3
Job B: (Deadline=1, Profit=10)
Job C: (Deadline=2, Profit=15)
Job D: (Deadline=1, Profit=27)
Explain the concept of memorization in dynamic
32 programming. How does it prevent recomputing the L2 CO3
same subproblem?
ASSIGNMENT - IV
Question Blooms Marks
Related
Question Taxonomy
No
CO
Level
What is the purpose of a state-space tree in backtracking?
What is the difference between a promising node and a
33 L1 CO4
non-promising node?
Given the set S = {3, 5, 6, 7} and a target sum of 15, use
34 the backtracking algorithm to find all subsets that sum to L3 CO4
15. Show the steps of your search.
35 Given a graph with 4 vertices and 3 colors, find a valid L3 CO4
coloring using backtracking. Show the state-space tree
SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
and the color assigned to each vertex.
Trace the backtracking solution for the 8-Queens
36 Problem for a 4x4 board. Show the first few steps of the L3 CO4
state-space tree and the nodes that are pruned.
Analyze the time complexity of the 0/1 Knapsack -5
37 Problem using a backtracking approach. How does this L4 CO4
compare to the dynamic programming solution?
Examine the Map Coloring problem. Why is
38 backtracking essential for solving it, as opposed to a L4 CO4
greedy approach?
Solve the 0/1 Knapsack Problem for a knapsack of
capacity 10 using the Branch and Bound method. The
items are: Item A (Weight=4, Value=10), Item B
39 L3 CO4
(Weight=7, Value=14), Item C (Weight=5, Value=8),
Item D (Weight=3, Value=5). Show the search tree,
including the bounds calculated at each node.
Compare and contrast the backtracking and Branch and
40 Bound solutions to the 0/1 Knapsack Problem. In what L4 CO4
scenarios would you choose one over the other?
Name the two key components of the Branch and Bound
41 L1, L2 CO4
algorithm. And also discuss types of branch bound.
Explain the concept of a "bounding function" and how it
42 L2 CO4
helps in pruning the search space
ASSIGNMENT - V
Question Blooms Marks
Related
Question Taxonomy
No
CO
Level
State the two conditions that a problem must satisfy to be
43 L1 CO5
considered NP-complete.
Explain the relationship between P, NP, NP-complete,
44 and NP-hard problems. Use a Venn diagram to illustrate L2 CO5
the relationships.
Explain the significance of Cook's Theorem. Why is it
45 considered the foundational result for the theory of NP- L2 CO5
completeness?
46 Given a graph G and an integer k, apply the concepts of L3 CO5
the Clique Decision Problem (CDP) to determine if the
SRK INSTITUTE OF TECHNOLOGY,ENIKEPADU, VIJAYAWADA-521108
Approved by AICTE, Affiliated to JNTUK, Kakinada SRKIT
ISO 9001:2015 Certified Institution, Accredited with NAAC ‘A’ Grade /CSD/102
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING-DATA SCIENCE
graph contains a clique of size k. Use a small example
graph and show the steps.
Compare and contrast the Travelling Salesperson
Decision Problem (TSP) and the Job Shop Scheduling
47 L4 CO5
problem. Both are NP-hard. Explain how they are 5
fundamentally similar in their combinatorial nature.
Examine the Chromatic Number Decision Problem
(CNDP). Explain why a brute-force approach of
48 L4 CO5
checking all possible colorings is inefficient, and how it
relates to the problem's NP-completeness.
Describe the fundamental difference between an NP-hard
49 problem and an NP-complete problem. Why might a L2 CO5
problem be NP-hard but not NP-complete?
A computer scientist claims to have found an algorithm
that can solve a famous NP-complete problem in
50 polynomial time. Evaluate the significance of this claim. L5 CO5
What would it imply about the relationship between the
complexity classes P and NP?
Suppose you have a new decision problem X. You are
able to show that a known NP-complete problem Y can
51 be reduced to X in polynomial time. What can you L4 CO5
conclude about the complexity of X? Justify your
answer.
52 How does a problem become classified as NP-hard? L1 CO5
Propose a new heuristic algorithm for a given NP-hard
problem (e.g., Graph Coloring or TSP). Explain the
53 L6 CO5
rationale behind your heuristic and discuss its potential
advantages and disadvantages.
Signature of faculty Signature of HOD
