Design And Analysis Of Algorithm 2019 – BSc Computer Science Part 3

Note: Attempt any five questions. All questions carry equal marks.

1. (a) What is algorithm ? Write and explain characteristics of a good algorithm.5

(b) What are recursive algorithms, explain with appropriate example ?5

2. (a) What are stacks ? Explain various operations that can be performed on stacks. Write an algorithm for above operations.7

(b) Define Disjoint set operations.3

3. (a) Write an algorithm to find maximum and minimum of given vector by using divide and conquer, also analyze its complexity.7

(b) What are randomized algorithm ?3

4. (a) Write various steps involved in Strassen’s matrix multiplication.5

(b) Write an algorithm for quick sort.5

5. (a) What is Single source shortest path problem, explain with an algorithm ?7

(b) What are minimum cost spanning trees, explain ?3

6. (a) State the merge sort and analyse its complexity.7

(b) Write best case and worst case complexity of binary search.3

7. What is 8-queen problem ? Represent a solution for it by using back tracking.10

8. Write short notes (any two) :5 each

(i) The Travelling Salesman Problem (TSP)

(ii) Optimal Binary Search Tree (OBST)

(iii) Least Cost Search

(iv) Hamilton Cycles

………………END………………

Thank You!