AI/AL/CD-402 (GS) – Analysis and Design of Algorithm

B.Tech. IV Semester
Examination, June 2024
Grading System (GS)
Max Marks: 70 | Time: 3 Hours

Note:
i) Attempt any five questions.
ii) All questions carry equal marks.

Previous Year Questions (June 2024)

Q.1

a) Define Time Complexity. Describe different notations used to represent these complexities. (Unit 1)

b) Write an algorithm for Strassen's matrix multiplication and analyze the complexity of algorithm. (Unit 1)
Q.2

a) Show that the average case time complexity of quick sort is O(nlogn). (Unit 1)

b) Describe in detail job sequencing with deadlines problem. Let $n=4, (P_{1}, P_{2}, P_{3}, P_{4}) = (100, 10, 15, 27)$ and $(d_{1}, d_{2}, d_{3}, d_{4}) = (2, 1, 2, 1)$ find the optimal solution for the given values. (Unit 2)
Q.3

a) Write an algorithm for single source shortest path and apply it for the following graph.

An undirected weighted graph with 6 vertices labeled A, B, C, D, E, and F. The edges and their corresponding weights are: Edge A to B with weight 10; Edge A to D with weight 30; Edge A to E with weight 45; Edge B to C with weight 50; Edge B to E with weight 40; Edge B to F with weight 25; Edge C to E with weight 35; Edge C to F with weight 15; Edge D to F with weight 20; and Edge E to F with weight 55.

(Unit 2)

b) Discuss the importance of proving both the greedy choice property and the optimal substructure property for establishing the correctness of a greedy algorithm. (Unit 2)
Q.4

a) Explain Floyd Warshall algorithm problem with the graph given in figure.

An undirected weighted graph with 9 vertices labeled 0 through 8. The edges and their corresponding weights are as follows: Edge 0 to 1 with weight 4; Edge 0 to 7 with weight 8; Edge 1 to 2 with weight 8; Edge 1 to 7 with weight 11; Edge 2 to 3 with weight 7; Edge 2 to 5 with weight 4; Edge 2 to 8 with weight 2; Edge 3 to 4 with weight 9; Edge 3 to 5 with weight 14; Edge 4 to 5 with weight 10; Edge 5 to 6 with weight 2; Edge 6 to 7 with weight 1; Edge 6 to 8 with weight 6; and Edge 7 to 8 with weight 7.

(Unit 3)

b) What are B-trees? How are they created? Explain with a suitable example. (Unit 5)
Q.5

a) Describe how dynamic programming can be used to solve reliability design problems. (Unit 3)

b) Describe graph coloring problem and write an algorithm for m-coloring problem. (Unit 4)
Q.6

a) Explain the 4-queen problem using backtracking algorithm. (Unit 4)

b) Explain the method of reduction to solve travelling sales person problem using branch and bound. (Unit 4)
Q.7

a) Compare and contrast NP-Hard and NP-Complete classes (Unit 5)

b) Write an algorithm to solve Knapsack problem using Greedy technique. Find the optimal solution to the Knapsack instance $n=7$, $m=15$, $(P_{1}, P_{2}, P_{3}...P_{7}) = (10, 5, 15, 7, 6, 18, 3)$, $(W_{1}, W_{2}, W_{3}...W_{7}) = (2, 3, 5, 7, 1, 4, 1)$. (Unit 2)
Q.8

Write short notes on any two of the following:

a) Data Stream Algorithms (Unit 5)

b) Approximations Algorithms (Unit 5)

c) Data Transfer Optimization (Unit 1)

d) Huffman coding (Unit 2)