Course Code: 23CI0601 R23

SIDDHARTHA INSTITUTE OF SCIENCE AND TECHNOLOGY:: PUTTUR

(AUTONOMOUS)
Siddharth Nagar, Narayanavanam Road – 517583

QUESTION BANK (DESCRIPTIVE)

Subject with Code: Data Structures & Algorithms (23CI05601) Regulation: R23
Course & Branch: B.Tech – CSE,CSM,CIA,CAD Year & Sem: II Year & I Sem

UNIT-I
INTRODUCTION, AVL TREES, B-TREES

1 a) What do you mean by algorithm? List some of the properties of it. [L1] [CO1] [2M]
b) Discuss the steps involved in performance analysis. [L2] [CO1] [2M]
c) Define Balance Factor. [L2] [CO1] [2M]
d) What is an AVL tree? Give one example. [L1] [CO1] [2M]
e) What is B-Tree? Give one example. [L1] [CO1] [2M]
2 a) Illustrate an algorithm for Finding sum of natural number. [L2] [CO1] [5M]
b) Analyze space complexity and time complexity in detail with example. [L4] [CO1] [5M]
3 What is Asymptotic Notation? Explain different types of notations with [L2] [CO1] [10M]
examples.
4 Discuss briefly with suitable example about Big ‘O’ notation and Theta [L2] [CO1] [10M]
notation ‘Ѳ’.
5 a) Discuss factors affecting the time complexity. [L2] [CO1] [5M]
b) Compare between Priori analysis and Posteriori analysis. [L4] [CO1] [5M]
6 Explain different AVL rotations with suitable examples. [L2] [CO1] [10M]
7 a) Write the applications and operations of an AVL tree. [L3] [CO1] [5M]
b) Define the Balance Factor of a node in an AVL tree. How is it calculated, [L2] [CO1] [5M]
and what is its significance?
8 Construct an AVL Tree by inserting numbers from 1 to 8. [L6] [CO1] [10M]
9 a) Write the applications and Operations of the B-Tree. [L3] [CO1] [5M]
b) Elaborate the B-Tree Deletion Operation with suitable example. [L3] [CO1] [5M]
10 Construct a B-Tree of order 3 by inserting numbers 1 to 10. [L3] [CO1] [10M]
Course Code: 23CI0601 R23
UNIT –II
HEAP TREES, GRAPHS, DIVIDE AND CONQUER

1 a) Define Heapify. [L2][CO2] [2M]

b) List out the applications of Heap tree. [L1][CO2] [2M]
c) What is directed and undirected graph? [L1][CO2] [2M]
d) Define Articulation point? [L2][CO2] [2M]
e) Construct Strassen’s 2×2 matrix. [L3][CO2] [2M]
2 a) Explain in detail about operations of Heap Tree. [L2][CO2] [5M]
b) Construct Max Heap Tree for the following elements 32, 15, 20, 30, 12, 25, [L3][CO2] [5M]
16.
3 Draw the Spanning Tree for the given graph using DFS and BFS algorithm. [L1][CO2] [10M]

4 a) Compare between Min heap and Max heap. [L2][CO2] [5M]

b) Explain Graph representations with suitable example. [L2][CO2] [5M]
5 Explain Graph Traversal techniques with neat example. [L2][CO2] [10M]
6 a) Discuss Connected components and Bi-connected components along with [L2][CO2] [5M]
Applications.
b) Sort the records with the following index values in the ascending order using [L2][CO2] [5M]
Quick Sort algorithm, 10,80,30,90,40,50 and 60.
7 Analyze the working strategy of merge sort and illustrate the process of [L4][CO2] [10M]
Merge Sort algorithm for the given data: 43, 32, 22, 78, 63, 57, 91 and 13.
8 Summarize an algorithm for quick sort. Provide a complete analysis of quick [L3][CO2] [10M]
sort for given set of numbers 40,20,70,14,60,61,97 and 30.
9 a) Explain the General Method of Divide and Conquer Method. [L2][CO2] [5M]
b) Explain about Convex Hull with example. [L2][CO2] [5M]
10 [L6][CO2] [10M]

Create Stassen’s matrix multiplication on A and B. Find the resultant matrix.

Course Code: 23CI0601 R23
UNIT –III
GREEDY METHOD, DYNAMIC PROGRAMMING
1 a) Define greedy method. [L2][CO2] [2M]
b) Discuss the disadvantages of greedy method. [L2][CO2] [2M]
c) What is Spanning Tree? [L1][CO2] [2M]
d) What is 0/1 knapsack problem. [L1][CO2] [2M]
e) Explain dynamic programming. [L2][CO2] [2M]
2 a) Solve job sequencing with deadlines by using greedy method where given [L3][CO3] [5M]
the jobs, their deadlines and associated profits as shown below. Calculate
maximum earned profit.
Jobs J1 J2 J3 J4 J5 J6
Deadlines 5 3 3 2 4 2
Profits 200 180 190 300 120 100

b) Build any one application of dynamic programming with an example. [L3][CO1] [5M]
3 Construct an optimal solution for Knapsack problem, where n=7,M=15 and [L3][CO3] [10M]
(p1,p2,p3,p4,p5,p6,p7) = (10,5,15,7,6,18,3) and (w1,w2,w3,w4,w5,w6,w7) =
(2,3,5,7,1,4,1) by using Greedy strategy.
4 Implement the Single Source Shortest Path using Dijkstra’s algorithm for the [L4][CO3] [10M]
given graph.

5 What is Minimum Cost Spanning Tree? Implement the Kruskal’s algorithm [L1][CO3] [10M]
and Prims algorithm.

6 Construct optimal binary search tree for the given problem n=4,(a1,a2,a3,a4)= [L6][CO3] [10M]
(a,b,c,d), P(1,2,3,4,)=(3,3,1,1),Q(0,1,2,3,4)=(2,3,1,1,1).
7 Solve Single Source Shortest Paths problem using dynamic programming. [L3][CO3] [10M]
Course Code: 23CI0601 R23
8 a) Explain 0/1 knapsack problem by using dynamic programming with an [L2][CO3] [5M]
examples.
b) Measure the String Editing problem with example. [L5][CO3] [5M]
9 Construct an algorithm for All pairs of shortest path and calculate shortest [L6][CO3] [10M]
path between all pairs of vertices by using dynamic programming method
for the following graph.

10 Analyze the minimum cost tour for given problem in travelling sales person [L4][CO3] [10M]
Concepts by using dynamic programming.
Course Code: 23CI0601 R23
UNIT –IV
BACKTRACKING, BRANCH AND BOUND

1 a) Define Backtracking. [L2][CO2] [2M]

b) Solve 4-Queens problem. [L1][CO2] [2M]
c) What is Graph coloring? [L2][CO2] [2M]
d) What is Branch and Bound? [L1][CO2] [2M]
e) State the Container problem. [L2][CO2] [2M]
2 a) Consider a set S= {5,10,12,13,15,18} and d=30. Solve it for obtaining Sum [L6][CO4] [5M]
of Subset using Backtracking method.
b) Recall the Graph Coloring. Explain in detail about graph coloring with an [L3][CO4] [5M]
example..
3 Describe how the backtracking method is applied to solve the 8-Queens [L5][CO4] [10M]
problem.
4 Compare Back Tracking and Branch and Bound methods by taking an [L4][CO4] [10M]
example.
5 Construct the State space tree for the profits={3,5,6,10} and [L3][CO4] [10M]
weights={2,3,4,5},n=4 and m=8 (Capacity). Apply the backtracking for 0/1
Knapsack and also find the Maximum profit.
6 a) Solve 4 – queens problem by generating state space tree . [L3][CO4] [5M]
b) Explain the principles of LIFO branch and bound. [L2][CO4] [5M]
7 Find the LC branch and bound solution for the traveling sale person problem [L4][CO4] [10M]
whose cost matrix is as follows:

8 Simplify 0/1 knapsack problem and design an algorithm of LC Branch and [L4][CO4] [10M]
Bound and find the solution for the knapsack instance of n = 4,(p1, p2, p3,
p4) = (10, 10, 12, 18), (w1,w2, w 3, w4) = (2, 4, 6, 9) and M = 15.
9 a) Explain the procedure for Travelling Sales Person Problem using branch and [L2][CO4] [5M]
bound.
b) Explain the principles of FIFO branch and bound. [L2][CO4] [5M]

10 a) Describe the general method of branch and bound. [L1][CO4] [5M]

b) Explain the role of the state-space tree in branch and bound techniques. [L4][CO4] [5M]
Course Code: 23CI0601 R23
UNIT –V
NP HARD AND NP COMPLETE PROBLEMS

1 a) Define P class and NP Class. [L2][CO2] [2M]

b) What are NP complete and NP Hard? [L1][CO2] [2M]
c) State deterministic algorithm? [L1][CO2] [2M]
d) Discuss about Non-deterministic algorithm? [L2][CO2] [2M]
e) What is Chromatic Number? [L1][CO2] [2M]
2 a) Explain and shows the relationship between P,NP,NP Hard and NP Complete [L2][CO5] [5M]
with neat diagram
b) Summarize non deterministic algorithm with an example. [L3][CO5] [5M]
3 a) Determine the classes NP-hard and NP-complete problem with example. [L3][CO5] [5M]
b) Illustrate the Satisfiability [SAT] problem. [L3][CO5] [5M]
4 a) State and Explain Cook’s theorem. [L1][CO5] [5M]
b) How to make reduction for 3-SAT to Clique Decision problem? and Explain [L1][CO5] [5M]
5 Explain why Clique Decision Problem is NP-hard with suitable an example. [L2][CO5] [10M]
6 Explain why Chromatic Number Decision Problem is NP-hard in detail with [L2][CO5] [10M]
an example.
7 a) Build Traveling salesperson Decision Problem with example. [L3][CO5] [5M]
b) Discuss about Chromatic Number Decision Problem in detail. [L2][CO5] [05M]
8 Explain why Traveling Sales person Decision Problem is NP-Hard with an [L2][CO5] [10M]
example.
9 Analyze Scheduling Identical Processors in NP Hard Scheduling Problem. [L4][CO5] [10M]
10 Describe Job Shop Scheduling in NP Hard Scheduling Problem. [L1][CO5] [10M]

Prepared by: V.GOPI,K.PURNIMA,B.HIMA BINDU,SHILPA