FirstRanker Logo

FirstRanker.com - FirstRanker's Choice is a hub of Question Papers & Study Materials for B-Tech, B.E, M-Tech, MCA, M.Sc, MBBS, BDS, MBA, B.Sc, Degree, B.Sc Nursing, B-Pharmacy, D-Pharmacy, MD, Medical, Dental, Engineering students. All services of FirstRanker.com are FREE

📱

Get the MBBS Question Bank Android App

Access previous years' papers, solved question papers, notes, and more on the go!

Install From Play Store

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

This post was last modified on 29 January 2020

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


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
  3. --- Content provided by FirstRanker.com ---

  4. What is order of growth?
  5. Define -notation.
  6. Give two examples of randomized algorithms.
  7. State two applications of Approximation algorithms.
  8. What is amortized efficiency?
  9. --- Content provided by FirstRanker.com ---

  10. Solve the recurrence relation, where T(1)=1 and T(n) for n>=2 satisfies
    T(n)=3T(n/2)+n
  11. What is derandomized algorithms?
  12. 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.
  5. --- Content provided by FirstRanker.com ---

  6. Define Linear Programming
  7. Explain permutation routing in a hypercube.
  8. Discuss Euclidean TSP.
  9. 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 ---



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 ---