click here to download ful paper qb updated part 1
click here to download ful paper qb updated part 2
http://www.mediafire.com/?7bu6dklkz5bznuq
sorry for the this error
Reg. No. :

B.E./B.Tech. DEGREE EXAMINATION,
NOVEMBER/DECEMBER 2010

Fourth Semester

Computer Science and Engineering

CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS

(Regulation 2008)

Time : Three hours

Answer ALL questions

Maximum : 100 Marks

PART A — (10 × 2 = 20 Marks)

1.

2.

3.

If f (n ) = a m n m + ....a1 n + a 0 , then prove that f (n ) = O(n m ) .

Establish the relationship between O and Ω .

Trace the operation of the binary search
algorithm for the input –15, –6, 0, 7,
9, 23, 54, 82, 101, 112, 125, 131, 142, 151,
if you are searching for the
element 9.

State the general principle of greedy
algorithm.

State the principle of optimality.

4.

5.

6.

7.

8.

9.

10.

Compare divide and conquer with dynamic
programming and dynamic
programming with greedy algorithm.

Explain the idea behind backtracking.

Define and solve the graph colouring problem.

Define NP Hard and NP Completeness.

What is a Minimum spanning tree?

Explain briefly the Time Complexity
estimation, space complexity
estimation and the trade off between Time and
Space complexity. (6)

Solve the following recurrence equations
completely

(1)

T (n ) =

T (n ) = 1, if n = 1 .

T (n ) = 5T (n − 1) − 6T (n − 2)

∑

n −1

i =1

T (i ) + 1, if n ≥ 2

(4)

(3)

(3)

(2)

(3)

n
T (n ) = 2T + n lg n .
2

Or

Question Paper Code : 53099

(b)

(i)

Write the linear search algorithm and analyse
for its best, worst
and average case time complexity.(10)

Prove that for any two functions

f (n ) and

g (n ) , we have

(ii)

f (n ) = è ( g (n )) if and only if f (n ) = O ( g (n )) and f (n ) = Ω( g(n )) . (6)

12.

(a)

(i)

Write a recursive algorithm to determine the
max and min from a
given element and explain. Derive the time
complexity of this
algorithm and compare it with a simple brute
force algorithm for
finding max and min.(10)

For the following list of elements trace the
recursive algorithm for
finding max and min and determine how many
comparisons have
been made.

22, 13, –5, –8, 15, 60, 17, 31, 47.

Or

(ii)

(b)

(i)

Write the container loading greedy algorithm
and explain. Prove
that this algorithm is optimal.(8)

Suppose you have 6 containers whose weights
are 50, 10, 30, 20,
60, 5 and a ship whose capacity is 100. Use
the above algorithm to
find an optimal solution to this instance of
the container loading
problem.(8)

Write and explain the algorithm to compute the
all pairs source
shortest path using dynamic programming and
prove that it is
optimal(8)

For the following graph having four nodes
represented by the
matrix given below determine the all pairs
source shortest path (8)

(ii)

13.

(a)

(i)

(ii)

(b)

(i)

Write the algorithm to compute the 0/1
knapsack problem using
dynamic programming and explain it.(8)

(ii)

Solve the following instance of the 0/1,
knapsack problem given the
knapsack capacity is W = 5(8)

Items

1

2

3

4

Weight

2

1

3

2

Value

12

10

20

15

0 ∞ 3 ∞

2 0 ∞ ∞
∞ 7 0 1

6 ∞ ∞ 0

Or

2

(6)

53099

14.

(a)

Or

(b)

Write an algorithm to determine Hamiltonian
cycle in a given graph
using back tracking. For the following graph
determine the Hamiltonian
cycle.(8 + 8)

15.

(a)

(b)

Write an algorithm and explain to determine
Biconnected Components.
Prove the theorem that two biconnected
components can have at most
one vertex as common and this vertex is an
articulation point.(10 + 6)
Powered by
www.annaunivquestionbanks.blogspot.com

1

2

3

4

4

7

5

3

40

42

25

12

Items

Weight

Value

Or

——————

3

Explain with an algorithm as to how 0/1
knapsack problem is solved
using branch and bound technique. Apply branch
and bound technique to
solve the following 0/1 knapsack instance if W
= 10.(8 + 8)

53099

Write an algorithm to determine the Sum of
Subsets for a given Sum and
a Set of numbers. Draw the tree representation
to solve the subset sum
problem given the numbers set as {3, 5, 6, 7,
2} with the Sum = 15. Derive
all the subsets.(8 + 8)

set 2 click here to download
0 comments:
Post a Comment