VASIREDDY VENKATADRI INSTITUTE OF TECHNOLOGY

(AUTONOMOUS)
YEAR/SEM: II – B.Tech. - I-Sem NAME OF THE EXAM: MID – I
SUBJECT: Advanced Data Structures and Algorithm Analysis
BRANCH: Common to All CSE & CSE Allied Branches DATE: 05-10-2024
Note: Answer ONE question from each unit
Time: 90 Minutes SET-01 Max. Marks: 30
CO BL PO M
UNIT-I
f(n)=O(g(n)), f(n)=Ω(g(n)) and f(n)=Θ(g(n)), illustrate these relations
a 1 2 1 6
in estimating the time complexities with suitable examples.
What is an Algorithm? How many ways to represent an Algorithm?
b 1 1 1 6
List out the characteristics of an algorithm.
1
OR
Describe in detail about Height Balanced Tree. Describe the
c algorithms used to perform single and double rotation on AVL tree 1 2 2 12
with suitable example each.
UNIT-II
What is a Graph? Illustrate the different memory representations with
a 2 1 1 7
an example each.
Explain the importance Strassen’s Matrix Muplication? Multiply the
matrices by using Strassen’s Matrix Multiplication.
b 2 2 2 5

OR
What is Bi-Connected Graph? List out the Bi-Connected
Components in a given graph in step wise with the help of an
2 algorithm.

c 2 2 2 7

What is graph Traversal? Give an Algorithm for types of

d 2 1 1 5
traversals with the help of suitable example each
UNIT-III
Find shortest path for the following graph from “P” using Dijkstra’s
algorithm?(Single Source Shortest Path)

a 3 4 2 6
3

OR
b Explain control abstraction (General Method) of greedy strategy. 3 1 1 6
 VASIREDDY VENKATADRI INSTITUTE OF TECHNOLOGY
(AUTONOMOUS)
YEAR/SEM: II – B.Tech. - I-Sem NAME OF THE EXAM: MID – II
SUBJECT: Advanced Data Structures and Algorithm Analysis
BRANCH: Common to All CSE Allied Branches DATE: 05-10-2024

Note: Answer ONE question from each unit

Time: 90 Minutes SET-02 Max. Marks: 30
CO BL PO M
UNIT-I
List out the characteristics of an Algorithm? f(n)=O(g(n)),
a f(n)=Ω(g(n)) and f(n)=Θ(g(n)), illustrate these relations in estimating 1 2 1 8
the time complexities with suitable examples.
Describe the differences between AVL Tree and Binary Search
b 1 1 1 4
1 Tree.
OR
What is B-Tree? How it differs from an AVL Tree? Construct B-Tree
c with order 4 tree by using the following sequence of numbers 1 4 2 12
6, 7, 9, 22, 13, 31, 35, 28, 24, 5, 34, 8, 25, 10, 11, 12, 14 and 39.
UNIT-II
Analyze the Time complexity of External sorting Technique in all
a 2 4 2 6
Three cases.
What is Heap Tree? List out the application of Heap Tree.
b Construct the min and max heap with the following elements20, 10, 5, 2 4 2 6
18, 6, 12, 14, 4, and 22.
OR
What is Graph? Illustrate the different memory representations for
the given graph. Identify which data structure is suitable for
representing the following diagram and explain which techniques are
2 used to represent memory
c 2 2 4 6

How Strassen’s Matrix Multiplication is different from Matrix

d Multiplication? Discuss in detail. Derive the time complexity of 2 1 1 6
Strassen’s Matrix Muplication Approach.
Design a linear time algorithm for solving the single source shortest
a 3 5 1 6
path algorithm for connected graph.
3 OR
b Write about General Method of Greedy Approach? 3 1 1 6
 VASIREDDY VENKATADRI INSTITUTE OF TECHNOLOGY
(AUTONOMOUS)
YEAR/SEM: II – B.Tech. - I-Sem NAME OF THE EXAM: MID – I
SUBJECT: Advanced Data Structures and Algorithm Analysis
BRANCH: Common to All CSE & CSE Allied Branches DATE: 05-10-2024
Note: Answer ONE question from each unit

Time: 90 Minutes SET-03 Max. Marks: 30

CO BL PO M
UNIT-I
What is Asymptotic Notation? Discuss various asymptotic notations
a 1 1 1 8
used to represent complexity of algorithms with examples?
b Describe the differences between AVL Tree and B-Tree. 1 1 1 4
1 OR
Describe in detail about Height Balanced Tree. Describe the
c algorithms used to perform single and double rotation on AVL tree 1 5 2 12
with suitable example each.
UNIT-II
Do the following operations of Heap Tree?
a. Construct the min and max heap with the following
elements20, 10, 5, 18, 6, 12, 14, 4, and 22. – 6m
a b. Insert 2 in the Min Heap. – 2m 2 5 1 12
c. Insert 28 in the Max Heap. – 2m
d. Perform two successive deletion operations on Max
2 Heap. 2m
OR
Derive the Time Complexity of Quick Sort in Big O Notation
b 2 1 1 8
in Worst Case and Average Case
How Strassen’s Matrix Multiplication is different from Matrix
c 2 1 1 4
Multiplication? Discuss in detail.
UNIT-III
a Discuss in detail about General Method of Greedy Approach? 6
OR
Using shortest path algorithm, obtain in non-decreasing order the
lengths of shortest path from node 1 to all the remaining nodes given
the following digraph.

3
b 2 2 1 6
 VASIREDDY VENKATADRI INSTITUTE OF TECHNOLOGY
(AUTONOMOUS)
YEAR/SEM: II – B.Tech. - I-Sem NAME OF THE EXAM: Mid-I (Open Book)
SUBJECT: Advanced Data Structures and Algorithm Analysis
BRANCH: Common to All CSE & CSE Allied Branches DATE: 05-10-2024
ANSWER ALL QUESTIONS
Time: 50 Minutes SET-01 Max. Marks: 20
Instructions to the students:
1. You can use only 3 printed text books from the books prescribed or recommended to you in the syllabus.
2. You are not authorized to share your resources with other students during the examination.
3. Do not reproduce or copy verbatim from your resources.
4. Mention the resources you have used for preparing your answer.

CO BL PO M
What is B-Tree? What are the cases you consider when deleting a node from
B-Tree. Construct B-Tree After deletion of node 0100 from the following B-
Tree with order 5.

1 1 1 1 8

Mention some methods for choosing the pivot element in quick sort? What
are the three cases that arise during the left to right scan in quick sort? Sort 2 5 3
2 8
the following list by using Quick Sort
39, 9, 81, 45, 90, 27, 72, 18
A thief enters a house for robbing. He can carry a maximum of weight of 60Kg.
There are 5 items in the house with the following weights and values.
ITEM WEIGHT VALUE/PROFIT
1 5 30
2 10 40
3 15 45
3 2 5 3 4
4 22 77
5 25 90
Find the optimal Solution for
1. Maximum Profit
2. Minimum Weight
3. Maximum Profit per unit weight
 VASIREDDY VENKATADRI INSTITUTE OF TECHNOLOGY
(AUTONOMOUS)
YEAR/SEM: II – B.Tech. - I-Sem NAME OF THE EXAM: Mid-I (Open Book)
SUBJECT: Advanced Data Structures and Algorithm Analysis
BRANCH: Common to All CSE & CSE Allied Branches DATE: 05-10-2024
ANSWER ALL QUESTIONS
Time: 50 Minutes SET-02 Max. Marks: 20
Instructions to the students:
1. You can use only 3 printed text books from the books prescribed or recommended to you in the syllabus.
2. You are not authorized to share your resources with other students during the examination.
3. Do not reproduce or copy verbatim from your resources.
4. Mention the resources you have used for preparing your answer.
CO BL PO M
Create an AVL Tree using the following data entered as a sequence set. Show
1 the balance factors in the resulting tree: 1 1 1 8
13, 22, 6, 9, 32, 55, 79, 65, 70,52,20,5
Consider the following graph. Assume we always choose the letter closest to
the beginning of the alphabet first. Discuss in detail generation of DFS Tree
for the given graph i.e. in what order will the nodes be visited using a Depth
First Search?

2 2 5 3 8

A thief enters a house for robbing. He can carry a maximum of weight of 20Kg.
There are 3 items in the house with the following weights and values.
ITEM WEIGHT VALUE/PROFIT
1 18 25
2 15 24
3 2 5 3 4
3 10 15
Find the optimal Solution for
1. Maximum Profit
2. Minimum Weight
3. Maximum Profit per unit weight