Answer all the questions in the assignment which carry 80 marks in total. 20 marks are for viva voce. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation. Make suitable assumption if necessary. All algorithms should be nearer to c-language.

Q1. There are three asymptotic notations to define the time complexity of an algorithm. Define these notations with the help of an example for each.

Q2. What is the Master Theorem? What kind of the problems are solved through this theorem. Use Master Theorem to give the tight asymptotic bounds of the following recurrence relation.

T (𝑛) = 2T ( 𝑛 2 ) + 𝑛 2

Q3. (a) What are the three methods for solving recurrence relations. Elaborate any two methods with the help of appropriate examples.

(b) Define and explain the recurrence relations for the following problems .

(i) Fibonacci series. (ii) Merge Sort.

Q4. Write Insertion Sort algorithm to sort the following list of integer numbers. Show all the intermediate steps.

         85        55       87      21        98      5       8      15     36   4

Also compute the worst case time complexity of the algorithm.

Q5. Write a program an algorithm to find a minimum of 10 integer numbers stored in an array and calculate the total number of comparison operations and how many times the loop will execute in the program?

Q6. Write pseudocode to compute an using right to left binary exponentiation algorithm and perform its complexity analysis. Apply the algorithm to compute a 33 and show all the intermediate steps.

Q7. Define minimum cost spanning tree (MCST)? What are its applications? Write Kruskal's algorithm for constructing a MCST using Greedy approach and apply this algorithm to the following graph.

Show all the intermediate steps.

Q8 (a) Illustrate the operation of Merge Sort algorithm for the following array A

42 84 15 60 25 10 35 70 75 5

(b) Show how the recurrence for Merge Sort algorithm can be solved through the recurrence tree.

Q9. Write all the three properties of shortest path and generic algorithm for solving a single source shortest path problem.

Q10. Define an optimization problem. Write a generic algorithm for applying greedy technique to solve an optimization problem and apply it to solve the following problem:

Consider a list of available currency notes in all denominations. Further it is assumed that currency notes of each denomination are available in sufficient numbers for the purpose of using minimum number of currency notes C = {1,2,5,10,50,100,500}

What should be the minimum number of notes to collect 999. Show all the intermediate steps

Q11. Define the following techniques. What kinds of problems are solved through these techniques? Discuss.

(i) Branch & Bound

(ii) Dynamic Programming