Download AKTU B-Tech 6th Sem 2016-2017 NCS064 Approximation And Randomized Algorithms Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 6th Semester (Sixth Semester) 2016-2017 NCS064 Approximation And Randomized Algorithms Question Paper

Printed Pages : 1 Roll No.| l l l l I l l l l l NCS064
B.TECH.
THEORY EXAMINATION (SEM?VI) 2016-17
APPROXIMATION AND RANDOMIZED ALGORITHMS
Time : 3 Hours Max. Marks : 100
Note : Be precise in your answer. In case Ofnumerical problem assume data wherever not provided.
SECTION-A
1 Explain the following : (10x2=20)
a) Define principle of optimality.
b) Define linear programming
c) Solve the recurrence relation, where T(1)=1 and T(n) for n>=2 satisfies
T(n)=3T(n/2)+n
d) What is order of growth?
e) Define ?-n0tation.
f) Give two examples of randomized algorithms.
g) What is amortized efficiency?
h) State two applications of Approximation algorithms.
i) What is derandomized algorithms?
j) What is bin packing?
SECTION-B
2 Attempt any five of the following : (10x5=50)
a) Explain in detail about simplex method
b) Illustrate the steps involved in analyzing algorithm using an example.
c) Explain a sortng algorithm that use divide and conquer method.
(1) Explain P, NP and N P complete problems.
e) Define Linear Programming
f) Explain permutation routing in a hypercube.
g) Discuss Euclidean TSP.
h) Discuss k-median on a cycle with suitable example.
SECTION-C
Attempt any two of the following : (15x2=30)
3. Suggest an approximation algorithm for traveling salesperson problems using Minimum
spanning tree algorithm. Assume that the cost function satisfies the triangle inequality.
4. Explain in detail about approximation algorithm for the Knapsack problem.
5. Discuss some examples of randomized algorithms using basic inequalities and random
variables.