What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.

Explain the divide and conquer paradigm from algorithm design with a suitable example. Write the Quick sort algorithm using a randomized approach and explain its time complexity.

Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.

Write the algorithm for selection sort and explain its time and space complexity.

Solve the following recurrence relation using the master method.

1. T(n) = 7 T(n/2) + n²
2. T(n) = 4 T(n/4) + kn

Explain the greedy algorithm for the fractional knapsack problem with its time complexity.

Trace heap sort algorithm for the following data:

{2, 9, 3, 12, 15, 8, 11}

What do you mean by Dynamic programming strategy? Explain the element of DP.

Explain the approximation for solving vertex cover with a suitable example.

Explain Prism’s algorithm for MST problem and analyze its time complexity.

Explain in brief about the classes P, NP, and NP complete with examples.

Write short notes on

1. Backtracking strategy
2. Tractable and Intractable Problem