Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 5th Semester (Fifth Semester) 2018-2019 RCS 502 Design Analysis Of Algorithms Question Paper
PaperId: I 110502 RollNo:{ l I L l I TT I
T ime: 3 Hours
B TECH
(SEM V) THEORY EXAMINATION 2018-19
DESIGN & ANALYSIS OF ALGORITHMS
T 0m! Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper speci?c instruction.
SECTION A
l. Attempt all questions in brief. 2 x 7 = 14
3. Rank the following by growth rate:
11, 2'3 " ,log n, log(logn),log1n,(lgn)15? 4 (3/2)? 11!
b. Prove that if n>=l, then for any n-key B-Tree of height h and minimum degree t >:2. h<=
log1((n +1)/2).
c. De?ne principal of optimality. When and how dynamic programming is
applicable
d. Explain application of graph coloring problem. i.
e. Compare adjacency matrix and linked Adjacqngy? sts representation of a Graph with
suitable example/diagram ? ?
f. What are approximation algorithms? W meant by P (n) approximation algon?smg"
g. What do you mean by stability of a WE algorithm? Explain its application!
2. Attempt any three of the following: RE: ? ,
a1
swam?: B
Use a [CCUISiOD ?ee to give a? asymptotically tight solution to the. tecun?ence
T(n)~ = T(an) + T(( [- g??i cn where a is a constant in the rag?) {1K 1 and
c> 0 is also a cons ? 5%
De?ne BNP, Wham and NP Complete Problems: J?mw that Travelling Salesman
Problem IS NP- -Complete.
."". k '
Consider the weights and values of items listed b.elow 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 15 maximized Moreover no item may be split The
total value of items picked by an optimal algorithm is denoted by Vopl. A greedy
algorithm sorts the items by their value-to-weight ratios in descending order and packs
them greedily, starting from the ?rst item in the ordered list. The total value of items
picked by the greedy algorithm 15 denoted by ngd\ Find the value of Vopt ngdy
??1 ithm 11 12 la 14
> W 10 7 4 2
V 60 28 20 24
Inseit 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.
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.
SECTION C
Attempt any one part of the following: 7 x l = 7
(a) The recurrence T (n) = 7T (n/3) + 112 describes the running time of an algorithm A.
Another competing algorithm B has a running time of S (n) = a S (n/ 9) + n2. What is the
smallest value of ?a" such that A is asymptotically faster than 8.?
(b) How will you sort following may A of elements using heap sort:
A=(23,9,l8,45,5,9,1,17, 6).
Attempt any one part of the following: 7 x l = 7
(3) 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?
(b) Insert the elements 8, 20, ll, 14, 9, 4, 12 in a Red-Blaek Tree and delete 12, 4, 9, 14
respectively.
Attempt any one part of the following: 7 x 1 = 7
(a) When do Dijkstra and the Bellman-Ford algorithm both fail to ?nd a shortest patli?ICan
Bellman ford detect all negative weight cycles in a graph'?Apply Bellman F ord Algorithm
0n the following graph:
(b) Given an integer x and a positive number 11, use divide &. conquer approach to write a
function that computes x?with time complexity O (logn) 1;? "
>3: A -?.; ?., /.
V?: 1. u ?
? ;
1% :
Attempt any one part of the following: $1 7 x 1= 7
(a) Solve the Subset sum problem using Backtrackmg where n=4 m=l8 w [4]? = {5 10, 8
13:
(b) Give Floyd War shall algorithm to ?nd?he shortest path for all pairs of vertices in a
graph Give the complexity of the algorithm Explain with example
Attempt any one part of the following?
7 x l = 7
(a) What is the application of?? t" Fourier Transform (FFT)? Also write the recursive
algorithm for FFT. ??3-
(b) Give a linear time algorithm to determine if a text T is a cycle rotation of another stting T
For example, ?RAJA? and ?JARA? are cyclic rotations of each other
44 vwm, ?-77:
2133.4.wsr?.
This post was last modified on 29 January 2020