MCS-031 Design and Analysis of Algorithms Jan – June 2012

Question 1:

(a) What is Randomized Quicksort? Analyse the expected running time of Randomized Quicksort, with the help of a suitable example.

(b) Explain the Greedy Structure algorithm. Give an example in which the Greedy technique fails to deliver an optimal solution.

(c) Describe the two properties that characterise a good dynamic programming Problem.

(d) State Traveling Sales Persons problem. Comment on the nature of solution to the problem.

Question 2: Give an analysis of each one of the following with examples:

(i) Insertion Sort

(ii) Selection Sort

(iii) Heap Sort

(iv) Merge Sort

(v) Quick Sort

Question 3:

(a) Consider Best first search technique and Breadth first search technique.
Answer the following with respect to these techniques.
Give justification for your answer in each case.

(i) Which algorithm has some knowledge of problem space?

(ii) Which algorithm has the property that if a wrong path is chosen, it can be corrected afterwards?

(b) Describe the difference between a Deterministic Finite Automata and Non-Deterministic Finite Automata. In general, which one is expected to have less number of states ?

(c) Explain “TURING THESIS” in detail.

Question 4:

(a) Write a randomized algorithm to statistic in a set of n elements Select.

(b) Write a recursive procedure to compute the factorial of a number.

(c) Design a Turing Machine that increments a binary number which is stored on the input tape.