• Attempt any five questions.
• All questions carry equal marks.
Obtain asymptotic bound using substitution method for T(n)=3T(n/3)+n and represent in θ notation.
What is Merge sort? Sort the elements 20,30,15,11,35,19,12,11,55 using Merge sort.
Discuss Strassen's matrix multiplication and Classical O(n³) methods. When does Strassen's outperform?
Define spanning tree? Construct a minimal spanning tree for the given graph using Prim's algorithm.
Solve job sequencing with deadlines using Greedy: n=4, P=(100,10,15,27), d=(2,1,2,1).
Apply greedy method to solve 0/1 Knapsack: n=3, m=20, W=(18,15,10), P=(25,24,15).
Construct a multistage graph for the given graph using the greedy method.
Explain the Floyd Warshall algorithm for the given graph.
Using branch and bound technique explain the 0/1 knapsack problem.
Give the solution to the 8-queens problem using backtracking.
What is graph coloring? Explain graph coloring for the given graph.
Use OBST to compute w(i,j), r(i,j), c(i,j) for identifier set (char,float,while,else) with given probabilities and construct optimal BST.
Explain in detail about 2-3 Trees with an example.
Write short notes on any two: a) Binary search algorithm and its time complexity b) Single source shortest path c) Parallel algorithms d) NP Completeness.
