B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010
1. Differentiate Time Complexity from Space complexity.
2. What is a Recurrence Equation?
3. What is called Substitution Method?
4. What is an Optimal Solution?
5. Define Multistage Graphs.
6. Define Optimal Binary Search Tree.
7. Differentiate Explicit and Implicit Constraints.
8. What is the difference between a Live Node and a Dead Node?
9. What is a Biconnected Graph?
10. What is a FIFO branch-and-bound algorithm?
(b) Elaborate on Asymptotic Notations with examples.
and minimum items in a set of n elements.
(b) Explain Merge Sort Problem using divide and conquer technique. Give an
(b) Explain how dynamic programming is applied to solve traveling
(b) With an example, explain Graph Coloring Algorithm.
(b) With an example, explain how the branch-and-bound technique is used to solve 0/1 knapsack problem.