Ques 1.

Define asymptotic analysis and explain the three notations which are primarily used for asymptotic analysis with the help of example.

Ques 2.

Define Tower of Hanoi problem as a recurrence relation problem and solve it through a recurrence tree.

Ques 3.

What is Master Method? Write all the three cases of Master Method to solve the following recurrence relation: (5) T(n) = _aT (n/b) + f(n) and explain. 

Ques 4.

Find the optimal solution to the fractional Knapsack problem using Greedy technique: 
 Number of objects n: 6
Maximum Weight M = 25
Value of each item:
(

Ques 5.

Write a pseudocode of evaluating polynomial expression using Horner’s rule and perform complexity analysis (step by step). Apply it to evaluation the polynomial expression: (10) P(x) = 3x⁶+4x⁵+2x4+2x³+8x+9

Ques 6.

Write pseudocode for left to right binary exponentiation evaluation. Apply the algorithm `for evaluating a280 and show a step by step result.

Ques 7.

Write Kruskal’s algorithm for finding minimum cost spanning tree using greedy approach and apply to the following graph and show step by step results.

Ques 8.

Write Kruskal’s algorithm for finding minimum cost spanning tree using greedy approach and apply to the following graph and show step by step results

Ques 9.

What is edge relaxation technique in shortest path algorithm? Write and apply Bellman Ford’s algorithm to find the shortest path from a node A to all the remaining nodes in the following graph:

Ques 10.

Write Quick Sort algorithm to sort the following list of integer numbers. Show all the intermediate
steps
 15, 12, 18, 5, 6, 8, 22, 3, 25, 30, 35, 8, 32
Also compute the worst case time complexity of the algorithm.

Ques 11.

Apply Kruskal’s algorithm to find a minimum cost spanning tree for the following graph: