Design and Analysis of Algorithms 2075

Attempt all questions.

1.  What do you mean by complexity of an algorithm? Explain RAM model for the analysis of algorithm with example.                                                                                           

2.  What is recurrence tree method? Determine a good asymptotic upper bound of following relation using recurrence tree method. 

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

X[]={10, 8, 12, 70, 20, 5, 30}

4.  What is Huffman code? Write down Hoffman algorithm and find out its complexity.[

5.  What is dynamic programming? Find the longest common subsequence between “XYYXXY” and “XXYXXYY”.                                                                                  

6.  Explain the Kruskal’s algorithm for computing spanning tree of weighted connected graph with an example of seven nodes graph.

7.  What is left turn and right turn? How to detect the intersection of two line segment? Explain with example.                                                                                                   

8.  What types of problems are called class-P, class-NP and NP-completeness? Explain with examples.                                                                                                                       

9.  What is short path problem? Explain Dijkstra’s algorithm to compute shortest path.  

10.  Explain worst case, best case and average case of algorithm analysis with an example.