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

Total No. of Questions : 5] [Total No. of Printed Pages : 4

Time: $1\tfrac{1}{2}$ Hours] [Maximum Marks: 50

Note: Attempt all sections as directed.

Section-A

Note: Attempt any two questions.15 each

1. Attempt any two parts of the following :

(a) Write down the properties of asymptotic notations.

(b) Explain Recursive algorithm.

2. Attempt any two parts of the following :

(a) Give the general strategy of Divide and conquer method.

(b) Differential merge sort with quick sort with example.

3. Attempt two parts of the following :

(a) Write an algorithm for knapsack problem using Greedy Strategy.

(b) Give and explain minimum spanning tree algorithm.

Section-B

Note : Attempt any one question.20 each

4. Attempt any two questions :

(a) Discus the various stages of algorithm design and analysis process using flow chart.

(b) Explain dynamic programming.

(c) Write the formula to find the shortest path using Floyd’s approach. Use Floyd’s method to solve the following all pairs shortest path problem.

$\begin{bmatrix} 0 & \infty & 3 & \infty \\ 2 & 0 & \infty & \infty \\ \infty & 7 & 0 & 1 \\ 6 & \infty & \infty & 0 \end{bmatrix}$

5. Explain any two of the following:

(a) Huffman tree construction algorithm.

(b) Differentiate back tracking and branch and bound algorithm.

(d) Pseudo code conventions.

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

Thank You 🙂