Design and Analysis of Algorithms 2071

Attempt all questions.

1.  Why do you need the algorithm analysis? Explain the best, worst and average case complexities with suitable example.                                                                            

2.  Explain the master method for solving the recurrence relations. Solve the following recurrence relations using this method.                                                                                     

3.  Explain the divide and conquer approach for algorithm design. Design the binary search algorithm and analyze it’s time complexity.                                                               

4.  Explain the merge-sort algorithm with example and analyze its time complexity. 

5.  What do you mean by a prefix code? How Huffman algorithm generates prefix codes? Explain with an example.

6.  Discuss the 0/1 knapsack problem and how this problem can be solved? Explain the algorithm.          

7.  Explain the algorithm to find the all pair shortest path of a weighted connected graph. Trace the algorithm for the following graph. 

8.  Write an algorithm for depth first search. Use depth first search to find a spanning tree of the following graph.

9.   Define the convex hull in 2D. Write the Grahm’s scan algorithm for computing the convex hull of points in 2D and analyze its time complexity. 

10.  What do you mean by approximation algorithm? Write the algorithm for approximate the vertex cover of a connected graph with example.