Analysis And Design Of Algorithms (3150703)

Q1. What is an Algorithm? Explain various properties of an algorithm.

Q2. Discuss insertion sort with its time complexity. Support your answer with suitable example.a=(10,27,30,88,17,98,42,54,72,95)

Q3. Write a program/algorithm of Quick Sort Method and analyze it with example. A=(25,29,30,35,42,47,50,52,60)

Q4. Explain the use of Divide and Conquer Technique for Binary Search Method. What is the complexity of Binary Search Method? Explain it with example. Search key=13, a=(2,4,7,8,10,13,14,60)

Q5. Explain how to find out Longest Common Subsequence of two strings using Dynamic Programming method. Find any one Longest Common Subsequence of given two strings using Dynamic Programming.
X=abbacdcba
Y=bcdbbcaac

Q6. Write equation for Chained matrix multiplication using Dynamic programming. Find out optimal sequence for multiplication:
A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal parenthesization of matrices.

Q7. Write the Prim’s Algorithm to find out Minimum Spanning Tree. Apply the same and find MST for the graph given below

Q8. Using greedy algorithm find an optimal schedule for following jobs with n=6.
Profits: (P1,P2,P3,P4,P5,P6) = (20, 15, 10, 7, 5, 3)
Deadline: (d1,d2,d3,d4,d5,d6) =(3, 1, 1, 3, 1, 3)

Q9. Explain Breadth-First-Search andDepth First Traversal Methodin brief with suitable example.

Q10. What do you mean by backtracking? Explain in brief. Discuss four queens problem using backtracking

Q11. Discuss Rabin-karp algorithm for string matching.

Q12. Explain finite automata for string matching with example.

Q13. Consider Knapsack capacity W=9, w=(3,4,5,7) and v=(12,40,25,42) find the maximum profit using dynamic method.

Q14. Write the pseudo-code for Naïve- string Matching algorithm.

Q15. Write the master theorem. Solve following recurrence using it.
1. T(n)= 9T(n/3)+n
2. T(n)= 3T(n/4)+nlogn.