WBUT 2012: DESIGN AND ANALYSIS OF ALGORITHM (Paper Code:CS-501)

CS/B.TECH(CSE)(N)/SEM-5/CS-501/2012-13

2012

DESIGN AND ANALYSIS OF ALGORITHM

Time Allotted : 3 Hours                                              Full Marks : 70

The figures in the margin indicate full marks.

Candidates are required to give their answers in their own words

as far as practicable.

GROUP – A

(Multiple Choice Type Question)

1.       Choose the correct alternatives for the following:     10 x 1 = 10

          i)       The Big O Notation of the expression

                   f(n) = n log₂ n + n² + e^log₂ ⁿ is

                   a)      O (n log₂ n)                                      b)      O (n²)

                   c)      O ( n )                                     d)      O (e^log₂ ⁿ).

          ii)      Traveling Salesman Problem is

                   a)      NP Hard                       b)      NP

                   c)      NP Complete                d)      none of these.

          iii)     o (g ( n ) ) is [Read as small oh of g( n ) ] is

                   a)      asymptotically loose     b)      asymptotically tight

                   c)      same as Big Oh             d)      None of these.