Algorithm Quiz -1

 

  1. What is an optimal Huffman code for following set of frequency based on the first 8 Fibonacci numbers ?

 c1:1  c2:1  c3:2  c4:3  c5:5  c6:8  c7:13  c8: 21

 

  1. Can you generalized your answer to find the optimal code when the frequencies are in first  n Fibonacci numbers ?

 

  1. Run the Bellmen-Ford Algorithm on the directed graph of figure A. using vertex Y as the source. This is seen in core men book page:-----------532

Does the simulation gives a Single Source Shortest path?

 

  1. Why Dijkstra’s Algorithm doesn’t work on negative weighted graph ?

 

 

 Algorithm Quiz -2

 

1.Simulate the Algorithm for finding the articulation points in the below graph.(10)

 

 

 

 

    Note: Please save it in your computer and open it into the Microsoft Front Page

 

2. After simulate also write down the condition for a vertex to be Articulation point.(3)

 

3. An diagraph (of  course without cycle ) is given below simulate and topologically sort the given graph. See page 487. (5)

 

4. Why we need to consider decreasing order of finishing time while we topologically sort any graph? (2)