MADANAPALLE INSTITUTE OF TECHNOLOGY & SCIENCE
(UGC-AUTONOMOUS INSTITUTION)
Affiliated to JNTUA, Ananthapuramu & Approved by AICTE, NewDelhi
NBA Accredited - [Link]. (CIVIL, CSE, ECE, EEE, MECH), MBA & MCA
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING (CYBER SECURITY)
23CSC101 Advanced Data Structures and Algorithm Analysis
QUESTION BANK
UNIT-1
Part-A(1 marks)
1. What is Algorithm Analysis? Write down the importance of Algorithm Analysis.
2. What is Time Complexity & Space Complexity?
3. What is B Trees? Write down the Characteristics.
4. Difference between Time Complexity & Space Complexity
5. List various Asymptotic Notations.
6. Define Graph and write its applications.
7. Define algorithm.
8. Define asymptotic analysis and specify its types
9. Differentiate between Big-oh and omega notation.
10. Write properties of B-Tree.
11. Differentiate between BFS and DFS.
12. What is AVL tree? Why AVL tree?
13. List various rotations in AVL tree
14. Write Pseudocode for AVL tree rotations
15. List various cases in deletion operation of B-Tree
Part B
1. Construct an AVL tree for a given set of elements {13, 10, 15, 5, 11, 16, 4, and 6}. Insert
14 and analyze the time complexity.
2. Explain DFS traversal with example and analyze its time complexity.
3. What is AVL tree and specify its rotations. Apply rotations and construct an AVL tree
for a given set of elements 14,17,11,7,53,4,13,12,8,60,19,16,20.
4. What is Graph Traversal and Explain BFS traversal with example and analyze its time
complexity.
5. Explain in detail about AVL Trees – Creation, Insertion, Deletion Operations and
Applications with example.
6. Construct an B tree for a given set of elements {1,12,8,2,25,6,14,28,17,7,52,16,48,68}
with the order of 5
7. Construct AVL tree with example and perform delete operation with analyzing various
cases.
8. What is Graphs –? Explain in details about its Traversals.
9. Construct a B-Tree of order 5 with a set of 20 random elements stored in an array.
Perform search and delete operations.
10. Discuss about Asymptotic Notations
11. Differentiate between BFS and DFS.
UNIT-2
Part-A (1 marks)
1. Define Divide & Conquer Algorithm. Write down the Characteristics of Divide and Conquer
Algorithm.
2. What is spanning tree. List methods used for calculating MST.
3. Difference between the Greedy Algorithm and the Divide and Conquer Algorithm.
4. Write Pseudocode for Merge Sort and specify its Time complexity
5. Write algorithm for Knapsack problem.
6. What is a Greedy algorithm? Write down the Advantages.
7. Write Pseudocode for Quick Sort and specify its Time complexity
8. State single source shortest path algorithm.
9. State efficiency of prim’s algorithm.
10. Define feasible solution w.r.t greedy knapsack problem.
11. Define the terms feasible solution, optimal solution.
12. Differentiate 0/1 knapsack problem and fractional knapsack problem.
13. Specify properties of minimum cost spanning tree
14. Write algorithm steps for job sequencing using deadline
15. Write algorithm steps for knapsack problem
Part B
1. What is Merge sort? Write Pseudocode for Merge sort and apply for given set of elements
12, 31, 25,8,32,17,40,42.
2. What is Greedy Method? Explain in details Knapsack Problem for Capacity=100kg,
weights{10,20,30,40,50} and profit{20,30,66,40,60)
3. Find the optimal solution for the fractional knapsack problem making use of greedy
approach. Consider-
n=5 w = 60 kg
(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)
(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)
4. Specify Minimum cost spanning trees properties and Explain Kruskal’s algorithm with
example.
5. Solve the quick sort problem for a given set of elements {5, 3, 1, 9, 8, 2, 4, and 7}.
6. Explain Single source shortest paths using Dijkstra’s algorithm
7. Define Quick Sort. Explain with example and write down the application, advantage and
disadvantage.
8. Consider the following matix and find the shortest path distance between every pair of
vertices Using Floyd Warshall Algorithm.
9. Given the jobs, their deadlines and associated profits as shown-
Jobs J1 J2 J3 J4 J5 J6
Deadlines 5 3 3 2 4 2
Profits 200 180 190 300 120 100
Answer the following questions-
Write the optimal schedule that gives maximum profit.
Are all the jobs completed in the optimal schedule?
What is the maximum earned profit?
10. Specify Minimum cost spanning trees properties and Explain Prim’s algorithm with
example.
UNIT III
1. Define Dynamic programming.
2. What is the Purpose of the Floyd Warshall algorithm?
3. What is the difference between dynamic programming with divide and conquer method?
4. What is the Purpose of the Bellman-Ford algorithm?
5. State Principle of Relaxation of Edges for Bellman-Ford.
6. Define Optimal Binary Search Tree (OBST).
7. Write algorithm steps for 0/1 knapsack problem using dynamic programming.
8. List applications of dynamic programming.
9. What is Travelling Salesman Problem w.r.t Dynamic programming
10. Write formula for cost table,C[i,j] in Optimal Binary Search Tree.
Part B
1. a) Explain the methodology of Dynamic programming. Mention the applications of Dynamic
programming.
(b) Solve the following instance of 0/1 KNAPSACK problem using Dynamic programming n =
3, (W1, W2, W3) = (2, 3, 4), (P1, P2, P3) = (1, 2, 5), and m = 6.
2. Describe Travelling salesperson problem and find the travelling salesman tour for the below
graph and matrix using dynamic programming.
3. Apply 0/1 Knapsack problem using Dynamic programming for n = 4, (W1, W2, W3,W4) =
(3, 4,6,5), (P1, P2, P3,P4) = (2, 3,1,4), and M=8.
4. What is single-source shortest path algorithm? Solve the following graph using Bellman Ford
Algorithm to calculate shortest [Link] its time complexity.
5. Find the shortest path distance between every pair of vertices Using Floyd Warshall Algorithm.
6. Construct Optimal Binary Search Tree (OBST).
Key: A B C D
Probability: 0.1 0.2 0.4 0.3
7. Explain Optimal Binary Search Tree (OBST ) with an example
8. Explain Bellman Ford Algorithm with example
9. Explain how solution will be provided for single source shortest path problem using dynamic
programming with an example.
10. Use dynamic programming Technique to solve Travelling salesperson problem and find the
travelling salesman tour for the below graph.
UNIT-IV
1. Define n-queens problem
2. Define branch and bound method
3. What is meant by feasible solution?
4. Write any two characteristics of Greedy Algorithm?
5. Define optimal solution?
6. Write various constraints used in 8-queens problem.
7. How many combinations are possible to place 8 queens in 8x8 chess board?
8. What is State-Space Tree?
9. What is Sum of Subset problem?
10. Define Graph Coloring?
11. What is Chromatic Number?
12. What is Travelling Salesman Problem w.r.t Branch and Bound method.
Part B
1. Analyze Sum of Subset Problem and Find all possible subset of m and Generate State
Space Tree for W={3,5,6,7} and m=15.
2. Solve 0/1 Knapsack problem using Branch and Bound for following example with
capacity, M = 10.
3. Explain N-queen problem and Draw the state-space tree along with answer nodes for 4-
queens problem.
4. Consider the sum-of-subset problem, n = 4, Sum = 13, and w1 = 3, w2 = 4, w3 = 5 and
w4 = 6. Find a solution to the problem using backtracking. Show the state-space tree
leading to the solution.
5. Color the below given graph with 3 colors using Backtracking algorithm
6. What do you understand by backtracking? Explain the N-Queens problem with the help
of suitable example.
7. Apply Branch and Bound algorithm to solve the Travelling Salesman problem for
8. What do you understand by backtracking? Explain the N-Queens problem with the help
of suitable example.
9. Explain the Graph – coloring problem. And draw the state space tree for m= 3 colors,
n=4 vertices graph using Backtracking.
10. Apply Branch and Bound algorithm for the Travelling Salesman Problem given below.
UNIT V
1. How NP-hard problems are different from NP-Complete?
2. Define Cook’s theorem
3. List NP-Hard Graph Problems
4. Define Clique decision problem
5. Define Chromatic Number Decision Problem
6. Define NP hard problems
7. Define NP complete problems
8. Define assignment problem
9. What is meant by Scheduling Identical Processors
10. What is Job Shop Scheduling?
Part B
1. Discuss in detail about the class P, NP, NP-hard and NP-complete problems. Give
examples for each class.
2. Explain Clique Decision Problem (CDP) with example
3. Explain Class NP-Hard? Differentiate between NP-Hard & NP-Complete algorithms?
4. Explain NP-Hard Graph Problems with example