Download DBATU B.Tech 2019 March 2nd Semester Design and Analysis of Algorithms Question Paper

DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE

Mid Semester Examination - March 2019

Course: S.Y.B.Tech(CSE)                                                                           Sem: II

Subject Name: Design & Analysis of Algorithms                                              Subject Code: BTCOC401

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

Max Marks: 20                                                                                             Date:- 11/Mar/2019

Duration:-1 Hr.

Instructions to the Students:

1. Check that you have received a correct Question paper.
2. Assume suitable data if necessary and mention it clearly

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

Q.1. Attempt any six Questions (1*6 = 6 Marks)

1. Which of the following asymptotic notation is the worst of all?
   a) O(n+9999)          b) O (n³)          c) O(log (n))          d) O (2ⁿ)
2. Two main measures for efficiency of algorithm are :
   a) Processor & Memory          b) Complexity & capacity          c) Time & space          d) Data & space

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

3. Which of the following does not exist in complexity theory?
   a) Best case          b) Worst case          c) Average case          d) Base case
4. Merging 4 sorted files containing 50, 10, 25 and 15 records will take optimal time.
   a) O (200)          b) O(100)          c) O(175)          d) O (150)
5. Define Feasible & optimal solution of Greedy algorithm.

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

6. DIjkstra's algorithm is also called ________ shortest path problem.
   a) Multiple source          b) Single source          c) Single destination          d) Multiple destination
7. State necessary criterion for a recursive function.

Q. 2. Attempt any two of the following (2*3 =6 Marks)

1. Explain Divide & Conquer strategy of algorithm development.

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

2. Consider the following instances of the Knap-Sack problem:
   n=3,m=20,(p1,p2,p3)=(24,25,15) and (w1,w2,w3)=(18,15,20).
   Find feasible solutions.
3. Obtain optimal solutions for the following jobs:

   Jobs	J1	J2	J3	J4
   Deadline	2	1	2	1
   Profit	100	27	15	10

Q.3. Attempt any one of the following (1*8 = 8 Marks)

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

1. Construct heap tree for following list of numbers.
   20,10,30,50,60,20,35,40,50,25,80 & perform heap sort.
2. Write a program for Merge Sort.

***END***

Visit FirstRanker.com for more resources.

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