Use Mathematical Induction to prove that <img src='./qimages/9788-1a.jpg'> For a problem two algorithms A1 and A2 have time complexities 5n^2 and 100 n log n. Find the range for the size of instance of the given problem for which Al is more efficient than A2 Define the big theta notation. Show that n^2 3 log n Explain the bottom-up build heap procedure.
Illustrate heapsort algorithm on the sequence 12, 25, 13, 7>.
Solve the following recurrence equations: T(n Write a Regular expression to generate strings of even length over the alphabet L b}.

2.(a) Give a divide and conquer algorithm to find the ith smallest in an unsorted list of n integers. Show that the algorithm works in time. Write a recursive function to calculate the sum of all elements in an integer array. Explain any two applications of DFS traversal algorithm.

3.(a) Given the currency coins of denomination 4 and 6. Design a dynamic programming algorithm to obtain minimum number of coins for a given amount. Using Prim's algorithm, find a Minimal Spanning tree for the graph given below:

<br><br> <img src='./qimages/9788-3b.jpg'>
Write a context-free grammar to generate all palindromes of even length over the alphabet L bl.
Derive the parse tree and derivation for the string aabbaa. Explain the algorithm to find the Strongly Connected Component in an undirected graph.

(ii) Find the Strongly Connected Components in the following graph:

<br><br> <img src='./qimages/9788-4b-ii.jpg'>

5.(a) Explain the following: Undecidable problems
Turing machines
Define the Class NP and NP-complete problems. Write a Turing machine to recognize the language of all strings of even length over the alphabet b}.