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

DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE

Mid Semester Examination Sept. 2019

Course: B. Tech in Information Technology

Subject Name: Design and Analysis of Algorithms

--- Content provided by FirstRanker.com ---

Sem: V

Subject Code: BTITC502

Max Marks: 20

Date: 19/09/2019

Duration: 1 Hr.

--- Content provided by FirstRanker.com ---

Instructions to the Students:

1. Assume suitable data wherever necessary.

Q.1 Select any one option from the following questions. (6 Marks)

1. Which of the following standard algorithms is not a Greedy algorithm? (CO2)
   1. Dijkstra's shortest path algorithm
   2. Prim's algorithm

   --- Content provided by FirstRanker.com ---

   3. Kruskal algorithm
   4. Huffman Coding
   5. Bellman Ford Shortest path algorithm
2. The 0-1 Knapsack problem can be solved using Greedy algorithm. (CO2)
   1. True

   --- Content provided by FirstRanker.com ---

   2. False
3. Time required to merge two sorted lists of size m and n, is (CO3)
   1. O(mn)
   2. O(m+n)
   3. O(m log n)

   --- Content provided by FirstRanker.com ---

   4. O(n log m)
4. What is the worst-case time for binary search finding a single item in an array? (CO3)
   1. Linear time
   2. Quadratic time
   3. Logarithmic time

   --- Content provided by FirstRanker.com ---

   4. Constant time
5. What is the worst-case time for quick sort to an array of n elements? (CO3)
   1. O(log n)
   2. O(n log n)
   3. O(n)

   --- Content provided by FirstRanker.com ---

   4. O(n²)
6. Which of the following is/are the operations performed by Kruskal's algorithm? (CO2)
   1. sort the edges of G in increasing order by length
   2. keep a subgraph S of G initially empty
   3. builds a tree one vertex at a time

   --- Content provided by FirstRanker.com ---

   1. i, and ii only
   2. ii and iii only
   3. i and iii only
   4. All i, ii and iii

--- Content provided by FirstRanker.com ---

Q.2 Solve Any Two of the following. (3X2)

1. Write an algorithm for knapsack problem using greedy method. What is its time complexity? (CO1)
2. Explain quick sort with respect to its: (CO2)
   1. Best case behavior
   2. Worst case behavior
   3. What is the time complexity of it?

   --- Content provided by FirstRanker.com ---

3. Sort the following no. using merge sort: 10, 50, 87, 73, 64, 92, 23, 34, 54, 18, 36. (CO3)

Q.3 Solve Any One of the following. (8)

1. We want to merge some sorted files where the no. of records are: {12, 34, 56, 73, 24, 11, 34, 56, 78, 91, 34, 91, 62} what is the optimal way to merge them? (CO3)
2. Solve the travelling salesmen problem for the graph given below, adjacency matrix for the graph is (CO4)
   

   --- Content provided by FirstRanker.com ---

   	1	2	3	4
   1	0	4	1	3
   2	4	0	2	1
   3	1	2	0	5
   4	3	1	5	0

*** End ***

FirstRanker.com