M.C.A. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2017.
Third Semester
Paper II DESIGN AND ANALYSIS OF ALGORITHMS
2 90232-A
Time 3 Hours Max. Marks 70
PART — A
Answer any FIVE questions.
Each question carries 6 marks.
6 30 Marks)
1. What is significance of amortized analysis? Explain with example.
2. State and describe disjoint set operations.
3. Derive the average case complexity of quick sort.
4. Solve the following job sequence problem n p2, p3, p4) 10, 15,
d2, d3, d4) 1). Find the optimal Sequence and profit.
5. Apply back tracking technique to solve the 3 — coloring problem for following
graph.
6. Write short notes on optimal binary search trees using dynamic programming.

7. Write about NP- hard and NP-complete problems.
8. Explain how branch and bound technique differs from back tracking.
PART — B
Answer ONE question from each unit.
Each question carries 10 marks.
10 40 Marks)
UNIT — I
9. Describe the basic asymptotic efficiency classes? Give example for each class.
Or
10. Illustrate connected and biconnected components with suitable example.
UNIT — II
11. What is Strassen matrix multiplication? Derive the time complexity of Strassen's
Multiplication.
Or
12. Construct minimum spanning tree using Kruskal's algorithm and also compute its
complexity.
UNIT-IlI
3 90232-A
13. Consider 5 items along with their respective weights and values
I I2, I3, I4, I5>
w 10, 20, 30,40>
v 20, 100, 90, 160>
The capacity of knapsack W 60. Find the solution to the fractional knapsack
problem.
Or
14. State and explain about 8 — queen problem with example.
UNIT IV
15. Explain about FIFO branch and bound solution with example.
Or
16. State and explain Cook's theorem.
———————