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

Printed

Time: 3 Hours

Roll FirstRanker.com

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

B.TECH.

FirstRanker.com

THEORY EXAMINATION (SEM–VI) 2016-17

APPROXIMATION AND RANDOMIZED ALGORITHMS

Max. Marks : 100

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

Note: Be precise in your answer. In case of numerical problem assume data wherever not provided.

SECTION-A

1 Explain the following : (10×2=20)

1. Define principle of optimality.
2. Define linear programming

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

3. What is order of growth?
4. Define -notation.
5. Give two examples of randomized algorithms.
6. State two applications of Approximation algorithms.
7. What is amortized efficiency?

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

8. Solve the recurrence relation, where T(1)=1 and T(n) for n>=2 satisfies
   T(n)=3T(n/2)+n
9. What is derandomized algorithms?
10. What is bin packing?

SECTION-B

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

2 Attempt any five of the following : (10×5=50)

1. Explain in detail about simplex method
2. Illustrate the steps involved in analyzing algorithm using an example.
3. Explain a sorting algorithm that use divide and conquer method.
4. Explain P, NP and NP complete problem.

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

5. Define Linear Programming
6. Explain permutation routing in a hypercube.
7. Discuss Euclidean TSP.
8. Discuss k-median on a cycle with suitable example.

SECTION-C

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

Attempt any two of the following : (15×2=30)

1. Suggest an approximation algorithm for traveling salesperson problems using Minimum spanning tree algorithm. Assume that the cost function satisfies the triangle inequality.
2. Explain in detail about approximation algorithm for the Knapsack problem.
3. Discuss some examples of randomized algorithms using basic inequalities and random variables.

FirstRanker.com

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