1) Explain spanning tree. Describe the design steps in prims algorithm to construct minimum spanning tree with suitable example.
2) Describe the method of binding the minimum spanning tree for a connected graph using prims algorithm.
3) Explain the design steps in kruskal algorithm to construct minimum spanning tree with suitable example.
4) Compare and contrast depth first search and birth first search. How do they fit in to the decrease and conquer strategies.
5) Describe NP-hard and NP complete problems with suitable example.
6) Describe connected components and bi-connected components with pseudocode.
7) Give a appropriate example and describe the birth first search and depth first search algorithm.
8) What do you mean by branch and bound? Describe in detail.
9) Discuss the solution for knapsack problem using branch bound techniques.