Unit-1

Part – A

1. Define an algorithm
2. Define Pseudocode
3. List the characteristics of an algorithm
4. Define space complexity
5. Define time complexity
6. List asymptotic notations
7. Define Balance factor in AVL Tree
8. List rebalancing cases in AVL tree
9. List the properties of B-Trees
10. Distinguish multiway tree and B-Trees
11. Define Graph
12. List the graph traversal techniques
13. List the methods to represent a graph
14. When does height data need to be maintained in AVL Tree?
15. What is overflow condition in B-Trees

Part – B

1. Define an algorithm. Explain the characteristics of an algorithm to be satisfied.

2. Explain in detail about Asymptotic notations.
3. Design an algorithm for finding the number of binary digits for a positive decimal
integer and calculate time and space complexity.
4. Design an algorithm that inputs three integers and outputs them in non-decreasing
order. Calculate time and space complexity.
5. Design a recursive algorithm for finding a Fibonacci series and determine the space
complexity and time complexity for the algorithm.
6. Design a recursive algorithm for finding a sum of elements in an array and determine
the space complexity and time complexity for the algorithm.
7. Design an iterative algorithm for finding a Fibonacci series and determine the space
complexity and time complexity for the algorithm.
8. Illustrate the concept of magic square and write an algorithm
9. Analyse and solve the following problem using Depth First Search (DFS).
10. Analyse and solve the following problem using Breadth First Search (BFS).

11. With an example, distinguish between Breadth First Search and Depth First Search
12. Construct AVL tree for the following data 21,26,30,9,4,14,28,18,15,10,2,3,7 and
analyze where rotations are required.
13. Construct an AVL tree by inserting the following elements sequentially: 30, 20, 40,
10, 25, 35, 50. Show all rotations required to maintain balance.
14. Consider the following AVL tree. Find updated AVL tree after insertion of 70?

15. Illustrate the algorithm of insertion operation in AVL Tree

16. Given an AVL tree and N values to be inserted in the tree. Write a function to insert
elements into the given AVL tree.
17. Deleting a node from an AVL tree may cause multiple rotations. Explain with an
example how the deletion process might lead to multiple balancing operations.
18. Compare the AVL tree structures formed by inserting the elements in the order 10, 20,
30, 40, 50, 60, 70, 80, 90, 100 versus 50, 30, 70, 20, 40, 60, 80, 10, 35, 45. Which one
has a more balanced structure?
19. Construct a B-Tree of order 3 by inserting the following keys sequentially: 10, 20, 5,
6, 12, 30, 7, 17. Show the step-by-step process.
20. Perform deletion of 12 from the given B-Tree of order 3, ensuring all B-Tree
properties hold. Show all intermediate steps.
21. Analyze the effects of deleting a non-leaf node versus a leaf node in a B-Tree with
an example. How does deletion maintain the balance of the tree?
22. Define B- Tree. Illustrate the properties of B- Tree
 Unit-2

Part – A

1. Define Divide and Conquer

2. Write control abstraction of Divide and Conquer
3. List the applications of Divide and Conquer
4. Write the time complexity of Merge sort
5. Write the time complexity of Quick Sort
6. Write the time complexity of Strassens Matrix multiplication
7. Define Greedy Method
8. Write control abstraction of Greedy Method
9. List the applications of Greedy Method
10. Define spanning tree
11. Define Minimum spanning tree
12. List the methods to obtain minimum spanning tree

Part- B
1. Apply quick sort algorithm on the following sequence of keys to arrange in ascending
order 33,66,11,55,67,78,24,35,88,99
2. Apply merge sort algorithm on the following sequence of keys to arrange in
ascending order 33,66,11,55,67,78,24,35,88,99
3. Compute the product of the following 4×4 matrices using Strassen’s Algorithm:

4. Multiply the following 4×4 matrices using Strassen’s Algorithm and show all
intermediate steps
 Use the Divide and Conquer approach in Strassen’s Algorithm by splitting each
4×4 matrix into four 2×2 submatrices, compute P1 to P7, and reconstruct the final
matrix.
5. Analyze the differences between general matrix multiplication and Strassen’s matrix
multiplication in terms of algorithmic structure and computational complexity.
6. Analyze the impact of choosing different pivot strategies (first element, last element,
or random) on the performance of Quick Sort for the following elements
12, 7, 14, 9, 10, 11, 6, 2, 8, 1, 0
7. Analyze the merge sort algorithm by outlining its procedure and evaluating its time
complexity across best, average, and worst cases.
8. Analyze the quick sort algorithm by outlining its procedure and evaluating its time
complexity across best, average, and worst cases.
9. Explain the concept of the Greedy Method and describe its control abstraction
10. Given the following jobs with profit and deadlines, find the maximum profit
sequence using the Greedy Algorithm

11. Apply greedy algorithm, solve the following job scheduling problem and find the
optimal scheduling order.

Jobs J1 J2 J3 J4 J5 J6 J7
profits 3 5 20 18 1 6 30
deadlines 1 3 4 3 2 1 2

12. Given a set of jobs with equal deadlines but different profits, analyze how the
Greedy approach affects the solution.
 Compare the results if the deadlines were increased.

13. Apply Greedy Method, find the optimal solution of the Fractional Knapsack instance
n= 7, M=15, (p1, p2, ……p7) = (10,5,15,7,6,18,3) and (w1,w2,. ...w7)=(2,3,5,7,1,4,1)
14. Solve the Fractional Knapsack Problem using the Greedy Approach for the
following items (Capacity = 20): BL3

Find the maximum profit and show the step-by-step selection process.

15. Illustrate Prim’s algorithm and Apply Prim’s algorithm and find minimum spanning
tree

16. Illustrate Krushkal’s algorithm and Apply Krushkal’s algorithm and find minimum
spanning tree

17. With an example, distinguish Prim’s and Kruskal’s Algorithm

18. Construct the Minimum Spanning Tree using Prim’s Algorithm for the following
graph:
Edges: (A-B, 4), (A-C, 3), (B-C, 1), (B-D, 2), (C-D, 5), (C-E, 6), (D-E, 7)
19. Apply Kruskal’s Algorithm to the following graph and find the MST:
Edges: (1-2, 1), (1-3, 4), (2-3, 2), (2-4, 6), (3-4, 3)
20. Given a graph with negative edge weights, analyze why Prim’s Algorithm or
Kruskal’s Algorithm may or may not work correctly.
 Unit-3
Part-A
1. Define dynamic programming
2. Mention the steps involved in dynamic programming
3. Define principle of optimality
4. List the applications of dynamic programming
5. Mention the drawback of Bellman Ford algorithm
6. Distinguish between Fractional Knapsack and 0/1 Knapsack Problem
7. Define travelling salesperson problem
8. Write the recurrence relation of all pair shortest path problem
9. Define 0/1 Knapsack
10. Define single source shortest path problem

Part-B
1. Apply dynamic programming and obtain an optimal solution to 0/1 knapsack problem
with n=3, m=20, (W1, W2, W3) = (2, 3, 4), (P1, P2, P3) = (1, 2, 5) and M = 6.
2. Compare dynamic programming with greedy method.
3. Explain Principle of optimality and how it is working in different problems which can
be solved by dynamic programming technique.
4. Given a weighted digraph G = (V, E) with weight. Determine the length of the
shortest path between all pairs of vertices in G. Here we assume that there are no
cycles with zero or negative cost.

5. Consider the following directed weighted graph G = {V, E}. Find the shortest paths
between all the vertices of the graphs using the Floyd-Warshall algorithm.

6. Explain how the Floyd-Warshall algorithm uses dynamic programming to solve the
all-pairs shortest path problem.
7. Illustrate working principle of Bellman Ford's algorithm and write the algorithm
 8. Apply Bellman Ford’s Algorithm

9. Why do we need to be careful with negative weights, explain with an example.

10. Write an algorithm of Bellman Ford's algorithm

11. Analyze the behavior of the Bellman-Ford algorithm in detecting negative weight
cycles. Suppose the algorithm has completed all |V| - 1 iterations. What does it mean
if any edge still offers a shorter path in a subsequent iteration? How does this help in
cycle detection? Support your answer with an example.

12. Consider the knapsack instance n = 3, (w1, w2, w3) = (2, 3, 4), (P1, P2, P3) = (1, 2,
5) and M = 6. Apply dynamic programming and find the solution

13. Let us consider that the capacity of the knapsack is W = 8 and the items are as shown in
the following table. Apply dynamic programming and find the solution

Item A B C D

Profit 2 4 7 10

Weigh
1 3 5 7
t

13. A thief enters a house for robbing it. He can carry a maximal weight of 5 kg into his
bag. There are 4 items in the house with the following weights and values. What items
should thief take if he either takes the item completely or leaves it completely?

Item Weight(kg) Value ($)

Mirror 2 3

Silver nugget 3 4

Painting 4 5

Vase 5 6
14. With an example, explain how dynamic programming is applied to solve 0/1
Knapsack Problem
15. Apply dynamic programming, for the following graph find minimum cost tour for the
traveling salesperson problem:

16. Find the travelling salesman tour for the below graph using dynamic programming.
(10M)

17. Given a distance matrix for 4 cities as shown below, use dynamic programming and
find minimum cost tour for the traveling salesperson problem:

18. Find the travelling salesman tour for the below graph using dynamic programming
 Unit-4
Part-A
1. Define backtracking
2. List the applications of backtracking
3. Define E-Node
4. Define live node
5. Define State space tree
6. Define implicit constraints
7. Define explicit constraints
8. Define bounding function
9. Define Branch and Bound
10. List the applications of BRANCH AND Bound
11. Compare Backtracking and Branch and Bound

Part-B
1. Explain how the backtracking algorithm solves the N-Queens problem.
2. Write N- Queens algorithm using backtracking
3. Suppose we start with the feasible sequence 7, 5, 3, 1
i. Complete the solution by placing the remaining 4 queens on the board
ii. List the full column sequence that represents a valid solution.
iii. Show or briefly describe the reasoning or checks used to ensure the placement
is valid.
4. Give the statement of sum of subsets problem. Apply backtracking and find all sum of
subsets for n=4, s={11,13,24,7} and Sum=31.Draw the portion of the state space tree.
5. Given a set of positive integers: S = {10, 7, 5, 18, 12, 20, 15} and a target sum = 35.
Apply backtracking and find all sum of subsets.
6. Write recursive backtracking algorithm for sum of subsets
7. Apply Backtracking algorithm, color the below given graph with 3 colors.

8. Explain the Graph – coloring problem. And draw the state space tree for m= 3 colors,
n=4 vertices graph using Backtracking.
9. Define Graph Coloring. Write a recursive backtracking algorithm for graph coloring
10. Discuss Draw the portion of state space tree generated by LCBB for the following
instance of 0/1 knapsack n= 5, M=12, (p1, ……p5) = (10,15,6,8,4)
(w1,. ...w5)=(4,6,3,4,2).
11. Explain N-queen problem and Draw the state-space tree along with answer nodes for
4-queens problem.
12. Apply Branch and Bound algorithm for the Travelling Salesman Problem given
below.

13. Solve the following instance of travelling sales person problem using Least Cost
Branch Bound.

14. Apply Branch and Bound algorithm to solve the Travelling Salesman problem for

15. Explain about LC Search. Write control abstraction of LC Search.

16. Draw the portion of the state space tree generated by LC branch and bound for n=4,
(P1, P2, P3, P4) = (10,10,12,18), (W1, W2, W3, W4) = (2, 4, 6,9), and m = 15.
17. Draw the portion of the state space tree generated by FIFO branch and bound for n=4,
(P1, P2, P3, P4)= (10,10,12,18), (W1, W2, W3, W4) = (2, 4, 6,9), and m = 15.
18. Draw the portion of the state space tree generated by LC branch and bound for the
following knapsack instances: n = 5, (P 1, P2, P3, P4) = (10,15,6, 8, 4), (W1, W2, W3,
W4) =(4, 6, 3, 4, 2) and m = 12.
 UNIT-5

Part-A

1. Define deterministic algorithm

2. Define non deterministic algorithm
3. Define Class P problem
4. Define Class NP problem
5. Define NP-hard problem
6. Define NP-complete problem
7. Define chromatic number
8. List NP-hard problems
9. State Cooks theorem
10. Draw the relationship among P, NP, NP-hard and NP-complete problem

Part-B

1. Write and explain the Cooks theorem.

2. Explain Class NP-Hard? Differentiate between NP-Hard & NP-Complete algorithms?
3. Discuss in detail about the class P, NP, NP-hard and NP-complete problems. Give
examples for each class.
4. Explain the following with examples
i. Class P Problems
ii. Class NP Problems
iii. NP complete problem
iv. NP hard problem.
v. Deterministic algorithm.
5. Illustrate deterministic algorithm with an example
6. Illustrate non-deterministic algorithm with an example
7. Distinguish Deterministic algorithm and non-deterministic algorithm
8. Explain the difference between the complexity classes P and NP
9. Illustrate the Clique Decision Problem with an example graph.
10. Illustrate the Chromatic Number Decision Problem using a simple graph example
11. Illustrate Scheduling Identical Processors with an example
12. Illustrate job Shop Scheduling with an example