1 (a)
Find ged(31415, 14142) by applying Euclid's algorithm. Estimate how many times it is faster when compared to the algorithm based on consecutive integer checking.

4 M

1 (b)
Compare the order growth of 1/2 n(n-1) and n

^{2}.
4 M

1 (c)
Explain the mathematical analysis of Fibonacci recursive algorithm.

6 M

1 (d)
Write Brute force string matching algorithm.

6 M

2 (a)
Find the upper bound of recurrences given below by substitution method. \[ \displaystyle i) \ 2T \left ( \dfrac {n}{2} \right )+n \\ ii) \ T\left ( \dfrac {n}{2} \right )+1 \]

6 M

2 (b)
Sort the following elements using merge sort. Write the recursion tree.

70, 20, 30, 40, 10, 50, 60

70, 20, 30, 40, 10, 50, 60

6 M

2 (c)
Write the algorithm for quick sort. Derive the worst case time efficiency of the algorithm.

8 M

3 (a)
Write greedy method control abstraction for subset paradigm.

4 M

3 (b)
Using greedy method, trace the following graph to get shortest path from vertex 'a' to all other vertices.

6 M

3 (c)
What is the solution generated by the function job scheduling (JS) when n=5,

[P

[d

[P

_{1}, P_{2}, P_{3}, P_{4}, P_{5}]=[20, 15, 10, 5, 1] and[d

_{1}, d_{2}, d_{3}, d_{4}, d_{5}, = [2, 2, 1, 3, 3]
6 M

3 (d)
Apply PRIMS algorithm for the following graph to find minimum spanning tree.

4 M

4 (a)
Using dynamic programming, compute the shortest path from vertex 1 to all other vertices.

10 M

4 (b)
Solve the Knapsack n=3, {W

_{1}, W_{2}, W_{3}}={1, 2, 2} and {P_{1}, P_{2}, P_{3}}={18, 16, 6} and M=4 dynamic programming.
4 M

4 (c)
For the given graph, obtain optimal cost tour using dynamic programming.

6 M

5 (a)
What are the three variations of decrease and conquer technique.

3 M

5 (b)
Conduct DFS for the following graph.

5 M

5 (c)
Apply DFS based algorithm to solve topological sorting problem for the following graph:

6 M

5 (d)
Construct shift table for the pattern EARN and search for the same in text FAIL - MEANS - FIRST - ATTEMPT - IN - LEARNING using Horspool algorithm.

6 M

6 (a)
Explain the four methods used to establish lower bounds of algorithm.

8 M

6 (b)
Define decision trees. Write the decision tree for the three element selection sort.

6 M

6 (c)
Define P, NP and NP complete problems.

6 M

7 (a)
Explain how back tracking used for solving 4-queens problem. Write the state space tree.

6 M

7 (b)
Solve the following assignment problem using branch and bound method.

Job1 | Job2 | Job3 | Job4 | |

Person a | 9 | 2 | 7 | 8 |

Person b | 6 | 4 | 3 | 7 |

Person c | 5 | 8 | 1 | 8 |

Person d | 7 | 6 | 9 | 4 |

8 M

7 (c)
Apply twice-around-the-tree algorithm for the travelling sales person problem for the following graph.

6 M

8 (a)
Explain the various models for parallel computations.

9 M

8 (b)
Let the i/p to the prefix computations be 5, 12, 8, 6, 3, 9, 11, 12, 1, 5, 6, 7, 10, 4, 3, 5 and three are four processors and ? stands for addition. With diagram explain how prefix computation is done by parallel algorithm.

8 M

8 (c)
Explain how matrix M is computed using parallel algorithm for the given graph.

3 M

More question papers from Design and Analysis of Algorithms