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