Download AKTU B-Tech 5th Sem 2018-2019 RCS 502 Design Analysis Of Algorithms Question Paper

Firstranker's choice

www.FirstRanker.com

Printed Pages: 02

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

Paper Id: 110502

www.FirstRanker.com

Roll No:

B TECH

(SEM V) THEORY EXAMINATION 2018-19

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

DESIGN & ANALYSIS OF ALGORITHMS

Subject Code: RCS502

Time: 3 Hours

Total Marks: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

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

2. Any special paper specific instruction.

SECTION A

1. Attempt all questions in brief.

   2 x 7 =14

   1. Rank the following by growth rate:
      

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

      n, 2^n, log n, log (logn), log2n, (lgn)^n, 4, (3/2)^n, n!
   2. Prove that if n>=1, then for any n-key B-Tree of height h and minimum degree t >=2, h<= log: ((n+1)/2).
   3. Define principal of optimality. When and how dynamic programming is applicable.
   4. Explain application of graph coloring problem.
   5. Compare adjacency matrix and linked Adjacency lists representation of a Graph with suitable example/diagram.

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

   6. What are approximation algorithms? What is meant by P (n) approximation algorithms?
   7. What do you mean by stability of a sorting algorithm? Explain its application

SECTION B

2. Attempt any three of the following:

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

   1. Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(an) + T((1-a)n) + cn, where a is a constant in the range(0 < a < 1) and c> 0 is also a constant.
   2. Define BNP, NP hard and NP Complete Problems: Prove that Travelling Salesman Problem is NP-Complete.
   3. Consider the weights and values of items listed below. Note that there is only one unit of each item. The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. Find the value of Vopt - Vgreedy

      Item	I1	I2	I3	I4
      W	10	7	4	2
      V	60	28	20	24

   4. Insert the following keys in a 2-3-4 B Tree:
      40, 35, 22, 90, 12, 45, 58, 78, 67, 60 and then delete key 35 and 22 one after other.

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

   5. Prove that if the weights on the edge of the connected undirected graph are distinct then there is a unique Minimum Spanning Tree. Give an example in this regard. Also discuss Prim's Minimum Spanning Tree Algorithm in detail.

www.FirstRanker.com

www.FirstRanker.com

SECTION C

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

3. Attempt any one part of the following:

   7x1=7

   1. The recurrence T (n) = 7T (n/3) + n² describes the running time of an algorithm A. Another competing algorithm B has a running time of S (n) = a S (n/9) + n². What is the smallest value of 'a' such that A is asymptotically faster than B.?
   2. How will you sort following array A of elements using heap sort:
      A(23, 9, 18, 45, 5, 9, 1, 17, 6).

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

4. Attempt any one part of the following:

   7x1=7

   1. Explain the different conditions of getting union of two existing binomial Heaps. Also write algorithm for union of two Binomial Heaps. What is its complexity?
   2. Insert the elements 8, 20, 11, 14, 9, 4, 12 in a Red-Black Tree and delete 12, 4, 9, 14 respectively.

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

5. Attempt any one part of the following:

   7x1=7

   1. When do Dijkstra and the Bellman-Ford algorithm both fail to find a shortest path? Can Bellman ford detect all negative weight cycles in a graph? Apply Bellman Ford Algorithm on the following graph:
      

      This download link is referred from the post: AKTU B-Tech Last 10 Years 2010-2020 Previous Question Papers || Dr. A.P.J. Abdul Kalam Technical University

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