STUPIDSID
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.
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