GTU Computer Engineering (Semester 5)
Analysis And Design Of Algorithms
December 2014
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) Explain Bubble sort algorithm. Derive the algorithmic complexity in Best case, worst case and Average case analysis.
7 M
1 (b) Explain master theorem and solve the following recurrence equation with master method
1. T(n)= 9T(n/3) + n
7 M

2 (a) Explain Binary search algorithm with divide and conquer strategy and use the recurrence tree to show that the solution to the binary search recurrence T(n)= T(n/2) +Θ(1)is T(n)=Θ(lgn).
7 M
2 (b) Find Minimum Spanning Tree for the given graph using Prim's Algo. (initialization from node A)

7 M
2 (c) What is an amortized analysis? Explain accounting method and aggregate analysis with suitable example.
7 M

3 (a) Given two sequences of characters, P= Q= Obtain the longest common subsequence.
7 M
3 (c) Describe an assembly line scheduling problem and give dynamic programming algorithm to solve it
7 M
3 (d) Is Selection sorting a greedy algorithm? If so, what are the functions involved.
7 M

4 (a) How you can identify articulation points explain with example. Describe the use of articulation point.
7 M
4 (b) Explain in Brief:
NP Hard Problem, Polynomial reduction.
7 M
4 (c) Explain Backtracking with Knapsack problem.
7 M
4 (d) Explain Dijkstra's shortest path algorithm with example. If we want to display intermediate node than what change we should make in the algorithm.
7 M

5 (a) Explain Rabin-Karp method for string matching and also give the algorithm.
7 M
5 (b) Explain Strasson's algorithm for matrix multiplication.
7 M
5 (c) Explain how to apply the divide and conquer strategy for sorting the elements using quick sort with example. Write algorithm for quick sort method.
7 M
5 (d) Using algorithm find an optimal parenthesization of a matrix chain product whose sequence of dimension is ?13,5,89,3,34 ?(use dynamic programming).
7 M



More question papers from Analysis And Design Of Algorithms
SPONSORED ADVERTISEMENTS