MORE IN Design and Analysis of Algorithms
VTU Computer Science (Semester 4)
Design and Analysis of Algorithms
December 2015
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) What is an algorithm? Explain the notion of algorithm with an example.
6 M
1 (b) Explain the asymptotic notations with examples.
6 M
1 (c) Write an algorithm for selection sort. Analyze its efficiency.
8 M

2 (a) What is divide and conquer? Explain the general method of divide and conquer.
6 M
2 (b) Write an algorithm for merge sort. Analyze its efficiency.
8 M
2 (c) Apply quick sort on following list and draw recursive call tree: 5, 3, 1, 9, 8, 2, 4, 7.
6 M

3 (a) What is minimum cost spanning tree? Apply Prim's and Kruskal's algorithm on Fig. Q3(a).

10 M
3 (b) Write Dijkstra's shortest path algorithm. Apply Dijkstra's algorithm on Fig. Q3(b) to obtain shortest paths.

10 M

4 (a) Explain dynamic programming. Find transitive closure using Warshall's algorithm for the digraph Q4(a).

6 M
4 (b) Find all pair shortest paths using Floyd's algorithm for the graph Fig. Q4(b).

8 M
4 (c) Find the optimal solution for the following instance of knapsack problem using dynamic programming.
 Item Weight Value 1 2 12 2 1 10 3 3 20 4 2 15
6 M

5 (a) Explain different decrease and conquer approaches using example.
6 M
5 (b) Differentiate between DFS and BFS.
4 M
5 (c) Write Horspool's algorithm for string matching. Find the pattern: BARNER. In the text: JIM_SAW_ME_IN_A_BARBERSHOP.
10 M

6 (a) What is decision tree? Draw the decision tree for three element selection sort and estimate its lower bound.
10 M
6 (b) Explain following with examples:
i) P problems ii) NP problems iii) NP-compete problems.
10 M

7 (a) What is back tracking? Draw the state space tree for 4-queen's problem.
8 M
7 (b) What is branch and bound method? Apply branch and bound to the following instance of assignment problme: $\begin{matrix} \begin{matrix} \text{Job 1} &\text{Job 2} &\text{Job 3} &\text{Job 4} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{matrix} \\ \begin{bmatrix} 9& & &2 & & &7 & & &8 \\ 6& & &4 & & &3 & & &7 \\ 5& & &8 & & &1 & & &8 \\ 7& & &6 & & &9 & & &4 \end{bmatrix}\begin{matrix} \text{Person a}\\ \text{Person b} \\ \text{Person c} \\ \text{Person d} \end{matrix} \end{matrix}$
6 M
7 (c) Explain approximation algorithm for traveling salesman problem.
6 M

8 (a) What is PRAM? Explain PRAM algorithm with example.
6 M
8 (b) Explain various computational models.
6 M
8 (c) What is list ranking? Explain different types of list ranking.
8 M

More question papers from Design and Analysis of Algorithms