Printed
Time: 3 Hours
Roll FirstRanker.com
--- Content provided by FirstRanker.com ---
B.TECH.
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)
- Define principle of optimality.
- Define linear programming
- What is order of growth?
- Define -notation.
- Give two examples of randomized algorithms.
- State two applications of Approximation algorithms.
- What is amortized efficiency?
- Solve the recurrence relation, where T(1)=1 and T(n) for n>=2 satisfies
T(n)=3T(n/2)+n - What is derandomized algorithms?
- What is bin packing?
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
--- Content provided by FirstRanker.com ---
2 Attempt any five of the following : (10×5=50)
- Explain in detail about simplex method
- Illustrate the steps involved in analyzing algorithm using an example.
- Explain a sorting algorithm that use divide and conquer method.
- Explain P, NP and NP complete problem.
- Define Linear Programming
- Explain permutation routing in a hypercube.
- Discuss Euclidean TSP.
- Discuss k-median on a cycle with suitable example.
--- Content provided by FirstRanker.com ---
SECTION-C
--- Content provided by FirstRanker.com ---
Attempt any two of the following : (15×2=30)
- Suggest an approximation algorithm for traveling salesperson problems using Minimum spanning tree algorithm. Assume that the cost function satisfies the triangle inequality.
- Explain in detail about approximation algorithm for the Knapsack problem.
- Discuss some examples of randomized algorithms using basic inequalities and random variables.
--- Content provided by FirstRanker.com ---
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 ---