M.Tech III (Third) Semester Examination 2012-13

Course Code:MCS336 Paper ID:0973209

Approximation Algorithm

Time: 3 Hours Max. Marks: 70 Max Marks: 75

Note: Attempt six questions in all. Q. No. 1 is compulsory.

1. Answer any five of the following (limit your answer to 50 words). (4x5=20)

a) What is an NP-complete problem? Why is it such an important topic in computer science?

b) Explain Steiner trees in detail..

c) How a Euclidian TSP works? Explain.

d) How one can do dual fitting based analysis for greedy set algorithm?

e) Explain the mechanism for scheduling on unrelated parallel machines.

f) What do you mean by NP-hard problem?

g) Explain asymptotic p-task in detail.

h) What is the need of rounding algorithms? Explain with suitable example.

2. a) A radar unit is used to measure speeds of cars on a motorway. The speeds are normally distributed with a mean of 90 km/hr and a standard deviation of 10 km/hr. What is the probability that a car, picked at random, is travelling at more than 100 km/hr? (5)

b) Entry to a certain University is determined by a national test. The scores on this test are normally distributed with a mean of 500 and a standard deviation of 100. Aakash wants to be admitted to this University and he knows that he must score better than at least 70% of the students who took the test. Aakash takes the test and scores 585. Will he be admitted to this University? Show all the steps. (5)

3. Prove the Vertex cover problem is NP-complete? Also write the greedy algorithm for vertex set cover. (10)

4. Explain the story behind Knapsack problem? Explain various types of Knapsack problem with the help of suitable example. (10)

5. State and prove LP-duality theorem. (10)

6. What do you mean by K-median problem? Explain with the help of an example? Also explain primal dual schema. (10)

7. What do you mean by Pseudo Polynomial Time Algorithm? What are its major significances in Computer Science? Explain with suitable example. (10)

8. Write shorts notes on any two of the following: (5+5)

a) Randomized complexity classes

b) Bin-packing

c) Delta TSP