Hemwati Nandan Bahuguna Garhwal University 2005 B.E Electrical and Electronics Engineering algorithm design and analysis - Question Paper

1. What operations are supported on disjoint sets?
2. Write an algorithm HEAP_DELETE (A,i),which deletes the item in node I from heap A.
3. Solve the recurrence relation by iteration: T(n)=T(n-1)+n^4
4. Rank the subsequent functions by order of growth: (3/2)^n,(2/3)^n,2^2^n,e^n,2^2^n,2(n!)
5. show that for any real constants a and b where: b>0,(n+a)^b=q(n)^b
6. Can the master method be applied to solve recurrence: T(n)=4T(n/2)+n^2logn? Why or Why not?
7. Show that the outcome of inserting the subsequent items in an initally empty B-tree of order 5: 25,31,38,76,05,60,38,08,30,15,35,17,23,53,27,43,65,48
8. discuss dynamic programming. Apply it on matrix chain multiplication issue.
9. What is "Greedy Algorithm"? write its pseudo code. Prove that the fractional knapsack issue has a greedy-choice property.
10. Prove that matroids exhibit the greedy option property.
11. provide a linear time algorithm along with proof of correctness to obtain strongly connected components of a graph.
12. elaborate a single source shortest paths? write down Dijkstras algorithm for it.
13. describe approximation algorithm. What is approximation ratio? Approximate the travelling salesman issue with triangle inequality.
14. provide the randomized version of quick sort Analyse it for finding the expected running time.
15. Write a short notes on the following: (i) Randomised algorithm (ii) Rabin-Karp algorithm.
16. describe NP,NP hard and NP complete. provide examples of every.

Earning:   Approval pending.