West Bengal Institute of Technology (WBIT) 2009-5th Sem B.Tech Computer Science and Engineering Computer Science -Design and Analysis of Algorithm - Question Paper
Name :
Roll No.:.................................................................
Invigilators Signature:..............................................
CS/B.Tech(CSE)/SEM-5/CS-503/2009-10
2009 DESIGN & ANALYSIS OP ALGORITHMS
Time Allotted : 3 Hours Full Marks : 70
The figures in the margin indicate Jiill marks.
Candidates are require d to give their answers in their own words
as far as practicable.
GROUP - A ( Multiple Choice Type Questions )
1. Choose the correct alternatives for the following :
10 x 1 = 10
i) Lower bound of any comparison sort is
a) 0( log n) b) 0( n2)
c) O ( n log n) d) O ( n2 log n).
ii) 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.
iii) Kruskal algorithm is a
a) Divide & conquer algorithm
b) Branch and bound algorithm
c) Greedy algorithm
d) Dynamic programming.
Iv) Travelling salesman problem belongs to
b) NP class
a) P class c) NP- Hard
d) NP-complete class.
v) Time complexity of insertion sort is
b) Quadratic
a) Linear c) Cubic
d) Exponential.
vi) Which one of the following functions is asymptotically smallest ?
a) 2n
b) nlogn
c)
d) ( ioO )(lognl 1/3 + (loglogn)2/3.
vii) Which one of the following statements is correct ?
a) If A < p B and B e P then A e P
b) If A < p B and Ai P then B g P
cf If A< pB and B<pC then A< pC
d) all of these.
viii) Consider the following statements :
I) NP hard problem is a subset of NP complete problem.
II) An algorithm to multiply two matrices has complexity O ( n3 ) .
Which of the following alternatives is true.
a) I-True, II-False b) Both true
c) Both False d) I-False, II-True.
ix) Optimal substructure property is exploited by
a) Dynamic progamming b) Greedy method c) Both (a) & (b) d) None of these.
x) Which of the following approaches is adopted in Divide & Conquer algorithms ?
a) Top-down b) Bottom-up
c) Both (a) & (b) d) none of these.
GROUP -B ( Short Answer Type Questions )
Answer any three of the following. 3x5= 15
2. a) Derive the complexity of merge sort.
b) What is the difference between a 0-1 Knapsack problem and a fractional Knapsack problem ? 4+1
3. Write an algorithm for eight queens problem.
4. State master's theorem and find the time complexity for the following recurrence : 2 + 3
T(n) = 2T(n1/2) + log n
5. a) What are the basic characteristics of dynamic
programming ?
b) Write an algorithm for matrix-chain multiplication. 2 + 3
6. Apply backtracking technique to solve the 3-colouring problem for the following graph.
GROUP -C ( Long Answer Type Questions )
Answer any three of the following. 3 x 15 = 45
7. a) Define the classes P and NP.
b) Discuss what you mean by polynomial reductions.
c) Discuss diagrammatically the relations among P class, NP class, NP hard and NP complete.
d) Describe Clique Decision Problem ( CDP ).
e) Prove the CDP is NP complete. 2+2+2+2+7
8. a) State the general Knapsack problem. Write a greedy
algorithm for this problem and derive its time complexity.
b) Given the weight vector { 2, 3, 5, 7, 1,4, 1 ) and the profit vector ( 10, 5, 15, 7, 6, 18, 3 ) and a Knapsack of capacity 15, find at least three feasible solutions including optimal one for the knapsack problem of seven objects. 10 + 5
9. Write the algorithm of Quick sort. Find the best case, worst case and average case time complexities of this algorithm.
5+10
10. a) Explain how do you attempt to solve 15-puzzle problem
using branch and bound strategy. Draw a portion of the state space generated by it.
b) Write an algorithm for finding the minimum spanning tree of a graph. Discuss its time complexity. 8 + 7
11. a) What do you mean by non-deterministic algorithms ?
b) How are graphs represented in computer ?
c) Write short notes on any three of the following :
i) Recursion tree
ii) Approximation schemes
iii) Turing machines
iv) FFT algorithm. 3 + 3 + ( 3 x 3 )
55901 4
|
Attachment: |
| Earning: Approval pending. |
