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

Tuesday, 22 January 2013 12:45Web

**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 issu

**e.**

**9.**What is "Greedy Algorithm"? write its pseudo cod

**e.**Prove that the fractional knapsack issue has a greedy-choice property.

**10.**Prove that matroids exhibit the greedy option property.

**1**provide a linear time algorithm along with proof of correctness to obtain strongly connected components of a graph.

**1.****1**elaborate a single source shortest paths? write down Dijkstras algorithm for it.

**2.****1**describe approximation algorithm. What is approximation ratio? Approximate the travelling salesman issue with triangle inequality.

**3.****1**provide the randomized version of quick sort Analyse it for finding the expected running tim

**4.****e.**

**1**Write a short notes on the following:

**5.****(**Randomised algorithm

**i)****(**Rabin-Karp algorithm.

**i****i)****1**describe NP,NP hard and NP complet

**6.****e.**provide examples of every.

Earning: Approval pending. |