Design and Analysis of Algorithms 2074

Attempt all questions.

1.  What do you mean by complexity of an algorithm? Algorithm A has complexity O(2^logn) and algorithm B has time complexity O(log₂n) . Elaborate, how can you explain this statement.  

2.  Define the Master theorem for solving the recurrence relation and solve the following recurrence relation using this method.

3.  Write the algorithm for Merge sort and find its time complexity. Compare merge sort with quick sort in terms of time and space complexity.

4.  How can you solve the selection problem in linear time in worst case? Explain the algorithm.

5.  Discuss the fractional knapsack problem and how this problem can be solved? Explain the algorithm.

6.  What do you mean by dynamic programming approach for algorithm design? Explain the algorithm to solve the longest common subsequences and analyze its complexity.  

7.  Describe the prism’s algorithm for finding the maximum spanning tree of a graph. Also trace the algorithm for a weighted connected graph with at least 7 vertices.

8.  Write algorithm for single source shortest path in a DAG. Trace the algorithm for finding the shortest path from a source vertex in the following graph.

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

10.  Why approximation algorithms are used? Write the algorithm for approximate the vertex cover of a connected graph with example.