Design and Analysis of Algorithms 2070

Attempt all questions.

1.  Explain the term Big-oh, Big-omega and Big-theta. Show that a function f=3n²+4n+7  is big theta of n².             

2.  What do you mean by a recurrence relation? Solve the following recurrence relation using iterative expansion method                                                                                              

3.  Write an algorithm for quick-sort and trace out the algorithm for the following array

4.  How can you solve the selection problem in linear time? Write the algorithm and analyze for its time complexity.                                                                                                      

5.  What is prefix code? You have given a message text having seven distinct characters  {p, q, r, s, t, u, v} with frequency {40, 20, 15, 12, 8, 3, 2}. Trace the Huffman algorithm to build the tree and obtain the optimum prefix codes for each characters.                 

6.  Explain Prim’s algorithm for computing the MST of a given graph and analyze it. Also verify the correctness of this algorithm.                                                                        

7.  Distinguish the main idea for divide and conquer approach with dynamic programming approach. Find the longest common subsequence between two sequences <A,B,C,B,D,A,B> and <B,D,C,A,B,A>.

8.  Define convex hull in 2D. Explain the gram’s scan algorithm for computing convex hull and analyze it.                                                                                                                

9.  Explain about the complexity classes P, NP and NP complete with suitable examples. 

10.  Explain Dijkstra’s algorithm for computing the single source shortest path in a graph with suitable example.