Design and Analysis of Algorithms 2073

Attempt all questions.

1.  Explain bog-oh, big-omega and big-theta notations for computing analysis of algorithm with example.

2.  What do you mean by recurrence relation? Solve the following recurrence relation using master method.  

3.  What is quick sort? Trace the following data using quick sort algorithm.

4.  What is Greedy paradigm? Write down the Greedy job sequencing algorithm.

5.  Write algorithm to compute Longest Common Subsequence of given two sequences. Compute the LCS of “COMPANY” and “COLONY”. 

6.  What is Floyd’s algorithm? Write the details of Floyd’s algorithm to find shortest path in a graph.                                                                                                                          

7.  What is convex hull? Describe the Graham’s scan algorithm to compute convex hull.

8.  Describe the term Class-P, Class-NP and NP-completeness.   

9.  What is directed acyclic graph? How to find the shortest path from a vertex of directed acyclic graph?

10.  What is BST? Write the algorithm of insertion and deletion operation of BST