West Bengal Institute of Technology (WBIT) 2008-5th Sem B.Tech Computer Science and Engineering Computer Science -Design and Analysis of Algorithm - Question Paper
CS/B.TBGR (CWK)/SBM-8/CS-B03/06/(09) 3
ENGINEERING & MANAGEMENT EXAMINATIONS, DECEMBER - 2008 DESIGN AND ANALYSIS OP ALGORITHMS SEMESTER-5
Time : 3 Hours ] [ Full Marks : 70
GROUP-A (Multiple Choice Type Questions)
1. Choose the correct alternatives for the following : 10 x 1 = 10
I) Which of the following problems Is solved by using Branch and Bound method ?
a) Knapsack problem
b) Hamiltonian problem
c) Travelling salesman problem
d) 15-Puzzle problem.
II) Lower bound for any comparison sort is
a) O (log n) b) O (n2 )
c) O (nlog n) d) O ( n2 log n ).
ill) 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.
Iv) Which of the following algorithm design techniques is used in the quick sort algorithm ?
a) Dynamic programming b) Backtracking
c) Divide and conquer d) Greedy method. i_J
v) The Big O notation of the expression /(n) n log n+n2 + elog " is
a) O (n) b) Of n2 )
c) O ( n log n) d) O (elogn ).
vi) Which one is true of the following ?
a) All NP hard problems are NP complete
b) All NP complete problems are NP hard
c) Some NP complete problems are NP hard
d) None of these.
vii) Time complexity of non-deterministic algorithm is always
a) less than deterministic algorithm
b) greater than deterministic algorithm
c) equal to deterministic algorithm
d) none of these.
viiij Time complexity for recursive relation T (n) = 2T (Vn ) + 1 is
a) 0 (log n ) b) 0 ( n2 )
c) 8 { n log n ) d) 0 ( n ).
ix) BFS has running time
a) 0{|y| + |E|) b) 0( | V |)
c) Of | E |) d) 0(|N| + |E|).
x) In which sorting technique at every step each element is placed in its proper position ?
a) Bubble sort b) Merge sort
c) Quick sort d) Heap sort.
GROUP -B (Short Answer Type Questions )
Answer any-three of the following. 3x5 = 15
2. Find the best and worst case time compleidty of qtifigk sort.
3. pifferentiate between greedy method and dynamic programming.
4. Write an algorithm to find a minimal spanning tree of undirected graph.. Estimate the time complexity of your algorithm.
5. a) Let ( u,v ) be a minimum weight edge in a graph G. Show that (u, v) belongs to some minimum spanning tree oG.
b) Prove that n! = O (n" ).
6. Find the optimal solution for the fractional Knapsack problem given below :
%
1= {Ilf I2, I3, I4, I5} w = {5, 10, 20, 30, 40} v = {30, 20, 100, 90, 160}
The knapsack capacity, W = 60
7. Use a recursion tree to give an asymptotically tight solution to the recurrence : T(n)T(n-a)+T(a)+cn where a >=1 and c > 0 are constant.
GROUP -C (Long Answer Type Questions )
#
Answer any three of the following questions. 3x15 = 45
8. a) Find the minimum number of operations required for the following matrix chain
multiplication using dynamic programming :
A ( 10 x 20 ) * B ( 20 x 50 ) * C ( 50 x 1 ) * D ( 1 x 100 )
b) Give an algorithm for matrix-chain multiplication.
c) Design a back tracking algorithm to find all the Hamiltonian cycles in a Hamiltonian graph. What is the worst-case time complexity of the algorithm ? 5 + 3 + 7
9. a) What/are the characteristics of greedy algorithm ?
b) Discuss activity selection problem for Job sequencing.
c) A newspaper agent daily drops the newspaper to the area assigned In such a manner that he has to cover all the houses in the respective area with minimum travel cost. Compute the minimum travel cost. The area assigned to the agent where he has to drop the newspaper is shown in the figure below : 3 + 5 + 7
Give a non-deterministic graph colouring algorithm.
10. a) b) c)
11. a) b) c)
Define clases P, NP and NP-complete.
*
Describe circuit satisfiability problem and prove that clrcuit-SAT is In NP. 5 + 5 + 5
Write down the Dijkstra algorithm for finding out the shortest path.
Prove that the time complexity of Dijkstra algorithm Is 3{n-2)(n-l)/2-0(n2).
Find out the shortest path from vertex 1 to all remaining vertices for the following graph using Dijkstra algorithm. 6 + 3 + 6
12. a) Write down DFT algorithm and explain its method of execution,
7
b) Write short notes on any two of the following :
i) Asymptotic notation 11) Strassen's matrix multiplication ill) Approximation algorithms.
END
56661 (16/12)
2x4
|
Attachment: |
| Earning: Approval pending. |
