Download AKTU B-Tech 5th Sem 2015-2016 Design And Analysis Of Algorithms Ecs 502 Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 5th Semester (Fifth Semester) 2015-2016 Design And Analysis Of Algorithms Ecs 502 Question Paper

Printed Pages: _ 677 ECS-502
(Following Paper ID' and Roll No. to be filled in your
Answer Book)
Roll No.
B.Tech.
(SEM. V)THEORY EXAM. 2015-16
DESIGN AND ANALYSJS OF ALGORITHMS
[Time:3 hours] ? . [MaximumMarks:100|
Section-A
1. Attempt all parts. All parts carry equal marks. Write
answer of each part in short. (10x2=20)
(a) Why should we do asymptotic analysis of
algorithms? Explain.
(b) Order the following expressions by their
asymptotic growth and justify your answer
2?.n!, (log n)!,n3 52mg?, 220 , nloglogn , C"
2650 _ (1) P.T.O.

(C)
(d)
'(e)
(0
(g)
(h)
(i)
(i)
(k)
Attempt any five questions from this section.
How can youy modify Quick sort algorithm to
serch an item in a list?
What are all pairs shortest path?.?7 : '_
Dc?nc Convex Hull. "
Discuss various properties of Binomial Tree
What are the steps te design an algorithm?
Prove that red-black tree with n internal nodes has
height at most 2Iog2(n+1)
\
Prove that the maximum degree of n- node in a
binomial tree is logzn.
What do you understand by ?stable? sort? Name
two stable sort algorithms.
De?ne Greedy Approach.
Section-B
(5x10=50)
2. Explain insertion in Red Black Tree. Show steps for
inserting 9,8,7,6,5,4,3,2, & 1 into empty RB tree.
(2) ECS?502
2650
Show all the steps of Strassen?s matrix Multiplication
algorithm to multiply the fellowing matrices
3 2 1 5
x: and=y=
l4 8] [9 6]
Define Dynamic programming. How Dynamic
Programming approach is used to ?nd the shortest path?
Illustrate with an example.
Find optimal solution to the Fractional Knapasck
instances n= 7 and Knapsack capacity M = 15 Where
pro?ts and weights are as follows (pi, p2 ....?.p7) =
(10,5.15,7,6.18,3) & (wf, w2 ...... W7) = (2,3,5.7,l,4.l)
respectivel)
Construct the string- matching automaton for the pattern
P=a a b a b and illustrae its operation on the text string
T=aaababaabaabaab.
Illustrate the operation of heap sort on the array
A=(6,1.2,4,3,5,7,9.8,0)
Find an LCS for the sequences. X={x1, x2 ...... Xm,} and
Y={yl ,y2 ..... yn}. Also show that it requires 0 (m+n)
time.
(3) P.T.O.

9. Write short note on F aSt F ouriei' Transform (FFT).
, Section-C
Attempt any two questions from this section. (2x15=30)
10. Attempt both :
(a) Why thestatement ?The running time of algorithm
A is at least 0 (n3) is meaningless?? Explain .
(b) What is the procedure of paitition (A, p, r) in Quick
Sort and also de?ne the complexity of Quick Sort.
1 1 . What do you mean by Branch & Bound? How TSP
can be solve using this approach.
12. Attempt both :
(a) Discuss the relationship between the class P, NP,
NP- complete and NP- hard with suitable example
of each class. I
(b) De?ne Approximation algorithms. What is
ApproXimation ratio? Give an Approximation
algorithm for the Travelling Salesman
_._)(..__
- 2650 (4) ECS-502