**Analysis Design of Algorithm**

**Question Bank-Solution with explanation**

**Contains most asked questions from previous years examinations (ADA).**

Q1. Explain multistage graph problem with example?

Ans. Click Here.

Q2. What is the optimal Huffman code for the following set of frequencies numbers-

a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21

Ans. Click Here.

Q3. Solve the TSP using Branch and Bound Techniques.

Ans. Click Here.

Q4. Obtain a setoff optimal Huffman codes for the seven messages (M1……M7) with relative frequencies (q1…..q7)=(4, 5, 7, 8, 10, 22, 15). Draw the decode tree for this set of codes.

Ans. Click Here.

Q5. Find an optimal merge pattern for 11 files whose length are 28, 32, 12, 5, 84, 5, 3, 9, 35, 3, 11.

Ans. Click Here.

Q6. Sort the given list using Merge sort- 70, 80, 40, 50, 60, 12, 35, 95, 10.

Ans. Click Here.

Q7. Explain Strassen’s matrix multiplication algorithm with example

Ans. Click Here.

Q8. Find shortest path using Dijkstra’s algorithm.

Ans. Click Here.

Q9. Sort the following list using Quick Sort- 10, 5, 13, 4, 15, 11, 6, 12.

Ans. Click Here.

Q10. Use Binary Search Tree to find location of 45 in the given array-9,12,15,24,30,36,45,70.

Ans. Click Here.

Q11. Apply Kruskal’s algorithm to find the minimum spanning tree of the graph

Ans. Click Here.

Q12. What is minimum spanning tree? Using Prim’s algorithm find minimum spanning tree of the following graph?

Ans. Click Here.

Q13, Define minimum spanning tree. What is Prim’s algorithm. Using this algorithm find MST of the following graph.

Ans. Click Here.

Q14. Color the following graph using a vertex coloring algorithm. What is the minimum number of colour required?

Ans. Click Here.

Q15. Create a B-Tree of order 5 from the following list of data items: 30, 20, 35, 95, 15, 60. 55, 25, 5, 65, 70, 10, 40, 50, 80, 45.

Ans. Click Here.

Q16. A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of.

Ans. Click Here.

Q17. Find an optimal solution to the Knapsack instance n=3, m=20, (p1,p2,p3)=(25,24,15) and (w1,w2,w3)=(18,15,10).

Ans. Click Here.

Q18. Show Preorder, Inorder and Postorder for the following tree.

Ans. Click Here.

Q19. Tabulate the difference between Kruskal’s and Prim’s algorithm?

Ans. Click Here.

Q20. Use the Floyd-Warshall algorithm and find shortest path between all pairs of vertices for the graph?

Ans. Click Here.

Q21. Define Dynamic Programming?

Ans. Click Here.

Q22. In what way AVL is better than a Binary tree? Insert these keys in to an AVL tree.

342, 206, 444, 523, 607, 301, 142, 183, 102, 157, 149.

Ans. Click Here.

Q23. Sort the following array using Heap sort?

66, 33, 40, 20, 50, 88, 60, 11, 77, 30, 45, 65.

Ans. Click Here.

Q24. Define Algorithm? Discuss how to analyse Algorithm?

Ans. Click Here.

Q25. What is the running time of Quick Sort Algorithm when all elements of array A have the same value?

Ans. Click Here.

Q26. Sort the following numbers using Merge Sort?

4, 9, 7, 2, 10, 5, 12, 14

Ans. Click Here.

Q27. What do you mean by Algorithm?

Ans. Click here.

Q28. Find an optimal solution to the Knapsack instance (Fraction Method)

n=3, m=21, (p1, p2, p3)=(25, 24, 15) and (w1, w2, w3)=(18, 15, 10).

Ans. Click Here.

Q29. Find an optimal solution to the Knapsack instance (Fraction Method)

n=3, m=21, (p1, p2, p3)=(1, 2, 5) and (w1, w2, w3)=(2, 3, 4).

Ans. Click Here.

Q30. Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph.

Ans. Click Here.

Q31. Find an optimal solution to the Knapsack instance (Set Method)

n=4, m=30, (p1, p2, p3, p4)=(2, 5, 8, 1) and (w1, w2, w3, w4)=(10, 15, 6, 9).

Ans. Click Here.

Q32. Find an optimal solution to the Knapsack instance (Tabular Method)

n=4, m=6, (p1, p2, p3, p4)=(4, 5, 6, 7) and (w1, w2, w3, w4)=(3, 4, 5, 6).

Ans. Click Here.

Q33. Define Optimal Merge Pattern with the help of an example?

Ans. Click Here.

Q34. What is minimum spanning tree? Using Prim’s algorithm find minimum spanning tree of the following graph.

Ans. Click Here.

Q35. What is minimum spanning tree? Using Kruskal’s algorithm find minimum spanning tree of the following graph.

Ans. Click Here.

Q36. Obtain a set of optimal Huffman codes for the seven messages. (m1…..m7) with relative frequencies (f1…….f7)=(4, 6, 8, 9, 11, 13, 19). Draw the decode tree for this set of codes.

Ans. Click Here.

Q37. Define Job Sequencing with Deadlines with the help of an example?

Ans. Click Here.

Q38. Describe Heap, Max Heap and Min Heap with the help of an example?

Ans. Click Here.

Q39. What is Divide and Conquer strategy? Write and explain the algorithm of divide and conquer.

Ans. Click Here.

Q40. What Binary search tree? Explain with the help of an example?

Ans. Click Here.

Q41. Sort the following numbers using Quick sort?

26, 5, 37, 1, 61, 11, 59, 15, 48, 19.

Ans. Click Here.

Q42. What is Algorithm Time Complexity?

Ans. Click Here.

Q43. What is Algorithm Space Complexity?

Ans. Click Here.