• Attempt any five questions.
• All questions carry equal marks.
Give the asymptotic bounds for f(n)=2n²-4n+20 and represent in θ notation.
Define Quicksort? Sort elements 22,12,30,46,28,14,8,10,56,18,3 using Merge sort.
Write an algorithm to find matrix multiplication using Strassen's method.
Construct Huffman coding for the given character frequencies and write applications.
Solve job sequencing with deadlines using Greedy: n=5, P=(5,20,10,15,1), d=(3,2,1,2,3).
Solve 0/1 Knapsack using DP: n=4, m=40, W=(2,11,22,15), P=(11,21,31,33).
Construct a multistage graph for the given graph using the Greedy method.
Explain the Floyd Warshall algorithm for the given graph.
Explain in detail about the FIFO branch and bound.
Write an algorithm for the 8-queens problem using backtracking.
Draw the state space tree for 'm' coloring when n=3 and m=3.
Use OBST to compute w(i,j), r(i,j), c(i,j) for identifier set (double,int,for,if) and construct optimal BST.
Explain in detail Height balanced tree with an example.
Write short notes on any two: a) Binary search algorithm and its time complexity b) Single source shortest path c) Hamiltonian graph and cycle d) Breadth First Search.
