1 (a)
What is an algorithm? What are the properties of an algorithm? Explain with an example.

8 M

1 (b)
Explain brute force method for algorithm design and analysis. Explain the brute force string matching algorithm with its efficiency.

8 M

1 (c)
Express using asymptotic notation i) n! ii) 6×2

^{n}+n^{2}
4 M

2 (a)
Explain divide and conquer technique. Write the algorithm for binary search and find average case efficiency.

10 M

2 (b)
What is stable algorithm? Is quick sort stable? Explain with example.

6 M

2 (c)
Give an algorithm for merge sort.

4 M

3 (a)
Explain the concept of greedy technique for Prim's algorithm. Obtain minimum cost spanning tree for the graph below Prim's algorithm.

9 M

3 (b)
Solve the following single source shortest path problem assuming vertex 5 as the source.

9 M

3 (c)
Define the following: i) Optimal solution; ii) Feasible solution

2 M

4 (a)
Using Floyd's algorithm solve the all pair shortest problem for the graph whose weight matrix is given below: \[ \begin{bmatrix} 0 &\infty &3 &\infty \\2 &0 &\infty &\infty \\\infty &7 &0 &1 \\6 &\infty &\infty &0 \end{bmatrix} \]

7 M

4 (b)
Using dynamic programming, solve the following knapsack instance.

N=4. M=5

(W

( P

N=4. M=5

(W

_{1}, W_{2}, W_{3}, W_{4})= (2, 1, 3, 2)( P

_{1}, P_{2}, P_{3}, P_{4})=(12, 10, 20, 15).
5 M

4 (c)
Outline an exhaustive search algorithm to solve traveling salesman problem.

8 M

5 (a)
Write and explain DFS and BFS algorithm with example.

8 M

5 (b)
Obtain topologies sorting for the given diagram using source removal method.

5 M

5 (c)
Explain Horspool's string matching algorithm for a text that comprises letter and space (denoted by hyphen) i.e "JIM-SAW-ME-IN-BARBER-SHOP" with pattern "BARBER". Explain its working along with a neat table and algorithm to shift table.

7 M

6 (a)
Define the following:

i) Class P

ii) Class NP

iii) NP complete problem

iv) NP hard problem

i) Class P

ii) Class NP

iii) NP complete problem

iv) NP hard problem

8 M

6 (b)
Write the decision tree to sort the elements using selection sort and find the lower bound.

8 M

6 (c)
What is numeric analysis?

2 M

6 (d)
Brief overflow and underflow in numeric analysis algorithms.

2 M

7 (a)
What is back tracking? Apply back tracking problem to solve the instance of the sum of subset problem: S={3,5,6,7} and d=15.

7 M

7 (b)
With the help of a state space tree, solve the following instance of the knapsack problem by the branch and bound algorithm.

Item | Weight | Value |

1 2 3 4 | 4 7 5 3 | 40 42 25 12 |

Knapsack | Capacity | W=10 |

6 M

7 (c)
Explain how backtracking is used for solving 4-Queen's problem. Show the state space table.

7 M

8 (a)
What is prefix computation problem? Give the algorithm for prefix computation which uses

i) n processors; ii) n/log n, processors.

Obtain the time complexities of these algorithms.

i) n processors; ii) n/log n, processors.

Obtain the time complexities of these algorithms.

10 M

8 (b)
What is super linear speed up? Obtain the maximum speed up where P=10 and various values of f=0.5, 0.1, 0.001.

5 M

8 (c)
What are the different ways resolving read and write conflicts?

5 M

More question papers from Design and Analysis of Algorithms