• Attempt any five questions.
• All questions carry equal marks.
Solve T(n)=1 for n≤4, T(n)=2T(√n)+log n for n>4 using substitution method.
The worst case of merge sort is O(n log n). What is its best case? Can we say merge sort is O(n log n)?
Obtain optimal Huffman codes for messages with frequencies (4,5,7,8,10,12,20). Draw the decode tree.
Use shortest paths algorithm to obtain lengths from vertex 1 to all remaining vertices in the given di-graph.
Give an example of knapsack instances for which |Sⁱ|=2ⁱ, 0≤i≤n, with one instance for each n.
Explain Floyd Warshall algorithm with suitable example.
Given an n×n chessboard, present an algorithm for Knight's tour problem to visit all squares exactly once.
Consider the traveling salesperson instance defined by the given 5×5 cost matrix.
Show that DFS visits all vertices in G reachable from V.
Obtain a nondeterministic algorithm of O(n) to determine if a subset of n numbers sums to m.
Write an algorithm to delete element x from a BST. What is the time complexity?
What do you mean by balance factor in AVL tree? Give example to balance an AVL tree.
Write an algorithm for n jobs on k parallel processors to minimize finish time.
Find optimal solution for 0/1 knapsack: W=(10,15,6,9), P=(2,5,8,1), M=30.
Write short notes on (any two): a) B-Trees b) Tree Traversal c) Reliability Design.
