Download DBATU B.Tech 2019 Oct-Nov IT 5th Sem Design and Analysis of Algorithms Question Paper

Download DBATU (Dr. Babasaheb Ambedkar Technological University) B Tech 2019 Oct-Nov (Bachelor of Technology) IT 5th Sem Design and Analysis of Algorithms Question Paper

QJ
Q.2
(A)
(B)
'(C)
Q.3
(A)
DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE
Mid Semester Examination Sept. 2019
V Course; B. Tech in Information Technology Sem: V
Subject Name: Design and Analysis of Algorithms Subject Code: BTITC502A
Max Marks: 20 Date: 19/09/2019 Duration:-1 Hr.
, Instructions to the Students:
1. Assume suitable data wherever necessary.
Select any one option from the following questions.
1. Which of the following standard algorithms is not a Greedy algo rithm?
a) Dijkstra?s shortest path algorithm b) Prim?s algorithm c) Kruskal algorithm d)
Huffman Coding e) Belimen Ford Shortest path algorithm
2. The 0-1 Knapsack problem can be solved using Greedy algorithm.
a) True b) False
3. Time required to tnerge tw0?sorted lists of size In and n, is
a) O(m | n) b) O(m + n) c) O(m log n) d) O(nlog m)
4. What is the worst-case time for binary search finding a single item in an array?
a) Linear time h) Quadratic time c) Logarithmic time d) constant time
5. What is the worst?case time for qnick sort to an array of n elements?
a) O(log n) b) O(n log n) c) O(n) d) O(n?) '
6. Which of the follmying is/are the operations performed by kruskal?s algorithm.
i) sort the edges of G In increasing order by length ii) keep a subgraph S of G initially
empty iii) builds a tree one vertex at a time
a) i, and ii only b) ii and iii only c)i and iii only d) All i, ii and iii
Solve Any Two of the following.
Write an algorithm for knapsack problem using greedy method. What is its time
complexity?
Explain quick sort with respect to its:
(a) Best case behavior ?
(b) Worst case behavior
(c) What is the time complexity of it?
Sort the following no. 'using merge sort: 10, 50, 87, 73, 64, 92, 23, 34,54, 18, 36.
Solve Any One of the following.
We want to merge some sorted ?les where them). of records are: {12, 34, 56, 73, 24, ll,
34, 56, 78,91, 34, 91, 62} whnt is optimal way to merge them?
'W?ET ?
(Level/C
0)
C02
C02
C03
C03
C03
C02
C01
C02
C03
C03
Maxks
3X2

'TVr-?llf
(B) Solve the (ravelling salesmen problem for the graph given below, adjacency matrix for CO4
the graph is L ' V L
1 2 3? ?4
1 o 4 1 :3 .
.2Wg4021
3 1 2 o 15* i
4 3 1 s p i
*** End iii: