Design and Analysis of Algorithms 2076

Attempt all questions.

1.  What do you mean by time and space complexity? Explain Big Oh, Big Omega and Big Theta.

2.  Define recurrence relation. Explain the recursion tree method for solving the recurrence relation with example.

3.  Explain the algorithm for binary search with an example and also discuss its time complexity.

4.  Compare the algorithms for quick sort, merge sort and heap sort in terms the time and space complexity.

5.  Discuss how knapsack problem can be solved in greedy approach. Explain the algorithm and complexity.

6.  Describe prim's algorithm for finding the minimum spanning tree of a graph. Also trace the algorithm for a weighted connected graph.

7.  Trace the algorithm for matrix chain multiplication for the given chain ABCD with size array {5, 2, 3, 5, 4}.

8.  Define the convex hull in 2D. Write the Graham's scan algorithm and discuss its correctness and analyze its time complexity.

9.  Define the term left turn and right turn. Explain, how can you detect the intersection of two given line segments efficiently.

10.  What is the application of approximate algorithms? Write the algorithm for approximate the vertex cover of a connected graph with example.