Analysis Design of Algorithm
Question Bank-Solution with explanation

Q1. Explain multistage graph problem with example?

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

Q3. Solve the TSP using Branch and Bound Techniques.

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.

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

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

Q7. Explain Strassen’s matrix multiplication algorithm with example

Q8. Find shortest path using Dijkstra’s algorithm.

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

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

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

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

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

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

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.

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.

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).

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

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

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

Q21. Define Dynamic Programming?

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.

Q23. Sort the following array using Heap sort?
66, 33, 40, 20, 50, 88, 60, 11, 77, 30, 45, 65.

Q24. Define Algorithm? Discuss how to analyse Algorithm?

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

Q26. Sort the following numbers using Merge Sort?
4, 9, 7, 2, 10, 5, 12, 14

Q27. What do you mean by Algorithm?

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).

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).

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

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).

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).

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

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

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

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.

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

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

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

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

Q41. Sort the following numbers using Quick sort?
26, 5, 37, 1, 61, 11, 59, 15, 48, 19.

Q42.  What is Algorithm Time Complexity?

Q43. What is Algorithm Space Complexity?