Course Code: 23CS0507 R23

SIDDHARTH INSTITUTE OF ENGINEERING & TECHNOLOGY:: PUTTUR

(AUTONOMOUS)
Siddharth Nagar, Narayanavanam Road – 517583

QUESTION BANK (DESCRIPTIVE)

Subject with Code: Advanced Data Structures & Algorithm Analysis (23CS0507) Regulation: R23
Course & Branch: B.Tech – CSE,CIC,CCC,CAI,CSM,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) Simplify 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) Analyze space complexity and time complexity in detail with example. [L4] [CO1] [2M]
b) Illustrate an algorithm for Finding sum of natural number. [L2] [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. [L3] [CO1] [5M]
b) Compare between Priori analysis and Posteriori analysis. [L5] [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: 23CS0507 R23
UNIT –II
HEAP TREES, GRAPHS, DIVIDE AND CONQUER

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

b) What is Articulation point? [L1][CO2] [2M]
c) What is directed and undirected graph? [L1][CO2] [2M]
d) Write the applications of Heap tree. [L3][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) Define Connected components and Bi-connected components along with [L2][CO2] [5M]
Applications
b) Explain Graph representations with suitable example. [L2][CO2] [5M]
5 Explain Graph Traversal techniques with neat example. [L2][CO2] [10M]
6 a) Compare between Min heap and Max heap. [L5][CO2] [5M]
b) Sort the records with the following index values in the ascending order using [L2][CO2] [5M]
Quick Sort algorithm. 9, 7, 5, 11, 12, 2, 14, 3, 10, 6.
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 12, 3, 18, 21, 4, 55, 64, 77and 76.
9 a) Explain about Convex Hull with example. [L2][CO2] [5M]
b) Explain the General Method of Divide and Conquer Method. [L2][CO2] [5M]
10 [L6][CO2] [10M]

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

Course Code: 23CS0507 R23
UNIT –III
GREEDY METHOD, DYNAMIC PROGRAMMING
1 a) Differentiate greedy and dynamic programming. [L2][CO2] [2M]
b) Define knapsack problem using greedy approach. [L2][CO2] [2M]
c) What is Spanning Tree? [L1][CO2] [2M]
d) What is 0/1 knapsack problem. [L1][CO2] [2M]
e) Define Job sequencing with deadlines. [L2][CO2] [2M]
2 Elaborate job sequencing with deadlines by using greedy method where [L6][CO3] [10M]
given 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

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] [5M]
given graph.

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

6 a) Discuss about Optimal binary search tree with suitable example. [L2][CO3] [5M]
b) Build any one application of dynamic programming with an example. [L6][CO1] [5M]
7 Solve Single Source Shortest Paths problem using dynamic programming. [L3][CO3] [5M]
Course Code: 23CS0507 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 betweenall 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: 23CS0507 R23
UNIT –IV
BACKTRACKING, BRANCH AND BOUND

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

b) What is Graph coloring? [L1][CO2] [2M]
c) Solve 4-Queens problem. [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) Describe how the backtracking method is applied to solve the 8-Queens [L3][CO4] [5M]
problem.
3 Recall the Graph Coloring. Explain in detail about graph coloring with an [L5][CO4] [10M]
example.
4 Analyze the least cost search approach in branch and bound. [L4][CO4] [10M]
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) Explain the principles of FIFO branch and bound. [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 Construct the LC branch and bound search. Consider knapsack instance n=4 [L6][CO4] [10M]
with capacity M=15 such that pi={10,10,12,18}, wi={2,4,6,9}apply FIFO
branch and bound technique.
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: 23CS0507 R23
UNIT –V
NP HARD AND NP COMPLETE PROBLEMS

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

b) What are NP complete and NP Hard? [L1][CO5] [2M]
c) What is Chromatic Number? [L1][CO5] [2M]
d) What is deterministic algorithm? [L1][CO5] [2M]
e) What is non-deterministic problem? [L1][CO5] [2M]
2 Construct the non-deterministic algorithms with suitable example. [L3][CO5] [10M]
3 Build the non-deterministic sorting algorithm and also analyze its complexity. [L6][CO5] [10M]
4 Determine the classes NP-hard and NP-complete problem with example. [L5][CO5] [10M]
5 State and Explain Cook’s theorem. [L2][CO5] [10M]
6 Illustrate the Satisifiability problem and write the algorithm. [L4][CO5] [10M]
7 Explain Traveling Salesperson Decision Problem With example. [L4][CO5] [10M]
8 a) Explain about Chromatic Number Decision Problem in detail. [L4][CO5] [05M]
b) Explain about Clique Decision Problem in detail. [L4][CO5] [05M]
9 a) Explain why Clique Decision Problem is NP-Hard. Explain. [L4][CO5] [05M]
b) Explain why Traveling Salesperson Decision Problem is NP-Hard. Explain. [L3][CO5] [05M]
10 a) Explain Scheduling Identical Processors in NP Hard Scheduling Problem. [L4][CO5] [05M]
b) Describe Job Shop Scheduling in NP Hard Scheduling Problem. [L1][CO5] [05M]

Prepared by CSE and CSIT Department