Design and Analysis of Algorithms 2072

Attempt all questions.

1.  Describe the best case and worst case complexity of an algorithm. Write algorithm for insertion sort and estimate the best and worst case complexity.  

2.  Explain the big Oh of the following recurrence relations using the iterative expansion method.                                                                                                                                                                                                                                                       

3.  What is the worst-case of quick sort? Show the how quick sort can be made to run in optimal time in the worst case.                                                                              

4.  Trace the heap-sort algorithm for the following data: {16, 41, 18, 99, 74, 20, 17, 25, 10}.   

5.  What is prefix code? How Huffman algorithm generates optimal prefix codes? Explain with suitable example. 

6.  What do you mean by dynamic programming approach for design of algorithm? Write the algorithm for matrix chain multiplication and estimate its time complexity.  

7.  Write the Dijkstra’s algorithm for single source shortest path in a weighted connected graph. Find the shortest path from the node S to other nodes in the following graph.

8.  Write an algorithm to compute the LCS of given two sequences. Trace the running of the algorithm to find the LCS of the sequences “XMJYAUZ” and “MZJAWXU”.  

9.   Define the term diagonal, ear and mouth of a simple polygon. How can you determine the intersection of two line segment efficiently? Explain in detail.

10.  Discuss NP completeness. What is the role of approximation algorithms? Explain the algorithm for vertex cover of a graph with running example.