Design and Analysis of Algorithms

What is the approximation ratio (or performance ratio) of the greedy algorithm for the Vertex Cover problem?

(i) 2
(ii) 1.5
(iii) ln n
(iv) 1

Randomized algorithms make use of:
(i) Deterministic input
(ii) Random choices during execution
(iii) Recursive backtracking
(iv) Fixed input-output pairs

Explain the approximation algorithm for the travelling salesman problem.

Discuss the steps to find approximate solutions to NP-Hard optimization problems using approximation algorithms with an example.

Explain the Bin Packing Problem using heuristic techniques such as:

• First Fit
• Best Fit
• Next Fit

Write the short note on the following:
(a) Cook's theorm
(b) Randomized algorithms
(c) Bin Packing

Answer the following:
(i) Describe randomized algorithms.
(ii) Write the algorithm for randomized quick sort.
(iii) Give the time complexity of randomized quick sort.

Write a short note on:

Heuristics characteristics and their application domains.

Write short notes on the following:
(i) Approximation algorithms.
(ii) Why are they important in the context of NP-hard optimization problems?
(iii) Describe how approximation algorithms can be applied to the Vertex Cover problem.